筛法求素数 的基本思想是:把从1开始的、某一范围内的 正整数 从小到大顺序排列, 1不是素数,首先把它筛掉。剩下的数中选择最小的数temp,这个数 是素数,而temp的倍数可以直接筛掉 。逐步迭代,可求出指定范围内的素数。

public class Main {  
    public static void main(String[] args) {  
        Scanner in = new Scanner(System.in);  
        while (in.hasNextInt()) {  
            int n = in.nextInt();  
            int[] array = new int[n];  
//            初始化筛数组
            for (int i = 2; i < n; i++) {  
                array[i] = i;  
            }  
//            如果没被筛出,则记录,并将temp的倍数筛出
            for (int i = 2; i < n; i++) {  
                if (array[i] != 0) {  
                    int j, temp;  
                    temp = array[i];  
                    for (j = 2 * temp; j < n; j += temp) {  
                        array[j] = 0;  
                    }  
                    System.out.print(array[i] + " ");  
                }  
            }  
        }  
    }  
}
最后修改于 2018-02-12 11:22:56
上一篇