筛质数的核心思想：
先把所有数放进一个数组
然后从前往后看，把每一个数的倍数删掉
第一个数是2，就把所有2的倍数删掉，4，6，8，10，12
第二个数是3，就把所有3的倍数删掉，6，9，12
第二个数是4，就把所有4的倍数删掉，8，12
第二个数是5，就把所有5的倍数删掉，10
以此类推
这样筛完之后，所有剩下的数就是质数
证明：对于任何一个数p而言，如果p没有被删掉的话，就意味着从2到p - 1中的任何一个数，都没有把p删掉
说明p不是2到p - 1中间任何一个数的倍数，也即2到p - 1中间不存在p的约数，所以p是一个质数
质数定理：1 ~ n中，有n / ln (n)个质数
线性筛：
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N = 1000010; 4 int primes[N], cnt; 5 bool st[N]; 6 void get_primes_1(int n) { 7 //朴素筛法，时间复杂度近似O(n log n) 8 for (int i = 2; i <= n; i++) { //从2到n枚举 9 if (!st[i]) { //如果这个数没有被筛过的话,说明是一个质数 10 primes[cnt++] = i; 11 } 12 //再把每一个数的倍数删掉 13 for (int j = i + i; j <= n; j += i) { //最朴素方法 14 st[j] = true; 15 } 16 } 17 } 18 void get_primes_2(int n) { 19 //埃氏筛法，时间复杂度O(n log log n),近似O(n) 20 for (int i = 2; i <= n; i++) { //从2到n枚举 21 if (!st[i]) { //如果这个数没有被筛过的话,说明是一个质数 22 primes[cnt++] = i; 23 for (int j = i + i; j <= n; j += i) { //最朴素方法 24 st[j] = true; 25 } 26 } 27 //并不需要把每一个数的倍数删掉，只把所有质数的倍数删掉就可以了 28 //可以把循环放进判断里面去 29 } 30 } 31 void get_primes_3(int n) { 32 //线性筛法的基本思路也是一样的：争取把每个合数，用它的某一个质因子筛掉 33 /* 34 线性筛法的核心思路：每一个合数，只会被它的最小质因子筛掉 35 */ 36 //线性筛法，时间复杂度O(n) 37 for (int i = 2; i <= n; i++) { //从2到n枚举 38 if (!st[i]) { //如果是一个质数的话 39 primes[cnt++] = i; //加进去 40 } 41 //从小到大枚举所有质数 42 for (int j = 0; primes[j] <= n / i; j++) { 43 st[primes[j] * i] = true; 44 if (i % primes[j] == 0) { //当这句话成立时，就意味着primes[j]一定是i的最小质因子 45 break; 46 } 47 } 48 } 49 } 50 /* 51 当n = 1e6时，埃氏筛法和线性筛法运行时间差不多 52 当n = 1e7时，线性筛法比埃氏筛法快一倍 53 */ 54 int main() { 55 int n; 56 cin >> n; 57 get_primes_3(n); 58 cout << cnt << endl; 59 return 0; 60 }
2020年8月2日复习更新，果然复习之后之前不明白的地方就容易明白了
线性筛法里，42行primes[j] <= n / i，是primes[j] * i <= n的变形，防止越界
然后把primes[j] * i筛掉
然后我终于看明白别人的题解了
1 void get_primes(){ 2 3 for(int i=2;i<=n;i++){ 4 if(!st[i]) primes[cnt++]=i; 5 for(int j=0;primes[j]<=n/i;j++){//primes[j]<=n/i:变形一下得到——primes[j]*i<=n,把大于n的合数都筛了就没啥意义了 6 7 st[primes[j]*i]=true;//用最小质因子去筛合数,一定有pj是pj * i的最小质因子 8 9 //1)当i%primes[j]!=0时,说明此时遍历到的primes[j]不是i的质因子，那么只可能是此时的primes[j]<i的 10 //最小质因子,所以primes[j]*i的最小质因子就是primes[j]; 11 //2)当有i%primes[j]==0时,说明i的最小质因子是primes[j],因此primes[j]*i的最小质因子也就应该是 12 //prime[j]，之后接着用st[primes[j+1]*i]=true去筛合数时，就不是用最小质因子去更新了,因为i有最小 13 //质因子primes[j]<primes[j+1],此时的primes[j+1]不是primes[j+1]*i的最小质因子，此时就应该 14 //退出循环，避免之后重复进行筛选。 15 if(i%primes[j]==0) break; 16 } 17 } 18 19 } 20 21 作者：orzorz 22 链接：https://www.acwing.com/solution/content/7950/ 23 来源：AcWing 24 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。