黑马程序员技术交流社区

标题: 都是求质数，咱来两个个求100之内的素数 ！程序好不好大... [打印本页]
作者: 史卜坤    时间: 2012-6-27 07:31
标题: 都是求质数，咱来两个个求100之内的素数 ！程序好不好大...
public class lianxi27 {
public static void main(String[] args) {
    boolean b =false;
    System.out.print(2 + " ");
    System.out.print(3 + " ");
    for(int i=3; i<100; i+=2) {
     for(int j=2; j<=Math.sqrt(i); j++) {
      if(i % j == 0) {b = false;
                      break;
       } else{b = true;}
     }
   if(b == true) {System.out.print(i + " ");}
    }
   }
}
//下面这个程序使用除1位素数得2位方法。

public class lianxi27a {
public static void main(String[] args) {
    int[] a = new int[]{2, 3, 5, 7};
   for(int j=0; j<4; j++)System.out.print(a[j] + " ");
    boolean b =false;
    for(int i=11; i<100; i+=2) {
     for(int j=0; j<4; j++) {
      if(i % a[j] == 0) {b = false;
                      break;
       } else{b = true;}
     }
   if(b == true) {System.out.print(i + " ");}
    }
   }
}
作者: 韦念欣    时间: 2012-6-27 09:20
本帖最后由 韦念欣 于 2012-6-27 09:30 编辑

楼主的第2个方法有些问题，楼主使用大数据量测试看看，结果不太对。

我写了一个效率更高的算法，1到100000以内的素数，注释掉输出语句后，20毫秒以内就可以得出正确结果（在我的机子上），而楼主第1种方法注释掉输出语句后 需要高达400毫秒的时间，楼主可以参考价参考。

这个算法是厄拉多塞筛法。
厄拉多塞是一位古希腊数学家，他在寻找素数时，采用了一种与众不同的方法，算法思想：先将2－N的各数写在纸上：在2的上面画一个圆圈，然后划去2的其他倍数；第一个既未画圈又没有被划去的数是3，将它画圈，再划去3的其他倍数；现在既未画圈又没有被划去的第一个数 是5，将它画圈，并划去5的其他倍数……依次类推，一直到所有小于或等于N的各数都画了圈或划去为止。这时，表中画了圈的以及未划去的那些数正好就是小于N的素数。
  1. class Prime {
  2.         static final int MAX = 1000000;
  3.         static boolean[] isPrime = new boolean[MAX];
  4.         private static void prime_weinianxin(){
  5.                 for(int i=2;i<MAX;i++)
  6.                                 isPrime[i] = true;
  7.                 for(int i=2;i*i<MAX;i++){
  8.                         if(isPrime[i]){
  9.                                 for(int j=i;j*i<MAX;j++){
  10.                                         isPrime[j*i] = false;
  11.                                 }
  12.                         }
  13.                 }
  14.         }
  15.         
  16.         public static void main(String[] args){
  17.                 long start = System.currentTimeMillis();
  18.                 prime_weinianxin();
  19.                 int count = 0;
  20.                 for(int i=0;i<isPrime.length;i++){
  21.                         if(isPrime[i]){
  22.                                 count++;
  23.                                 // System.out.println(i);        // 输出语句，删掉注释即可看到1到100000以内的所有素数
  24.                         }
  25.                 }
  26.                 System.out.println("1到100000以内的素数共有："+count+"个");
  27.                 long end = System.currentTimeMillis();
  28.                 System.out.println("用时: "+(end-start)+"毫秒");
  29.         }
  30. }
复制代码




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2