[数据结构与算法]埃拉托色尼筛选法

算法作用

用来产生一个不大于给定整数n的连续质数序列。

算法步骤

1. 输入一个数n
2. 初始化一个2~n的连续正数序列，作为候选质数
3. 在第一个循环中，将2的倍数消去
4. 在第二个循环中，将3的倍数消去
5. 在第三个循环中，将5的倍数消去
6. 不断做下去知道序列中没有可消除的元素为止

要点

• 设一个整数p，p以后，消去的过程就可以停止了。
• 显然p*p不会大于输入的整数n
• 设一个循环变量i
• 比i小的质数的倍数都已经被消除了，其中包括了 2i, 3i…, 所以循环到i的时候直接从i*i开始消除即可。这也可以说明只要循环到p就可以了。

Java代码实现

import java.util.Scanner;

public class Eratosthenes {
    public static void main(String[] args) {
        final int MAX_SIZE = 1000; //输入的数的最大为1000
        Scanner in = new Scanner(System.in);
        int num = in.nextInt(); //步骤第一步
        int [] nums = new int[MAX_SIZE]; //步骤第二步
        int [] res = new int[MAX_SIZE];	//结果序列

        int p = (int)Math.floor(Math.sqrt(num));//对输入的数开方并向下取整
        for (int i = 2; i < num; i ++ ){
            nums[i] = i;
        } //初始化候选序列

        for (int i = 2; i <= p; i ++ ) {
            if (nums[i] != 0) {
                int j = i*i;
                while (j <= num){
                    nums[j] = 0;
                    j += i;
                }
            }
        } //去掉合数

        for (int i = 2, j = 0; i <= num; i ++ ){
            if (nums[i] != 0) {
                res[j] = nums[i];
                j ++ ;
            }
        }//得到结果序列

        for (int i = 0; i < num; i ++ ){
            if (res[i] != 0)
            System.out.print(res[i] + " ");
        }

    }
}