Loading... 素数筛是我最早接触的几个算法之一。今天忽然发现有点不会写它了，于是重新温习一下。 ##引言 素数判断应该是刚开始的时候接触的比较多的一个(最少我写了一堆有关素数的题目)。素数的定义很简单： 只要一个数只有两个因子，1和它本身，那么这个数就是一个素数。 但如何验证一个数是素数呢？我第一个想到的是小于它的每个数都去除一遍。那么…………好吧我的废话有点多，下面列举三个方法吧。 ##1. 暴力循环 计算机擅长的是什么？循环嘛。那就让它循环吧： ```cpp /***************************************************************** Function:暴力就完事了 Time complexities: O(N!) *****************************************************************/ bool IsPrime(int n) { if (n < 2) return false; for (int i = 2; i*i < n - 1; i++) { //上面这里我小小的优化了一下，复杂度还没那么高 if (n % i == 0) return false; } return true; } ``` 然后，再for循环逐个判断………… 再然后，一个大大的**TLE**摆在你面前。 ##2. 埃拉托斯特尼筛法 TLE总不能就不管了吧？我们来找[古希腊数学家埃拉托斯特尼](https://zh.wikipedia.org/wiki/%E5%9F%83%E6%8B%89%E6%89%98%E6%96%AF%E7%89%B9%E5%B0%BC)帮我们解决(其实这个名字我还是现场Google的，怎么记得住哦)。他提出了一种算法叫“埃拉托斯特尼筛法”。 ###原理： 这是一种简单且历史悠久的筛法，用来找出一定范围内所有的素数。 所使用的原理是从2开始，将每个素数的各个倍数，标记成合数。一个素数的各个倍数，是一个差为此素数本身的等差数列。此为这个筛法和试除法不同的关键之处，后者是以素数来测试每个待测数能否被整除。 > 简单来讲，素数的倍数一定不是素数。 ###代码实现 ```cpp /***************************************************************** Function:埃拉托斯特尼筛法 Time complexities: O(NloglogN) *****************************************************************/ #include <algorithm> using namespace std; const int maxn = 65535; bool prime[maxn]; void IsPrime() { fill(prime, prime + maxn, true); //将所有重置为真 prime[0] = prime[1] = 0; for (int i = 2; i < maxn; i++) { if (prime[i]) { //素数的倍数一定不是素数 for (int j = i << 1; j < maxn; j += i) prime[j] = false; } } return; } ``` 详细步骤？自己去[Wiki](https://zh.wikipedia.org/wiki/%E5%9F%83%E6%8B%89%E6%89%98%E6%96%AF%E7%89%B9%E5%B0%BC%E7%AD%9B%E6%B3%95)上看去。 ##3. 欧拉筛 什么？还是TLE？那就再精简一点吧。 我们发现，在埃，埃拉…………埃式素数筛中，有些数是被重复筛了。比如60，它首先被2筛了一遍，又被3筛了一遍，还要被5筛一遍。这样就浪费了很多时间。那怎么办呢？我们可以找欧拉筛。 ###思路 首先先明确一个条件： > 任何合数都能表示成一系列素数的积 (别问我为什么，自己去验证) 然后，对于一个数 n ： 1. 如果 n 是素数，那么它和比它小的素数的乘积一定不会被重复筛。 2. 如果 n 是合数，此时 n 可以表示成递增素数相乘 `n = p1 x p2 x …… x pn`, 其中`pi`都是素数（2<=i<=n）， pi<=pj ( i<=j ) 。这时候我们只需要在p1的时候筛掉这个数就好了。 > 总结下来就是：对于每个合数，都只由它最小的质因子筛掉。 ###代码 ```cpp /***************************************************************** Function:线性素数筛 Time complexities: O(N) *****************************************************************/ #include <algorithm> using namespace std; const int maxn = 65535; bool check[maxn]; int prime[maxn]; int cnt = 0; void IsPrime() { fill(check, check + maxn, true); check[0] = check[1] = false; for (int i = 2; i < maxn; i++) { if (check[i]) prime[cnt++] = i; for (int j = 0; j < cnt && i * prime[j] < maxn; j++) { check[i * prime[j]] = false; //判重。这一步是重点 if (i % j == 0) break; } } return; } ``` 就先到这里吧，我要去补作业了(捂脸)。还有一堆资料没整理呢………… 最后修改：2019 年 04 月 22 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏