Loading... 源自项目：[2020贵软自无转系面试题参考答案](https://github.com/Co1lin/Articles/blob/master/2020%E8%B4%B5%E8%BD%AF%E8%87%AA%E6%97%A0%E8%BD%AC%E7%B3%BB%E9%9D%A2%E8%AF%95%E9%A2%98%E5%8F%82%E8%80%83%E7%AD%94%E6%A1%88.md) 其中有个面试题，问如何求1~1000以内的素数，由于数据规模小，可以用“土办法”。但如果把1000改为更大的数，就需要用到素数筛了。参考回答如下。后附实现代码。 ## 埃氏筛 可以用埃氏筛的方式。先开一个长度为N+1的布尔型数组，数组的下标对应N以内的数，先把数组初始化为全0，意味着是素数。接下来，从i=2开始遍历这些数，如果它的布尔标记为0，那么就把它的2倍、它的3倍、……一直到N以内最大的它的整数倍为止，将这些数都标记为1，意思是不是素数。如果i已经被标记为1，那么就直接跳过即可。最后N以内的素数就是标记仍然为0的数。（0、1除外。）时间复杂度为O(n\*log(log(n)))。 （改进版：） 可以用埃氏筛的方式。先开一个长度为N+1的布尔型数组，数组的下标对应N以内的数，先把数组初始化为全0，意味着是素数。接下来，从i=2开始遍历这些数，如果它的布尔标记为0，那么从j=i\*i开始，每次j递增i，将j对应的数都标记为1，意思是不是素数，直到j大于N。如果i已经被标记为1，那么就直接跳过即可。最后N以内的素数就是标记仍然为0的数。（0、1除外。）时间复杂度为O(n\*log(log(n)))。 （大佬们可以继续前进！如果问你不是1000而是300000000呢？） ## 欧拉筛 可以采用欧拉线性筛的方式。开两个长度为(N+1)的数组，一个为bool型，初始化为0，用于标记是否是素数；另一个int型，名为prime，初始化为全0，用于存储已经找到的素数。从i=2开始，我们用外层循环遍历每一个数，如果i的标记是0，那么把i添加进记录素数的数组中；然后无论i的标记，开启内层循环，令j=0，开始遍历prime中存的每一个素数prime\[j\]，将i\*prime\[j\]都标记为1。一直循环到某次i%prime\[j\]等于0，终止内层循环，继续外层循环，直至i>N结束外层循环。最后N以内的素数就是保存在prime数组中前面的非零数。 本算法时间复杂度为O(n)，因此称为线性筛。其中优化的原理在于每个合数都只被它最小的质因子筛去，减少了不必要的重复。 欧拉筛的关键代码是 ```cpp if (i % primes[j] == 0) // most important break; ``` 它的目的是保证每个合数都只被它最小的质因子筛去。 比如，i=15时，会依次筛掉`i*primes[0]=15*2=30`，和`i*primes[1]=15*3=45`。而此时`i%primes[1]=15%3=0`，因此会`break`，于是`i*primes[2]=15*5=75`就不会在i=15时筛掉；75会被它最小的质因子3筛掉，也就是i=25时，被`i*primes[1]=25*3=75`筛掉。 为什么呢？简单来说，当`i%primes[j]=0`时，i有质因子`primes[j]`。接下来是准备用`primes[j+1]`筛掉`i*primes[j+1]`；而由于i有质因子`primes[j]`，`i*primes[j+1]`就有质因子`primes[j]`；同时，`i*primes[j+1]`有质因子`primes[j+1]`，且`primes[j]<primes[j+1]`。因此如果用`primes[j+1]`筛掉`i*primes[j+1]`，而不是用`primes[j]`筛掉`i*primes[j+1]`，就不满足“保证每个合数都只被它最小的质因子筛去”了。因此当`i%primes[j]=0`时就需要`break`。 以上内容的严谨证明请参阅参考资料。 ## 实现 改进版埃氏筛： ```cpp // Created by Colin on 2020/05/17. // Copyright © 2020 Colin. All rights reserved. // https://blog.valderfield.com/archives/35/ #include <iostream> using namespace std; void E_sieve(const int N, bool* not_prime) { not_prime[0] = not_prime[1] = 1; for (int i = 2; i <= N; i++) { if (!not_prime[i]) { auto j = (long long)i * i; // j may exceed int !!! if (j <= N) for (; j <= N; j += i) not_prime[j] = 1; } } } int main() { bool not_prime[1000001] = { 0 }; int n; cin >> n; E_sieve(n, not_prime); for (int i = 2; i <= n; i++) { if (!not_prime[i]) cout << i << ' '; } cout << endl; return 0; } ``` 欧拉筛： ```cpp // Created by Colin on 2020/05/17. // Copyright © 2020 Colin. All rights reserved. // https://blog.valderfield.com/archives/35/ #include <iostream> #include <vector> using namespace std; void Euler_sieve(const int N, vector<int>& primes) { bool not_prime[1000001] = { 0 }; not_prime[0] = not_prime[1] = 1; for (int i = 2; i <= N; i++) { if (!not_prime[i]) primes.push_back(i); for (int j = 0; j < primes.size() && i * primes[j] <= N; j++) { not_prime[i * primes[j]] = 1; if (i % primes[j] == 0) // most important break; } } } int main() { int n; cin >> n; vector<int> primes; Euler_sieve(n, primes); for (auto x : primes) // supported by C++11 cout << x << ' '; cout << endl; return 0; } ``` -------------------- 参考资料： [关于求素数的思路（一般筛法到线性筛）](https://blog.csdn.net/liamleec/article/details/78524039) [OI Wiki - 筛法](https://oi-wiki.org/math/sieve/)（利益无关，友情安利。） [欧拉线性筛法求素数（顺便实现欧拉函数的求值）](https://blog.csdn.net/NK_test/article/details/46242401) [埃拉托色尼筛法的复杂度估计与改进 及线性时间筛法简介](https://www.cnblogs.com/dc93/p/3930362.html) Last modification：May 17, 2020 © Allow specification reprint Support Appreciate the author Like 0 如果觉得我的文章对你有用，请随意赞赏
2 comments
这个有问题吧..ola筛那边循环2会给1出掉 2作为最小的素数都筛不掉4了 望回复一下
你是说欧拉筛吗？我跑了一下程序感觉没问题？