一一般筛法|一一般筛法 + 埃式筛法 + 线性筛法
我们如何计算从1~n一共有多少个质数呢，我们就要考虑一种筛法，用已知的数把确定的那些不会是质数的数全部筛掉！
我们先介绍第一种一般筛法：
void get_primes2(){
for(int i=2;
i<=n;
i++){
if(!st[i]) primes[cnt++]=i;
//把素数存起来
for(int j=i;
j<=n;
j+=i){//不管是合数还是质数，都用来筛掉后面它的倍数
st[j]=true;
}
}
}
【一一般筛法|一一般筛法 + 埃式筛法 + 线性筛法】
分析：第一种筛法就是无论是合数还是质数都可以用来把后面那些不可能是质数的数给全部ban掉；
比较麻烦，所以时间复杂度是O(nlogn)
第二种筛法：埃式筛法
void get_primes1(){
for(int i=2;
i<=n;
i++){
if(!st[i]){
primes[cnt++]=i;
for(int j=i;
j<=n;
j+=i) st[j]=true;
//可以用质数就把所有的合数都筛掉；
}
}
}
分析：这个筛法是一位叫做Eratosthenes的人发明的筛法，不是因为这个发明的人是埃及人；
这个筛法的高明之处在于我们不再利用合数去筛掉别的数字了，因为合数本身就能被质数筛掉，所以这个合数去筛的那些数肯定会被质数提前筛掉，这样就少去了很多重复的过程；
时间复杂度是O(nloglogn),已经很快了，但是如果遇到10^7的数量级就会爆时间，所以就需要引出我们接下来的线性筛法！
第三种筛法：线性筛法
void get_primes(int n){
for(int i = 2;
i<=n;
i++){
if(!st[i]) primes[cnt++] = i;
for(int j = 0;
primes[j]<=n/i;
j++){
st[primes[j]*i] = true;
if(i%primes[j] == 0) break;
}
}
cout << cnt << '\n';
}
分析：这个方法好在哪儿呢，首先可以看到我们把所有的质数都放入到primes数组里面，我用的相当于是最小质因数去筛掉那些合数，当我们看到这里我们可以发现对应每个质数i时，primes数组递增，只可能是primes[j]^2，是因为primes[j]^2前面的数都已经被筛除干净了，最小的质因数就是primes[j]，比如10 = 2*5；我们使用2去筛掉的10，因为我用5去筛只能筛掉25，30，35，这些数字了，所以线性筛法的点在于用最小质因数筛，避免了质数重复筛；
时间复杂度是O(n)的，非常快！！！
推荐阅读
- 云计算起源（一个单词的演变，见证了一个时代的开端）
- 云计算演义(1)衣服再漂亮，总是要脱的（一个单词的演变，见证了一个时代的开端...）
- 贝佐斯（亚马逊是科技界唯一一家低利润公司）
- 操作系统|回顾2016年（我们见证了一场存储行业的厮杀）
- google|苹果和 Google 死磕专利（下一个目标 InterDigital）
- 《与 Rust 勾心斗角》·点
- 从零开始 实现一个自己的脚本引擎
- 项目开发|用node+WebSocket+MySQL+vue仿做学习通的一些功能（二）（主页的展示）
- #java|***********--＞JAVA50必刷题之第一题＜--***************
- 适合|适合 Kubernetes 初学者的一些实战练习 (四)