本文以P5736 【深基7.例2】质数筛 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)为例，介绍一下两种常用的质数筛法：埃氏筛与欧拉筛

埃氏筛

埃氏筛（Sieve of Eratosthenes）是一种古老而高效的算法，用于找出一定范围内的所有质数。质数是指除了1和其本身外，不能被其他任何数整除的自然数。埃氏筛算法的名字来源于古希腊数学家埃拉托色尼，他在公元前3世纪发明了这个算法。

埃氏筛算法的原理

埃氏筛的基本思想是从2开始，将每个质数的倍数标记为非质数，剩下的未标记的数就是质数。具体步骤如下：

  1. 初始化一个数组：假设我们要找出小于等于n的所有质数，先创建一个大小为n+1的布尔数组isPrime，并将所有元素初始化为true，表示这些数都是潜在的质数。然后将isPrime[0]和isPrime[1]设置为false，因为0和1不是质数。

  2. 从2开始：从第一个质数2开始，标记所有2的倍数（从4开始，间隔为2的数）为非质数，即将isPrime[4], isPrime[6], isPrime[8]等设置为false。

  3. 找到下一个未标记的数：找到数组中下一个值为true的数，它是下一个质数。然后标记这个数的所有倍数为非质数。

  4. 重复步骤3：继续这个过程，直到处理到数组的平方根位置。

埃氏筛算法的时间复杂度

埃氏筛算法的时间复杂度为O(n log log n)。这是因为在标记过程中，每个数的倍数仅被标记一次。相较于直接判断每个数是否为质数的O(n√n)时间复杂度，埃氏筛在处理大规模数据时具有显著的效率优势。

埃氏筛算法的实现

以下是Python实现埃氏筛算法的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def sieve_of_eratosthenes(n):
    is_prime = [True] * (n + 1)
    is_prime[0], is_prime[1] = False, False
    p = 2
    while (p * p <= n):
        if is_prime[p]:
            for i in range(p * p, n + 1, p):
                is_prime[i] = False
        p += 1
    prime_numbers = [p for p in range(n + 1) if is_prime[p]]
    return prime_numbers

# 示例
n = 30
print(f"小于等于 {n} 的质数有: {sieve_of_eratosthenes(n)}")

C++实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <vector>

// 埃氏筛算法函数
std::vector<int> sieve_of_eratosthenes(int n) {
    std::vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false; // 0和1不是质数
    
    for (int p = 2; p * p <= n; ++p) {
        if (is_prime[p]) {
            // 将p的所有倍数标记为非质数
            for (int i = p * p; i <= n; i += p) {
                is_prime[i] = false;
            }
        }
    }

    // 收集所有的质数
    std::vector<int> prime_numbers;
    for (int p = 2; p <= n; ++p) {
        if (is_prime[p]) {
            prime_numbers.push_back(p);
        }
    }

    return prime_numbers;
}

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

上述例题AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
// 埃氏筛算法函数
vector<int> sieve_of_eratosthenes(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false; // 0和1不是质数
    
    for (int p = 2; p * p <= n; ++p) {
        if (is_prime[p]) {
            // 将p的所有倍数标记为非质数
            for (int i = p * p; i <= n; i += p) {
                is_prime[i] = false;
            }
        }
    }

    // 收集所有的质数
    vector<int> prime_numbers;
    for (int p = 2; p <= n; ++p) {
        if (is_prime[p]) {
            prime_numbers.push_back(p);
        }
    }

    return prime_numbers;
}

int main() {
    int N = 100000,n;
    vector<int> primes = sieve_of_eratosthenes(N);
    set<int> primes_set(primes.begin(), primes.end());
    scanf("%d", &n);
    for(int i=1;i<=n;++i){
        int a;
        cin >> a;
        if (primes_set.find(a)!=primes_set.end()) cout << a << " ";
    }
    cout << endl;
    return 0;
}

应用与优势

埃氏筛不仅在理论上具有重要意义，在实际应用中也非常广泛。它不仅适用于编程竞赛中寻找质数的问题，也可以用于加密算法（如RSA算法）中的大质数生成。由于其高效性，埃氏筛在处理大范围数据时表现出色。

总之，埃氏筛是一种简单而高效的质数筛选算法，通过巧妙地标记非质数，显著减少了判断质数的计算量，是计算数学中的一个经典算法。

欧拉筛

欧拉筛（Sieve of Euler）是一种用于寻找一定范围内所有质数的高效算法，是埃氏筛的优化版本。欧拉筛在标记合数时，避免了重复标记，使得其时间复杂度和空间复杂度都优于埃氏筛。

欧拉筛算法的原理

欧拉筛的基本思想是通过线性筛选的方法，在标记合数时，每个合数只会被其最小的质因数标记一次，从而避免了重复标记。具体步骤如下：

  1. 初始化数组：创建一个大小为n+1的布尔数组isPrime，所有元素初始化为true，表示这些数都是潜在的质数。同时，创建一个空列表primes，用于存储找到的质数。

  2. 从2开始筛选：从2开始，依次检查每个数是否为质数。如果是质数，将其加入primes列表中。

  3. 标记合数：对每一个质数p，标记从p开始的所有p的倍数为非质数。需要注意的是，对于每个合数，只用其最小的质因数来标记，这样可以避免重复标记。

  4. 继续筛选：重复上述过程，直到遍历到n。

欧拉筛算法的时间复杂度

欧拉筛的时间复杂度为O(n)，比埃氏筛的O(n log log n)更为高效。这是因为欧拉筛在标记过程中，每个合数只会被标记一次，不会像埃氏筛那样存在重复标记的情况。

欧拉筛算法的实现

以下是Python实现欧拉筛算法的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def sieve_of_euler(n):
    is_prime = [True] * (n + 1)
    primes = []
    for i in range(2, n + 1):
        if is_prime[i]:
            primes.append(i)
        for p in primes:
            if i * p > n:
                break
            is_prime[i * p] = False
            if i % p == 0:
                break
    return primes

# 示例
n = 30
print(f"小于等于 {n} 的质数有: {sieve_of_euler(n)}")

C++实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <vector>

std::vector<int> sieve_of_euler(int n) {
    std::vector<bool> is_prime(n + 1, true);
    std::vector<int> primes;
    
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
        for (int p : primes) {
            if (i * p > n) break;
            is_prime[i * p] = false;
            if (i % p == 0) break;
        }
    }
    
    return primes;
}

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

上述例题AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
//  欧拉筛算法函数
std::vector<int> sieve_of_euler(int n) {
    std::vector<bool> is_prime(n + 1, true);
    std::vector<int> primes;
    
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
        for (int p : primes) {
            if (i * p > n) break;
            is_prime[i * p] = false;
            if (i % p == 0) break;
        }
    }
    
    return primes;
}

int main() {
    int N = 100000,n;
    vector<int> primes = sieve_of_euler(N);
    set<int> primes_set(primes.begin(), primes.end());
    scanf("%d", &n);
    for(int i=1;i<=n;++i){
        int a;
        cin >> a;
        if (primes_set.find(a)!=primes_set.end()) cout << a << " ";
    }
    cout << endl;
    return 0;
}

应用与优势

欧拉筛在寻找质数的应用中表现出色，特别是在处理大规模数据时，其线性时间复杂度显著提升了算法的效率。与埃氏筛相比，欧拉筛通过减少重复标记的操作，优化了空间和时间的使用，是质数筛选算法中的一种重要改进。

总的来说，欧拉筛是一种高效且优化的质数筛选算法，通过避免重复标记合数，显著提升了筛选速度和空间利用率，是计算数学中不可或缺的工具。无论是在理论研究还是实际应用中，欧拉筛都展现出了其独特的优势。

总结与对比

埃氏筛

  • 原理：从2开始，将每个质数的倍数标记为非质数，剩下的即为质数。
  • 时间复杂度：O(n log log n)。
  • 空间复杂度：O(n)。
  • 优点：实现简单，适合初学者。

欧拉筛

  • 原理：线性筛选，每个合数只会被其最小质因数标记一次，避免重复标记。
  • 时间复杂度：O(n)。
  • 空间复杂度：O(n)。
  • 优点：效率更高，适合处理大规模数据。

对比

  1. 效率：欧拉筛更高效，时间复杂度为O(n)，适合大规模数据；埃氏筛为O(n log log n)。
  2. 标记过程：欧拉筛避免了重复标记，标记过程更优化。
  3. 实现复杂度：埃氏筛简单直观，欧拉筛稍复杂但更高效。

总结

埃氏筛和欧拉筛各有优势，埃氏筛实现简单，适合初学者和处理较小规模的数据。而欧拉筛在效率上更胜一筹，适合处理大规模的数据，在高效性上表现尤为突出。选择哪种算法取决于具体应用场景和数据规模。在学习和研究过程中，可以从埃氏筛入手，逐步理解和实现欧拉筛，深入掌握质数筛选算法的优化和高效实现。

本站由 @anonymity 使用 Stellar 主题创建。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。