【C++板块提升计划】求质数的 N 种方法【原创】

zhangjinxuan

第一类：枚举法
1. 暴力枚举因数

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. bool prime(int n) {
   
5.         for (int i = 2; i < n; ++i) {
   
6.                 if (n % i == 0) {
   
7.                         return 0;
   
8.                 }
   
9.         }
   
10.         return 1;
    
11. }
    
12. 
    
13. int main() {
    
14.         int t, n;
    
15.         scanf("%d", &t);
    
16.         while (t--) {
    
17.                 scanf("%d", &n);
    
18.                 printf("%s\n", prime(n) ? "Yes" : "No");
    
19.         }
    
20. }

复制代码

通过枚举因数的方式找到质数
时间复杂度：O(n)
空间复杂度：O(1)
优点：适合初学者，空间复杂度小
缺点：时间复杂度高

2. 暴力枚举因数（优化版）

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. bool prime(int n) {
   
5.         for (int i = 2; i * i <= n; ++i) {
   
6.                 if (n % i == 0) {
   
7.                         return 0;
   
8.                 }
   
9.         }
   
10.         return 1;
    
11. }
    
12. 
    
13. int main() {
    
14.         int t, n;
    
15.         scanf("%d", &t);
    
16.         while (t--) {
    
17.                 scanf("%d", &n);
    
18.                 printf("%s\n", prime(n) ? "Yes" : "No");
    
19.         }
    
20. }

复制代码

进行了优化，我们只用枚举到 n ^ 0.5
时间复杂度：O(sqrt(n))
空间复杂度：O(1)
优点：适合初学者，空间复杂度小，可以解决大部分问题了
缺点：时间复杂度还是高，需要一点数学功底

第二类：筛法
1. 埃氏筛

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. bool b[10000001];
   
5. 
   
6. void init() {
   
7.         b[1] = 1;
   
8.         for (int i = 2; i <= 10000000; ++i) {
   
9.                 if (!b[i]) {
   
10.                         for (int j = i + i; j <= 10000000; j += i) {
    
11.                                 b[j] = 1;
    
12.                         }
    
13.                 }
    
14.         }
    
15. }
    
16. 
    
17. bool prime(int n) {
    
18.         return b[n] ? 0 : 1;
    
19. }
    
20. 
    
21. int main() {
    
22.         init();
    
23.         int t, n;
    
24.         scanf("%d", &t);
    
25.         while (t--) {
    
26.                 scanf("%d", &n);
    
27.                 printf("%s\n", prime(n) ? "Yes" : "No");
    
28.         }
    
29. }

复制代码

筛法求素数，一开始就把素数筛出来，后面查询就很简单了，属于”一劳永逸“
时间复杂度：O(n log log n)
空间复杂度：O(n)
优点：时间复杂度低，可以满足大部分需求
缺点：不适合初学者，而且还容易被数据卡掉
2. 埃氏筛（优化版）

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. bool b[10000001];
   
5. 
   
6. void init() {
   
7.         b[1] = 1;
   
8.         for (int i = 2; i * i <= 10000000; ++i) {
   
9.                 if (!b[i]) {
   
10.                         for (int j = i * i; j <= 10000000; j += i) {
    
11.                                 b[j] = 1;
    
12.                         }
    
13.                 }
    
14.         }
    
15. }
    
16. 
    
17. bool prime(int n) {
    
18.         return b[n] ? 0 : 1;
    
19. }
    
20. 
    
21. int main() {
    
22.         init();
    
23.         int t, n;
    
24.         scanf("%d", &t);
    
25.         while (t--) {
    
26.                 scanf("%d", &n);
    
27.                 printf("%s\n", prime(n) ? "Yes" : "No");
    
28.         }
    
29. }

复制代码

进行了优化，一是 i 只要枚举到 sqrt(10000000)，二是 j 可以从 i * i 开始枚举，这就是标准的埃氏筛了
时间复杂度：O(n log log n)
空间复杂度：O(n)
优点：时间复杂度低，可以满足大部分需求
缺点：不适合初学者，对于数学功底较高，还是容易被数据卡掉
3. 线性筛

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. bool b[10000001];
   
5. int c[10000001], tot;
   
6. 
   
7. void init() {
   
8.         b[1] = 1;
   
9.         for (int i = 2; i <= 10000000; ++i) {
   
10.                 if (!b[i]) c[++tot] = i;
    
11.                 for (int j = 1; i * c[j] <= 10000000 && j <= tot; ++j) {
    
12.                         b[i * c[j]] = 1;
    
13.                         if (c[j] % i == 0) break;
    
14.                 }
    
15.         }
    
16. }
    
17. 
    
18. bool prime(int n) {
    
19.         return b[n] ? 0 : 1;
    
20. }
    
21. 
    
22. int main() {
    
23.         init();
    
24.         int t, n;
    
25.         scanf("%d", &t);
    
26.         while (t--) {
    
27.                 scanf("%d", &n);
    
28.                 printf("%s\n", prime(n) ? "Yes" : "No");
    
29.         }
    
30. }

复制代码

线性筛，线性筛，也就是它的时间复杂度是线性的，要知道，线性筛的灵魂就在于 if (c[j] % i == 0) break; 这一句
时间复杂度：O(n)
空间复杂度：O(n)
优点：时间复杂度低，再也不会被卡掉了
缺点：空间复杂度较高，不适合初学者，对于数学功底极高
第三类：表法
1.

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. bool b[10000001] = {0, 0, 1, 1, 0, 1, ...(省略约3千万字符) };
   
5. 
   
6. bool prime(int n) {
   
7.         return b[n];
   
8. }
   
9. 
   
10. int main() {
    
11.         init();
    
12.         int t, n;
    
13.         scanf("%d", &t);
    
14.         while (t--) {
    
15.                 scanf("%d", &n);
    
16.                 printf("%s\n", prime(n) ? "Yes" : "No");
    
17.         }
    
18. }

复制代码

打表，这个不言而喻，管你O(nloglogn),管你O(n)，都比不过我的表！
时间复杂度：O(1)
空间复杂度：O(n)
优点：时间复杂度低，简单易懂，适合萌新
缺点：代码长，希望大家永远别写
2.

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. bool prime(long long n) {
   
5.         if (n <= 1) return 0;
   
6.         if (n <= 3) return 1;
   
7.         if (n == 5) return 1;
   
8.         /*此处省略约1垓个字符*/
   
9. }
   
10. 
    
11. int main() {
    
12.         init();
    
13.         int t, n;
    
14.         scanf("%d", &t);
    
15.         while (t--) {
    
16.                 scanf("%d", &n);
    
17.                 printf("%s\n", prime(n) ? "Yes" : "No");
    
18.         }
    
19. }

复制代码

这个更狠了……
时间复杂度：O(1)
空间复杂度：O(1)
优点：时间复杂度低，空间复杂度低，支持 long long，简单易懂，适合萌新和肝帝
缺点：保存这个代码需要 86EB 的存储空间

你还可以想到什么方法呢？欢迎回帖~

整理不易，喜欢别忘了评分

zhangjinxuan

@tommyyu @柿子饼同学 @高山 求支持

tommyyu

我有一个时间复杂度和空间复杂度都是O(1)的方法，但是代码有点长

柿子饼同学

zhangjinxuan 发表于 2023-1-8 15:06
@tommyyu @柿子饼同学 @高山 求支持

我一般用 bitset

zhangjinxuan

柿子饼同学 发表于 2023-1-8 18:18
我一般用 bitset

要是多次询问就废了，而且long long好像也不行，试试 (1e9+7) * (1e9+7)?

柿子饼同学

zhangjinxuan 发表于 2023-1-8 18:34
要是多次询问就废了，而且long long好像也不行，试试 (1e9+7) * (1e9+7)?

?
自己去查查 bitset 是啥

zhangjinxuan

柿子饼同学 发表于 2023-1-8 20:08
?
自己去查查 bitset 是啥

我只知道它比正常变量快32倍，啊，我语法都没学完

柿子饼同学

zhangjinxuan 发表于 2023-1-8 21:35
我只知道它比正常变量快32倍，啊，我语法都没学完

可以多看看 STL , 里面很多有用的容器和函数