[算法] 埃式筛和欧式筛算法简要介绍

一、摘要

素数筛是一种用于判断小于n的所有素数的算法。其中包括埃拉托斯特尼筛(埃式筛)和欧拉筛(线性筛、欧式筛)两类,本文将简要介绍埃式筛和欧式筛,并未对其中原理进行详细的介绍,若读者想了解两种筛选法的原理请查看算法学习笔记(17): 素数筛

二、埃式筛和欧拉筛介绍

1. 埃式筛

埃式筛的一个思路是,使用一个数组vector<bool> isPrime表示数字i是否是素数。从数字2开始遍历所有的小于n的数字i

  • 假如数字i是素数,即isPrime[i]=true,那么就把所有大于等于i*i,小于n数字i的倍数标记为不是素数,即令isPrime[i*j]=false
  • 假如数字i是合数,那么就跳过。

代码如下:

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

int main() {
    int n = 50;
    vector<bool> isPrime(n, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i < n;i++) {
        if (isPrime[i]) {	// 如果数字i为素数,那么就把大于等于i*i的,i的倍数设为不是素数
            for (int j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    // 输出所有小于n的素数
    for (int i = 0; i < isPrime.size(); i++) {
        if (isPrime[i]) {
            cout << i << " ";
        }
    }
    return 0;
}

2. 欧式筛

埃式筛存在一个问题是:例如,对于合数12,当遍历到数字i=2时,会把i*6=2*6=12标记为合数,当遍历到数字3时,又会把3*4=12标记为合数,因此埃式筛会存在对于一个合数多次标记的问题。欧式筛算法消除了这个问题。

欧式筛的思想是,使用一个数组vector<bool> isPrime表示数字i是否是素数,另外使用另一个数组vector<int> prime记录下所有已经找到的素数。从数字2开始遍历所有数字i

  • 假如数字i为素数,即isPrime[i]=true,就把数字i加入到数组prime;之后用数组prime中已找到的所有素数prime[j]数字i相乘,标记数字i*prime[j]为合数,直到i*prime[j]大于等于n。
  • 假如数字i为合数,即isPrime[i]=false,就直接用数组prime中已找到的所有素数prime[j]数字i相乘,标记i*prime[j]为合数,直到i*prime[j]大于等于n或者i%prime[j]==0

代码如下:

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

int main() {
    int n = 50;
    vector<bool> isPrime(n, true);
    vector<int> prime;
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i < n; i++) {
        if (isPrime[i] == true) {
            prime.push_back(i);
        }

        for (int j = 0; j < prime.size() && i * prime[j] < n; j++) {
            isPrime[i * prime[j]] = false;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
    for (int i = 0; i < prime.size(); i++) {
        cout << prime[i] << " ";
    }
    return 0;
}

三、参考

[1.] 算法学习笔记(17): 素数筛
[2.] Leetcode 计算质数 -- 埃氏筛、线性筛解析

上一篇:21天好习惯 第19天 欧拉筛


下一篇:数学模板