这是一道编程题 :Java求1到20的最小公倍数

这道题本身的算法思想我觉得并不难,我自己试着想了一种方法,算法思想是:
用短除法，就是先把1-20的数一直除以质数2，直到所有的数都不能整除2为止，再除以3……，依此类推，
最后把除数相乘就行
下面是我运行出的代码:
package beishu;
import java.util.ArrayList;
import java.util.Arrays;
public class beishu
{
     private static ArrayList tagetIntegers=new ArrayList();//存放除数，它们的积就是所求的值；
   private static int[] primes=new int[]{2,3,5,7,11,13,17,19}; //存放的是1-20的质数，可以封装一个方法
   private static int[] datas=new int[]{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};//存放数据源
   private static int flag_1=0;//标记，当值为0的时候表示当前质数数据源中的任何一个数都不能除      
   private static int j=0;//primes的下标。当他为7的时候，并且没有数可以短除它的时候 结束（也可以断
                                      datas的所有元素都为1的时候结束，麻烦些）；
   public static void main(String[] args)
{
     int flag_time=0;//标记时间复杂度；
   while(true){
    flag_1=0;
    doit();
     if(j>=primes.length-1 && flag_1==0){
    break;
}
  if(flag_1==0)
{
j++;
}
dataPrint();
flag_time++;
}
resultPrint();

System.out.println(“时间复杂度为：”+flag_time*20);
}

//完成一次短除；
public static void doit() {
for(int i=0;i if(datas%primes[j]==0){
datas=datas/primes[j];
flag_1=1;
}
}
if(flag_1==1){
tagetIntegers.add(primes[j]);
}
}

//打印现在的所有数据；
public static void dataPrint(){
System.out.println(“datas数据源：”+Arrays.toString(datas));
System.out.println(“除数:”+tagetIntegers.toString());
System.out.println(“标记：”+flag_1);
System.out.println(“j的值：”+j);
System.out.println();
}

public static void resultPrint(){
int result=1;
for (Integer i : tagetIntegers) {
result*=i;
}
System.out.println(“最后的结果为：”+result);
}
}



不知道细心的高手发现没有,其实这种方法是来回的判断和调用,复杂度很高,我之前在一本书上看到过穷举法和分解质因数发来解决此类的问题,轮过的高手能不能给出可运行的代码,感激不尽!

1. /**
   
2. * 求若干个指定数据的最小公倍数
   
3. */
   
4. import java.io.*;
   
5. public class Main{
   
6.     public static final int N = 10; //最多可计算数据的个数
   
7.     public static void main(String args[]) throws Exception{
   
8.         Main a = new Main();
   
9.         int n = a.input("请确定数据的个数 (2<=N<="+N+") : ",2,N); //确定数据个数
   
10.         int[] data = new int[n];
    
11.         for(int i = 0; i < n; i++){
    
12.             data[i]=a.input("",0,0);                              //输入数据
    
13.         }
    
14.         int result = a.commonMultiple(data);                      //计算
    
15.         a.output(data,result);                                    //输出
    
16.     }
    
17.     /**
    
18.      * 欧几里德辗转相除算法,求a、b两个数的最小公倍数
    
19.      */
    
20.     public int basal(int a,int b){
    
21.         int i=a,j=b,s;
    
22.         for(;j!=0&&(s=i%j)!=0;i=j,j=s);  //先求a、b的最大公约数j (欧几里德辗转相除算法)
    
23.         return (j==0?0:(a*b/j));         //得到最小公倍数 (=他们的乘积除以最大公约数)
    
24.     }
    
25.     /**
    
26.      * 分治算法,求整形数组p中所有元素的最小公倍数
    
27.      */
    
28.     public int commonMultiple(int p[]){
    
29.         if (p.length<=2){
    
30.             return (p.length==1?p[0]:basal(p[0],p[1])); //基础步
    
31.         }
    
32.         int[] t1=new int[p.length/2];
    
33.         int[] t2=new int[p.length-t1.length];
    
34.         System.arraycopy(p,0,t1,0,t1.length);           //划分步1
    
35.         System.arraycopy(p,t1.length,t2,0,t2.length);   //划分步2
    
36.         p=null;
    
37.         int result1 = commonMultiple(t1);               //治理步1
    
38.         int result2 = commonMultiple(t2);               //治理步2
    
39.         return basal(result1,result2);                  //组合步
    
40.     }
    
41.     /**
    
42.      * 输入方法,s为提示语,若min==max表示对输入的数大小无限制;否则输入的数应满足 min<=n<=max
    
43.      */
    
44.     public int input(String s,int min,int max){
    
45.             BufferedReader buf=new BufferedReader(new InputStreamReader(System.in));
    
46.             int n=0;
    
47.             for(;;){
    
48.             System.out.print(s);
    
49.             try{
    
50.                 n=Integer.parseInt(buf.readLine().trim());
    
51.             }catch(NumberFormatException e){
    
52.                     System.out.println("输入错误...");
    
53.                 continue;
    
54.             }catch(IOException e){
    
55.                     System.out.println(e);
    
56.                     System.exit(0);
    
57.             }
    
58.             if (min==max||n>=min&&n<=max)break;
    
59.             System.out.println("输入错误...");
    
60.         }
    
61.         return n;
    
62.     }
    
63.     /**
    
64.      * 输出方法
    
65.      */
    
66.     public void output(int[] a,int result){
    
67.         System.out.print("[");
    
68.         for (int i = 0; i<a.length; i++){
    
69.             System.out.print(a[i]+",");
    
70.         }
    
71.         System.out.println("\b] 的最小公倍数是 "+result);
    
72.     }
    
73. }

复制代码

我在网上看到的。分享下。看能引起你的思路吗？

李松柏 发表于 2013-3-11 23:23
我在网上看到的。分享下。看能引起你的思路吗？

谢谢额 我要的就是这个效果