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

zhangjinxuan

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

#include <bits/stdc++.h>
using namespace std;

bool prime(int n) {
        for (int i = 2; i < n; ++i) {
                if (n % i == 0) {
                        return 0;
                }
        }
        return 1;
}

int main() {
        int t, n;
        scanf("%d", &t);
        while (t--) {
                scanf("%d", &n);
                printf("%s\n", prime(n) ? "Yes" : "No");
        }
}

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

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

#include <bits/stdc++.h>
using namespace std;

bool prime(int n) {
        for (int i = 2; i * i <= n; ++i) {
                if (n % i == 0) {
                        return 0;
                }
        }
        return 1;
}

int main() {
        int t, n;
        scanf("%d", &t);
        while (t--) {
                scanf("%d", &n);
                printf("%s\n", prime(n) ? "Yes" : "No");
        }
}

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

第二类：筛法
1. 埃氏筛

#include <bits/stdc++.h>
using namespace std;

bool b[10000001];

void init() {
        b[1] = 1;
        for (int i = 2; i <= 10000000; ++i) {
                if (!b[i]) {
                        for (int j = i + i; j <= 10000000; j += i) {
                                b[j] = 1;
                        }
                }
        }
}

bool prime(int n) {
        return b[n] ? 0 : 1;
}

int main() {
        init();
        int t, n;
        scanf("%d", &t);
        while (t--) {
                scanf("%d", &n);
                printf("%s\n", prime(n) ? "Yes" : "No");
        }
}

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

#include <bits/stdc++.h>
using namespace std;

bool b[10000001];

void init() {
        b[1] = 1;
        for (int i = 2; i * i <= 10000000; ++i) {
                if (!b[i]) {
                        for (int j = i * i; j <= 10000000; j += i) {
                                b[j] = 1;
                        }
                }
        }
}

bool prime(int n) {
        return b[n] ? 0 : 1;
}

int main() {
        init();
        int t, n;
        scanf("%d", &t);
        while (t--) {
                scanf("%d", &n);
                printf("%s\n", prime(n) ? "Yes" : "No");
        }
}

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

#include <bits/stdc++.h>
using namespace std;

bool b[10000001];
int c[10000001], tot;

void init() {
        b[1] = 1;
        for (int i = 2; i <= 10000000; ++i) {
                if (!b[i]) c[++tot] = i;
                for (int j = 1; i * c[j] <= 10000000 && j <= tot; ++j) {
                        b[i * c[j]] = 1;
                        if (c[j] % i == 0) break;
                }
        }
}

bool prime(int n) {
        return b[n] ? 0 : 1;
}

int main() {
        init();
        int t, n;
        scanf("%d", &t);
        while (t--) {
                scanf("%d", &n);
                printf("%s\n", prime(n) ? "Yes" : "No");
        }
}

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

#include <bits/stdc++.h>
using namespace std;

bool b[10000001] = {0, 0, 1, 1, 0, 1, ...(省略约3千万字符) };

bool prime(int n) {
        return b[n];
}

int main() {
        init();
        int t, n;
        scanf("%d", &t);
        while (t--) {
                scanf("%d", &n);
                printf("%s\n", prime(n) ? "Yes" : "No");
        }
}

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

#include <bits/stdc++.h>
using namespace std;

bool prime(long long n) {
        if (n <= 1) return 0;
        if (n <= 3) return 1;
        if (n == 5) return 1;
        /*此处省略约1垓个字符*/
}

int main() {
        init();
        int t, n;
        scanf("%d", &t);
        while (t--) {
                scanf("%d", &n);
                printf("%s\n", prime(n) ? "Yes" : "No");
        }
}

这个更狠了……
时间复杂度：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 , 里面很多有用的容器和函数