素数筛是一种用于判断小于n的所有素数的算法。其中包括埃拉托斯特尼筛(埃式筛)和欧拉筛(线性筛、欧式筛)两类,本文将简要介绍埃式筛和欧式筛,并未对其中原理进行详细的介绍,若读者想了解两种筛选法的原理请查看算法学习笔记(17): 素数筛。
埃式筛的一个思路是,使用一个数组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; }
埃式筛存在一个问题是:例如,对于
合数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 计算质数 -- 埃氏筛、线性筛解析