埃拉托色尼筛算法

     还记得当时学习数据结构时老师留过一道作业题：编写程序打印出小于命令行参数所给定的整数的所有素数。当时我就是简单的利用穷举法实现的，呵呵，就是一个一个地进行判断。后来作业交了上去，也就不了了之了。老师并没有进行讲解，今天突然看到了应用数组解决这一问题的埃拉托色尼筛算法，恩！感觉很优美，省去了穷举法的大量的除法运算，下面我们就来看看其中的奥秘。
     首先我再明确一下素数的概念：一个正整数如果不等于1而且除了自己和1没有其他正因数，则称其为一个素数(也称质数)；否则称其为合数。1既不是素数也不是合数。
     埃拉托色尼筛算法的思想是：申请一个布尔数组a，如果i是素数，就把a[i]置为true，否则，就把a[i]置为false。首先，把所有数组元素都置为true，表明所有数都是素数。然后再把对应于下标为非素数(是已知素数的倍数，因为2是我们知道的最小的素数，所以以2作为跌代的起点)的数组元素设为false。如果在所有较小素数的倍数都被设为false值后，a[i]的值仍然是true,那么它肯定是一个素数。用JAVA实现的代码如下：

public class Primes {
      public static void main(String[] args) {
            int N = Integer.parseInt(args[0]);
            boolean[] a = new boolean[N];
            for(int i = 2; i < N; i++) {
                  a[i] = true;
             }
             for(int i = 2; i < N; i++) {
                  if(a[i] != false) {
                      for(int j = i; j*i < N; j++) {
                           a[i*j] = false;
                      }
                 }
             }
            for(int i = 2; i < N; i++) {
                 if(a[i]) {
                     System.out.println("" + i);
                 }
            }
      }
}

评论

1 楼 jpkuser 2010-05-20  

楼主给的代码可改进：
一．　外层循环的终止条件不必为i < N，此条件作了无用功，且如果N过大，如2000000会报java.lang.IndexOutOfBoundsException异常；
      因此，外层循环的终止条件应改为i*i < N
二．　用boolean数组不如用BitSet高效　
　　　因此，语句boolean[] a = new boolean[N];
　　　　　　　可改为BitSet b=new BitSet(N);
　　　　　　相应的a[i] = true；
　　　　　　　　　a[i*j] = false
　　　　　　　分别改为b.set(i);
　　　　　　　　　    b.clear(i*j);

完整代码如下：
　　　　　　         BitSet bs=new BitSet(n+1);
int i;
for(i=2;i<=n;i++)
　　bs.set(i);
for(i = 2; i*i < n; i++) {   
            　　　　　　if(bs.get(i)) {
            　　　　for(int j = i; j*i <= n; j++)    
                    　　　　　 bs.clear(i*j);
                       }
                   }