埃拉托斯特尼筛法

屈老师

筛选质数的常用算法是埃拉托斯特尼筛法（Sieve of Eratosthenes）。这是一个高效的算法，可以在给定范围内找到所有质数。以下是该算法的步骤和Python实现：

算法步骤

创建一个从2到n的列表，假设所有这些数都是质数。
从第一个质数（2）开始，将其所有倍数标记为非质数。
找到列表中下一个没有标记的数，这个数是下一个质数。
重复步骤2和3，直到处理完列表中的所有数。

Python实现

def sieve_of_eratosthenes(n):
    primes = [True] * (n + 1)  # 创建一个布尔列表，初始时所有元素设为True
    p = 2
    while p * p <= n:
        # 如果 primes[p] 未被标记为 False, 则是一个质数
        if primes[p]:
            # 更新所有 p 的倍数，从 p*p 开始标记为 False
            for i in range(p * p, n + 1, p):
                primes[i] = False
        p += 1
    
    # 收集所有质数
    prime_numbers = [p for p in range(2, n + 1) if primes[p]]
    return prime_numbers

# 测试算法
n = 50
print(f"小于等于 {n} 的所有质数: {sieve_of_eratosthenes(n)}")

C++实现

#include <iostream>
#include <vector>

std::vector<int> sieve_of_eratosthenes(int n) {
    std::vector<bool> primes(n + 1, true); // 创建一个布尔向量，初始时所有元素设为true
    std::vector<int> prime_numbers;

    primes[0] = primes[1] = false; // 0和1不是质数

    for (int p = 2; p * p <= n; ++p) {
        if (primes[p]) {
            for (int i = p * p; i <= n; i += p) {
                primes[i] = false;
            }
        }
    }

    for (int p = 2; p <= n; ++p) {
        if (primes[p]) {
            prime_numbers.push_back(p);
        }
    }

    return prime_numbers;
}

int main() {
    int n = 50;
    std::vector<int> primes = sieve_of_eratosthenes(n);
    std::cout << "小于等于 " << n << " 的所有质数: ";
    for (int prime : primes) {
        std::cout << prime << " ";
    }
    std::cout << std::endl;
    return 0;
}

解释

初始化：我们创建一个长度为n+1的布尔列表，所有元素初始时都设置为True。因为我们要标记从2到n的数，索引范围为0到n，所以需要n+1的长度。
标记非质数：从第一个质数（2）开始，将其所有倍数（从p*p开始）标记为False。
寻找下一个质数：如果一个数p没有被标记为False，则它是一个质数，继续标记它的所有倍数。
收集质数：在标记完成后，所有仍然为True的索引对应的数都是质数。

优化

内存优化：对于大范围的筛选，可以使用位数组（bit array）来节省内存。
步长优化：从p*p开始标记而不是2*p，可以减少不必要的标记操作，因为2*p到(p-1)*p之间的倍数已经被之前的质数标记过了。