[题] 筛质数 #质数（素数）

题目

AcWing 868. 筛质数

---

题解

方法一：朴素筛法 及其优化：埃氏筛

从2~n枚举 i,再从小到大枚举所有已知的质数 primes[j],筛掉合数 i*primes[j],遇到新的质数就入队==
枚举所有小于n的数i,将i的所有倍数筛掉。
筛完后剩下的数就是质数。

朴素做法
void get_primes(int n ){for(int i = 2; i <= n; i ++){if(!st[i])primes[cnt ++] = i;//如果是质数，入队for(int j = i + i; j <= n; j +=i)st[j] = 1;//删掉它的所有倍数}
}
时间分析：n/2 + n/3 +....+n/n = n log n（大概）

1. 朴素做法的优化:埃氏筛法。（此算法由一个埃及人发明，所以叫 埃氏筛法）
   原理：当i不是质数时，没必要筛掉它的倍数，因为它的吧倍数将会是其它质数的倍数。
2. 筛到N时，如果N没有被筛掉，就说在2~i-1中没有N的约数，所以N是质数。
   时间是O(n log n)约等于 O(n)（和O(n)一个级别）
   3.补充：质数定理：1~n当中有 n / logn 个质数

埃氏筛法
void get_primes(int n ){for(int i = 2; i <= n; i ++){if(!st[i]) {primes[cnt ++] = n;//没被筛掉，说明是质数for(int j = i + i; j <= n; j += i)//干掉它的所有倍数st[j] = 1;}	}
}
时间是O(n log log n)和O(n)一个级别

---

方法二：线性筛法求质数

原理 ：n只会被n的最小质因子筛掉
操作 ：
枚举i:(2~n)

1. i % primes[j] == 0
   => primes[j]一定是i的最小质因子.
   => primes[j]一定是primes[j] * i的最小质因子.
2. i % primes[j] != 0
   由于是从小到大枚举的质数，若此时还没枚举到i的任何一个质因子。
   说明primes[j]一定小于i的最小质因子。
   那么 primes[j] 也一定是primes[j] * i的最小质因子。
   这个操作可以保证枚举到i时，所有小于等于i的合数都一定会被筛掉。
   证明：对于任意一个合数x,假设primes[j]是x的最小质因数,i一定会在x之前枚举到x/primes[j],这时x就会被筛掉。
   举例：
   比如n=12时,x的最小质因数primes[j] = 2，
   那么i一定会在12之前枚举到n/primes[j] = 6,此时就会把2*6 = 12 = n筛掉。
   时间：数据范围在 10⁷以上的时候,线性筛法比埃氏筛法快一倍。

void get_primes(int n ){for(int i = 2; i <= n; i ++){//没被筛掉说明是质数,将这个新的质数加入primes里if(!st[i]) primes[cnt ++] = i;//从小到大枚举所有已知的质数 primes[j]for(int j = 0; primes[j] <= n / i; j ++){	//当质数大于n / i的时候break;//等价于 primes[j] * i <= n;也就是筛掉所有小于n的合数就可以了//筛掉合数 i*primes[j]st[primes[j] * i] = 1;	//当这句话发生的时候,primes[j]一定是i的最小质因子//那么用i的最小质因子筛掉i的目的已经达成了,所以跳出循环.if(i % primes[j] == 0) break;}}
}

---

代码

#include<bits/stdc++.h>
using namespace std;const int N = 1000010;int primes[N], cnt;
bool st[N];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] = 1;if(i % primes[j] == 0) break;}}
}int main(){int n;cin >> n;get_primes(n);cout << cnt << endl;return 0;
}