zhangjinxuan 发表于 2023-1-8 15:02:40

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

本帖最后由 zhangjinxuan 于 2023-1-9 14:28 编辑

第一类：枚举法
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;

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

bool prime(int n) {
        return b ? 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;

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

bool prime(int n) {
        return b ? 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;
int c, tot;

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

bool prime(int n) {
        return b ? 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 % i == 0) break; 这一句
时间复杂度：O(n)
空间复杂度：O(n)
优点：时间复杂度低，再也不会被卡掉了
缺点：空间复杂度较高，不适合初学者，对于数学功底极高
第三类：表法
1.
#include <bits/stdc++.h>
using namespace std;

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

bool prime(int n) {
        return b;
}

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 的存储空间

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

整理不易，喜欢别忘了评分{:10_254:}

zhangjinxuan 发表于 2023-1-8 15:06:38

@tommyyu @柿子饼同学 @高山 求支持{:10_254:}

tommyyu 发表于 2023-1-8 15:24:17

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

柿子饼同学 发表于 2023-1-8 18:18:50

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

我一般用 bitset

zhangjinxuan 发表于 2023-1-8 18:34:25

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

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

柿子饼同学 发表于 2023-1-8 20:08:58

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

?
自己去查查 bitset 是啥

zhangjinxuan 发表于 2023-1-8 21:35:14

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

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

柿子饼同学 发表于 2023-1-9 07:47:03

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

{:10_277:}
可以多看看 STL , 里面很多有用的容器和函数
页: [1]
查看完整版本: 【C++板块提升计划】求质数的 N 种方法【原创】