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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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] + " ");  
                }  
            }  
        }  
    }  
}