java實作第二屆藍橋杯最小公倍數（c++）

最小公倍數、

為什麼1小時有60分鐘，而不是100分鐘呢？這是曆史上的習慣導緻。

但也并非純粹的偶然：60是個優秀的數字，它的因子比較多。

事實上，它是1至6的每個數字的倍數。即1,2,3,4,5,6都是可以除盡60。

我們希望尋找到能除盡1至n的的每個數字的最小整數。

不要小看這個數字，它可能十分大，比如n=100, 則該數為：

69720375229712477164533808935312303556800

請編寫程式，實作對使用者輸入的 n （n<100）求出1~n的最小公倍數。

例如：

使用者輸入：

6

程式輸出：

60

使用者輸入：

10

程式輸出：

2520

要求考生把所有函數寫在一個檔案中。調試好後，存入與考生檔案夾下對應題号的“解答.txt”中即可。

相關的工程檔案不要拷入。

對于程式設計題目，要求選手給出的解答完全符合ANSI C标準，不能使用c++特性；

不能使用諸如繪圖、中斷調用等硬體相關或作業系統相關的API。

Java解法：

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    
    public void getResult(int n) {
        BigInteger temp1 = BigInteger.ONE;
        BigInteger temp2 = BigInteger.ONE;
        BigInteger temp3 = BigInteger.ONE;
        for(int i = 2;i <= n;i++) {
            temp1 = temp3;
            temp2 = new BigInteger(""+i);
            temp3 = temp1.gcd(temp2);
            temp3 = temp1.multiply(temp2).divide(temp3);
        }
        System.out.println(temp3);
    }
    
    public static void main(String[] args) {
        Main test = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        test.getResult(n);
    }
}
           

C++解法：

解答：
最小公倍數就是所有質數的相應幂的積
比如N=10
小于10的質數有2,3,5,7
對應的最大幂是：3，2，1，1
則最小公倍數是：2^3x3^2x5^1x7^1 = 2520

 #include <iostream>
 #include <cstring>
 #include <cmath>
 using namespace std;
 
 int a[50] = {0};//存素數 
 bool vis[100];
 int b[50] = {0};//存幂次 
 
 void init_prim()//求小于100的所有素數存入數組a 
 {
      int i,j,k;
      int m = (int)(sqrt(100.0)+0.5);
      memset(vis,0,sizeof(vis));
      vis[0] = 1;
      vis[1] = 1;//必須加上,否則第一個素數别認為是1 
      for(i=2; i<=m; i++)
      if(!vis[i])
      {
           for(j=2*i; j<=100; j+=i)
                vis[j] = 1;
      }
      int t = 0;
      for(k=0; k<100; k++)
      if(!vis[k])
           a[t++] = k;
 }
      
 int main()
 {
      int i,j,k;
      init_prim();
      int n;
      //2^6 = 64,2^7 = 128;由于n最大100，幂次最大6 
     // for(i=0 ; i<100; i++)//素數沒問題 
     // if(!vis[i])
     //      cout<<i<<endl;
    //  while(1);
      while(cin>>n)
      {
           memset(b,0,sizeof(b));
           for(i=0; i<=n&&a[i]<=n; i++)//”1到n素數個數小于n的一半 “不對，3有兩個素數 
           {
               // cout<<a[i]<<"-----"<<endl;
                for(j=1; j<=6; j++)
                {
                     if(pow((double)a[i],(double)j)>(double)n)
                     {
                          b[i] = j -1;//b的下标不必新開  
                          break;
                     }
                     else if(pow((double)a[i],(double)j) == (double)n)//必須分開 
                     {
                           b[i] = j;
                          break;     
                     }
                }                                   
           }
           //不知道是不是pow函數的問題，把ans定義為int得出的結果出問題，double就對了 
           double ans = 1;
           for(k=0; k<i; k++)
           {
                //cout<<a[k]<<"........"<<b[k]<<endl;
                ans *= pow((double)a[k],(double)b[k]);
           }
           cout<<(int)ans<<endl;      
      }
      return 0;     
 }
 
 //該程式 到25時就溢出，ans換位long long前幾個就錯誤啦，此時需要把pow函數換掉

 #include <iostream>
 #include <cstdio>
 #include <cstring>
 #include <cmath>
 using namespace std;
 
 const int N = 105;
 int n;
 int a[N][50];
 int b[N] = {0};
 
 void multiply()
 {
     int i,j,k;
     memset(a,0,sizeof(a));
     for(i=3; i<=100; i++)
     {
         /*
         下面的是直接按平常的乘法，乘數的一位乘以被乘數的每一位并處理進位；另外是乘數整體乘以被乘數的每一位最後統一處理進位
         */
         int temp = 0; 
         a[i][0] = 1;//很重要 
         for(j=2; j<=i; j++)
         {
             int  c = 0; 
             for(k=0; k<50; k++)//最大不超過160位 ，目前是100!,最後除以3等50 
             {
                 temp = a[i][k]*b[j] + c;
                 a[i][k] = temp%1000;
                 c = temp/1000;
             }          
         }
     }
 }
 
 void printData(int n)
 {
     int i,j,k;
     for(i=49; i>=0; i--)
     if(a[n][i])
         break;
     cout<<a[n][i];//第一個不輸出前導0 
     for(j=i-1; j>=0; j--)
         printf("%03d",a[n][j]);
     cout<<endl;   
 }
 
 int main()
 {
     int i, j, k;
     for(i=0; i<N; i++)
             b[i] = i;
     for(i=2; i<N; i++)
         for(j=i+1; j<=N; j++)
         {
             if(b[j]%b[i]==0)
                 b[j] /= b[i];
             //cout<<b[j]<<endl;
         }
     //for(i=0; i<100; i++)
       //  cout<<b[i]<<endl;
     //while(1);
     multiply();
     
     while(cin>>n)
     {
         
         if(n==1||n==2)
         {
             cout<<n<<endl;
             continue;
         }
         
         printData(n);
     }
     return 0;
 }