您的位置: 首页  >  文章  >  java代码求n个数的最小公倍数,HDOJ 2028，3种方法实现

java代码求n个数的最小公倍数,HDOJ 2028，3种方法实现

分类: 文章 • 2023-11-15 12:41:58

题目大意为：求n个正整数的最小公倍数

解题思路：求最小公倍数的方法我们在数学中学到过，我知道的有2种方法分别是

（1）求最大公约数法

（2）使用辗转相除法求 比如：下图为求 2 4 6的最小公倍数，用2 4 6做辗转相除法可得最小公倍数为2*1*2*3java代码求n个数的最小公倍数,HDOJ 2028，3种方法实现

而第三种方法为：先求出n个数中最大的那个数max，如果这个数可以整除所有的数，则这是最小公倍数
如果不能则令max+1直到找到可以整除所有的数的那个数为止


前2种方法应该是我们最先想到的，但是第三中方法我个人觉得是最容易实现的

第一种方法代码实现如下：

[java] view plain copy
  1. //通过求最大公约数方法求最小公倍数  
  2. import java.util.*;  
  3. class Main{  
  4.     public static void main(String args[]){  
  5.         Scanner sc=new Scanner(System.in);  
  6.         while(sc.hasNext()){  
  7.             int n=sc.nextInt();  
  8.             int a[]=new int[n];  
  9.             for(int i=0;i<n;i++){  
  10.                 a[i]=sc.nextInt();  
  11.             }  
  12.             int multipleAll=multiple(a,0);  
  13.             System.out.println(multipleAll);  
  14.         }  
  15.     }  
  16.     public static int divstor(int x,int y){//求2个数的最大公约数  
  17.         int min = x < y ? x : y ;    //取两个数的较小的那个  
  18.         for(int divstorX = min ; divstorX > 0 ; divstorX--){  
  19.             if(x%divstorX==0&&y%divstorX==0){      
  20.                 //从较小的那个数开始逐渐往后寻找直到找到可以同时整除这2个数的数就是最大公约数  
  21.                 return divstorX;  
  22.             }  
  23.         }  
  24.         return 1;  
  25.     }  
  26.     public static int multiple(int a[],int count){  
  27.         //count表示从0开始，因为数组是从0开始的（后面也是这样）也就是从第一个数开始  
  28.           
  29.         int divstorX=divstor(a[count],a[count+1]);      
  30.         //求第count-1个数与第count个数的最大公约数  
  31.           
  32.         int multipleX=a[count]/divstorX*a[count+1];  
  33.         //求这2个数的最小公倍数      
  34.         //这句不能是int multipleX=a[count]*a[count+1]/divstorX；  
  35.         //虽然结果是一样的，但是先把2个int相乘可能会超过int的范围，所以先除，在乘，可以防止越界  
  36.           
  37.         a[count+1]=multipleX;          
  38.         //把2个数的最小公倍数赋值给后面那个数也就是第count+2个数  
  39.           
  40.         count++;    //使标记转到第count+2个数  
  41.           
  42.         if(count!=a.length-1){    //如果count不是在倒数第二个数  
  43.             return multiple(a,count);  
  44.             //在求第count+1个数开始与第count+2个数的最小公倍数  
  45.         }  
  46.           
  47.         return multipleX;    //求完之后返回这个数组的最小公倍数  
  48.     }  
  49. }  
第二种辗转相除法:

[java] view plain copy
  1. /* 
  2.         使用辗转相除法求n个数的最小公倍数 
  3. */  
  4. import java.util.*;  
  5. class Main{  
  6.     public static void main(String args[]){  
  7.         Scanner sc=new Scanner(System.in);  
  8.         while(sc.hasNext()){  
  9.             int n=sc.nextInt();  
  10.             int a[]=new int[n];  
  11.             int max=0;  
  12.               
  13.             for(int i=0;i<n;i++){  
  14.                 a[i]=sc.nextInt();  
  15.                 if(a[i]>max){  
  16.                     max=a[i];  
  17.                 }  
  18.             }  
  19.               
  20.             int s=1;  
  21.             for(int i=2;i<=max;i++){  
  22.                   
  23.                 boolean b=false;    //设置标记  
  24.                   
  25.                 for(int j=0;j<n;j++){  
  26.                     if(a[j]%i==0){  
  27.                         a[j]=a[j]/i;      
  28.                         b=true;       
  29.                 //只要有一个数可以被i整除就令标记为真，并改变可以被整除的那个值，改变的值将出                现在辗转相除法的下一排  
  30.                     }  
  31.                 }  
  32.                   
  33.                 if(b){  
  34.                     s*=i;   //标记为真说明辗转相除法还能继续；令使s累乘边上的数  
  35.                     i--;  
  36.                 }  
  37.             }  
  38.               
  39.             for(int i=0;i<n;i++){  
  40.                 s*=a[i];    //在将s与最后得到的不能再继续辗转相除的数累乘  
  41.             }  
  42.               
  43.             System.out.println(s);  
  44.         }  
  45.     }  
  46. }  
第三种:

[java] view plain copy
  1. 第三种方法代码实现如下：  
  2. //先求出n个数中最大的那个数max，如果这个数可以整除所有的数，则这是最小公倍数  
  3. //如果不能则令max+1直到找到可以整除所有的数的那个数为止  
  4. import java.util.*;  
  5. class Main{  
  6.     public static void main(String args[]){  
  7.         Scanner sc=new Scanner(System.in);  
  8.         while(sc.hasNext()){  
  9.             int n=sc.nextInt();  
  10.             int a[]=new int[n];  
  11.             int max=0;  
  12.             for(int i=0;i<n;i++){  
  13.                 a[i]=sc.nextInt();  
  14.                 if(max<a[i]){  
  15.                     max=a[i];   //先找出这n个数的那个最大的数  
  16.                 }  
  17.             }  
  18.             for(int i=max;;i++){  
  19.                 boolean b=true; //设置标记  
  20.                 for(int j=0;j<n;j++){  
  21.                     if(max%a[j]!=0){  
  22.                         b=false;      
  23.             //只要有一个数不能整除max则令标记为false  
  24.                     }  
  25.                 }  
  26.                 max++;  
  27.                 if(b){  //如果标记为true说明该max可以整除这n个数  
  28.                     //则max为最小公倍数  
  29.                     System.out.println(i);  
  30.                     break;  //跳出循环  
  31.                 }  
  32.             }  
  33.         }  
  34.     }  
  35. 转载自https://blog.csdn.net/Dragon_Dai_2017/article/details/70303100

相关推荐