埃拉托斯特尼筛法

埃拉托斯特尼筛法

埃拉托斯特尼筛法是一种由古希腊数学家埃拉托斯特尼提出的一种简单检定素数的算法。它的原理是从2开始，将每个素数的各个倍数标记成合数，最后剩下的未被标记的数就是素数。

例如，要得到自然数25以内的全部素数，可以按照以下步骤进行：

• 列出2以后所有数：2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

• 标记第一个素数2：2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

• 用红色标记2的倍数：2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

• 如果最大数不大于最后一个标出的素数的平方，那么剩下的所有的数都是素数，否则回到第二步。本例中，25大于2的平方，返回第二步。

• 剩下的序列中第一个素数是3，用蓝色标记3的倍数：2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

• 得到的素数是2，3。

• 25仍然大于3的平方，再次返回第二步。

• 序列中第一个素数是5，用绿色标记5的倍数：2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

• 得到的素数是2，3，5。

• 因为25是5的平方，筛选完毕。

• 结论：去掉红色、蓝色和绿色的数，25内的素数是2，3，5，7，11，13，17，19，23。

#define MAX 1000002 // 定义一个常量表示最大范围
bool is_prime[MAX + 1]; // 定义一个数组表示每个数是否是质数

// 定义一个函数，初始化数组
void init() {
    for (int i = 0; i <= MAX; i++) { // 遍历所有的数
        is_prime[i] = true; // 把它们都标记为质数
    }
    is_prime[0] = is_prime[1] = false; // 把0和1标记为合数
}

// 定义一个函数，执行筛选操作
void sieve() {
    int r = (int) sqrt(MAX); // 计算最大范围的平方根
    for (int i = 2; i <= r; i++) { // 从2开始到最大范围的平方根结束
        if (is_prime[i]) { // 如果i是质数
            for (int j = i + i; j <= MAX; j += i) { // 遍历i的所有倍数
                is_prime[j] = false; // 把它们标记为合数
            }
        }
    }
}