3.筛质数 质数

 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 }