6.1.9 蓝桥杯数学之素数筛

6.1.9 蓝桥杯数学之素数筛

引言

在编程竞赛和算法设计中，寻找素数是一个常见且重要的任务。素数筛，尤其是埃拉托斯特尼筛法（埃氏筛）和线性筛，是两种高效寻找素数的方法。本文将介绍这些方法及其在蓝桥杯等编程竞赛中的应用。

埃拉托斯特尼筛法（埃氏筛）

埃拉托斯特尼筛法是最古老和最简单的素数筛选方法之一。

实现原理

1. 创建一个布尔数组，初始时假设所有数都是素数。
2. 从第一个素数2开始，将所有2的倍数标记为非素数。
3. 继续到下一个未被标记的数，重复步骤2。
4. 进行到不超过所需范围的平方根为止。

C++ 实现

#include <iostream>
#include <vector>
using namespace std;

vector<int> sieveOfEratosthenes(int n) {
    vector<bool> isPrime(n+1, true);
    vector<int> primes;
    isPrime[0] = isPrime[1] = false;
    
    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p) {
                isPrime[i] = false;
            }
        }
    }

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

    return primes;
}

int main() {
    int n;
    cout << "Enter the upper limit for prime numbers: ";
    cin >> n;
    vector<int> primes = sieveOfEratosthenes(n);
    for (int prime : primes) {
        cout << prime << " ";
    }
    return 0;
}

线性筛法

线性筛法，或称埃拉托斯特尼筛法的优化版本，可以更高效地筛选素数，尤其是在处理大范围内的素数时。

实现原理

1. 线性筛法维护一个素数列表。
2. 对于每个新找到的素数，只筛去那些由该素数和它之前的素数相乘得到的合数。
3. 这样可以确保每个合数只被它的最小素因子筛去，提高效率。

C++ 实现

#include <iostream>
#include <vector>
using namespace std;

vector<int> linearSieve(int n) {
    vector<int> primes;
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i <= n; ++i) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
        for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
            isPrime[i * primes[j]] = false;
            if (i % primes[j] == 0) break;
        }
    }

    return primes;
}

int main() {
    int n;
    cout << "Enter the upper limit for prime numbers: ";
    cin >> n;
    vector<int> primes = linearSieve(n);
    for (int prime : primes) {
        cout << prime << " ";
    }
    return 0;
}

结论

了解和掌握不同的素数筛选方法对于编程竞赛选手来说非常重要。这些方法不仅能帮助我们快速找到素数，还可以应用于各种与数论相关的问题，如因数分解、公约数和公倍数的计算等。