关于素数（欧拉筛）（更新至洲阁筛和min_25筛）
King_and_Grey
·
2024-06-15 18:16:27
·
算法·理论
配套学习题单
关于质数
质数又称素数。
一个大于 1 的自然数，除了 1 和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定 1 既不是质数也不是合数）。
质数的个数是无穷的。
判断素数
根据上述第 2 点，我们可以遍历 2 \sim \text{数字本身} - 1,只要数字本身被其中一个数整除了，那就说明那个数是合数。
Code:
bool isPrime(int x){
if(x == 1){
return false;
}
for(int i = 2;i < x;i++){
if(x % i == 0){
return false;
}
}
return true;
}
学习完此部分，请去完成下面的例题：
B2132 素数对
B2128 素数个数
B3840 [GESP202306 二级] 找素数
优化
虽然我们已经可以判断素数了，但是代码效率太低，遇到超大的数据会超时，所以我们需要优化。
其实我们在寻找数字还有没有其他因子时，只要遍历到sqrt(n),因为当一个数不是质数时，必定存在两个约数，一个大于等于sqrt(n)，另一个小于等于sqrt(n)。（想一想，为什么）
Code(优化过):
bool isPrime(int x){
if(x == 1){
return false;
}
for(int i = 2;i < sqrt(x);i++){
if(x % i == 0){
return false;
}
}
return true;
}
再次优化
这次的优化，在这篇文章给过，这次附上详细的注释讲解
bool isPrime(int x) {
if (x == 2 || x == 3) { //将两个小数额外处理
return true;
}
if (x % 6 != 1 && x % 6 != 5) { //余数不是1和5的一定不是质数
return false;
}
//余数是1和5的数也不一定是质数
//还是要跑循环，但这次我们是 i+=6 ，不再是单纯无脑的i++了
//这也是速度提升的关键
//如果一个数不能整除比它小的任何质数，那么这个数就是质数
int tmp = sqrt(x);
for (int i = 5;i <= tmp;i += 6) {
//i可以表示为6a+5,i+2可以表示为6b+1
if (x % i == 0 || x % (i + 2) == 0) {
return false;
}
}
//排除所有剩余的是质数数
return true;
}
筛
埃氏筛
众所周知，一个质数的倍数一定是合数。
所以假如我吗遍历到了一个质数，（设这个质数为 p）就把区间 [1,n] 中所有 p 的倍数筛去。
至于为什么这样能筛去所有的合数呢，因为一个合数一定能被分解为几个质数的幂的乘积，并且这个数的质因子一定是小于它本身的，所以当我们从小到大将每个质数的倍数都筛去的话，当遍历到一个合数时，它一定已经被它的质因子给筛去了。
让我们进一步的优化：
我们会先筛 2 的所有倍数，然后筛 3 的所有倍数，但筛除 3 的倍数时，我们还是从 3 的 2 倍开始筛，其实 3 \times 2 ，已经被 2 \times 3时筛过了。又比如说筛 5 的倍数时，我们从 5 的 2 倍开始筛，但是 5 \times 2会先被 2 \times 5 筛去, 5 \times 3会先被 3 \times 5 会筛去，5 \times 4会先被 2 \times 10 筛去，所以我们每一次只需要从 i^2开始筛，因为(2，3,…,i - 1)倍已经被筛过了。
另外，判断一个数 n 是不是质数，我们只判断 [2, \sqrt{n} ]内有没有它的因子。在筛合数的时候，我们也可以这样做，因为一个合数的最小质因子一定小于等\sqrt{n} 。所以对于区间[1,1e7]，最大的合数是1e7, 它的最小质因子一定是小于等于\sqrt{1e7}，区间内其他的合数的最小质因子也一定是小于等于 \sqrt{1e7}的，所以只需要用 [1, \sqrt{1e7}] 中的质数就可以筛去[1, 1e7]中所有的合数。
Code(优化后的埃氏筛):
bool isPrime[100000005];
bool is_prime(int n){
isPrime[1] = 1;
for(int i = 2;i <= n / i;i++){
if(isPrime[i] == 0) {
for(int j = i * i;j <= n;j += i){
isPrime[j] = 1;
}
}
}
}
时间复杂度近似 O(n)。
如果你还想要更快，请继续往下学习欧拉筛（线性筛）。
欧拉筛（线性筛）
大体思路我感觉和埃氏筛差不多，自己上代码吧！（有注释）
const int MAXN = 1e7 + 5;
bool isprime[MAXN]; // isprime[i]表示i是不是素数
int prime[MAXN]; // 现在已经筛出的素数列表
int n; // 上限，即筛出<=n的素数
int cnt; // 已经筛出的素数个数
void euler(){
memset(isprime, true, sizeof(isprime)); // 先全部标记为素数
isprime[1] = false; // 1不是素数
for(int i = 2; i <= n; ++i) // i从2循环到n（外层循环）
{
if(isprime[i]) prime[++cnt] = i;
// 如果i没有被前面的数筛掉，则i是素数
for(int j = 1; j <= cnt && i * prime[j] <= n; ++j)
// 筛掉i的素数倍，即i的prime[j]倍
// j循环枚举现在已经筛出的素数（内层循环）
{
isprime[i * prime[j]] = false;
// 倍数标记为合数，也就是i用prime[j]把i * prime[j]筛掉了
if(i % prime[j] == 0) break;
// 最神奇的一句话，如果i整除prime[j]，退出循环
// 这样可以保证线性的时间复杂度
//就是取模时间较大，数据小时不建议用线性筛，埃氏筛可能会更快
}
}
}
洲阁筛
草草草，世界上竟然还有比欧拉筛还快的筛法，蒟蒻于是立刻就学了。
接下来的内容可能很难，请谨慎阅读（例题讲解除外）
我学习的原文。
洲阁筛和min_25功能基本相同，但是跑的没 min_25 筛（min_25筛更难）快。
只不过能求出所有 \lfloor \frac{n}{i} \rfloor的前缀和的值。
First
Q:求1 \sim n 中质数的个数。
我们先设 f(n,m) 表示 2 \sim n中所有的质数或者不含最小质因子 p_1,p_2 \dots p_m （就是质因子大于 p_m 的数）的数的个数。
那么有：
f(n,m) = f(n,m - 1) + (f(\lfloor \frac{n}{p_m} \rfloor,m - 1) - (m - 1))
就是f(n,m)是由f(n,m - 1)转移过来的，那么我们只要把所有要筛数提出p_m，剩下的数最小质因子就为p_m,p_{m+1},p_{m+2}, \dots。注意删掉“质数"部分。
注意，我们并不想筛掉 p_m，但是注意到 f 是不包括 1的，所以后面的部分并没有把 1筛掉，符合要求。
注：接下来用 F(n) 代替了积性函数;psum 为预处理出来的质数函数前缀和。
由于是多项式，我们可以拆成 F(p) = p ^ k的形式，最终拼起来。这样，假函数成为完全积性函数，直接提出来F(p_m)就是对的了。
Second
状态不太一样，有点像 first 中的那个 f 数组。
定义 g(n,m) 表示 2 \sim n 中质数或最小质因子大于 p_m 的所有数的真的积性函数和。那么有：
g(n,m - 1) = g(n,m) + \sum_cF(p^c_m)(g(\lfloor \frac{n}{p^c_m} \rfloor,m) - psum(m)) + [c > 1])
意义为：
对于不包含 p_m 的那部分，直接从 g(n,m) 那里转移过来；对于包含 p_m 的那部分，枚举指数 c，如果形如 p^c_m，那么答案就是 F(p^c_m)；否则还会有若干比 p_m 大的质因子，答案为 F(p^c_m)(g(\lfloor \frac{n}{p^c_m} \rfloor,m)−psum(m))。
注意到当 p^2_m > n 的时候 g(n,m)=f(n,m)，于是将 g初始化设为 f，按照 m 从大到小递推即可。最终答案为 g(n,0)。好处是推完后我们得到的是一个数组，包含了所有 g(\lfloor \frac{n}{i} \rfloor,0)，于是再求
\lfloor \frac{n}{i} \rfloor
的时候就不用重新求了。
代码实现:
g(n,m - 1) = g(n,m) + \sum{_c}F(p^c_m)(g(\lfloor \frac{n}{p^c_m} \rfloor,m) - psum(m)) + F(p_m^c + 1)
主要是为了方便减少枚举上界。
复杂度
不知道，大家说还是 O(n^{0.75}/ ln n) 的，但是多枚举个 c 应该会增大复杂度。但是可以证明复杂度是不超过 O(n^{0.75})的。
代码在马上讲例题时给。
代码可能有误：
#define int long long
const int N = 1e10 + 5;
void init(const int up)
inline int Id(int x) {
return x <= S ? x : tot - n / x + 1;
}
int r[N], tot, g[N];
inline int calc(int k) {
return 3 * k + 1;
}
inline void work() {
cin >> n;
S = sqrt(n);
init(S + 200);
for (int l = 1; l <= n; l = r[tot] + 1)
r[++tot] = n / (n / l), g[tot] = r[tot] - 1;
int ptr = 1;
for (int j = 1; pri[j] * pri[j] <= n; ++j) {
while (pri[j] * pri[j] > r[ptr]) ++ptr;
for (int i = tot; i >= ptr; --i) {
g[i] -= g[Id(r[i] / pri[j])] - j + 1;
}
}
for (int i = 1; i <= tot; ++i) g[i] *= 4;
ptr = tot + 1;
for (int j = pcnt; j; --j) {
while (pri[j] * pri[j] <= r[ptr - 1]) --ptr;
for (int i = tot; i >= ptr; --i) {
int nw = pri[j], nww = nw * nw;
for (int c = 1; nww <= r[i]; ++c, nw = nww, nww *= pri[j]) {
g[i] += calc(c) * (g[Id(r[i] / nw)] - 4 * j) + calc(c + 1);
}
}
}
int res = g[tot] + 1;
cout << res << endl;
}
min_25筛
只要你完全学会了楼阁筛，其实min_25筛也没有那么难啦~
可惜我们可能连楼阁筛都学不会
First
和楼阁筛 筛完全一致，直接把 f(n,m) 拿过来即可。
Second
我们设 g(n,m) 表示 1 \sim n 中最小质因子大于 p_m 的数的（真）积性函数和。
那么有：
g(n,m)=f(n,\infty) − psum(m) + \sum_{p^e_k} F(p^e_k)g(\lfloor \frac{n}{p^e} \rfloor,k) + [e \neq 1])
意义为：分质数，合数考虑贡献。质数的贡献我们已经搞好了，为 f(n,\infty) − psum(m)，合数的话我们需要枚举最小质因子及其次数，即枚举 k > m 的 p_k，再枚举次数 e。由于是积性函数，我们可以直接将 F(p^e_k) 提出来。值得注意的是，形如 p_k,k > 1 的数我们既没有在质数处枚举到，也没有在合数处提出来 p^e_k 后枚举到，所以需要加上个 [e\neq1]。
复杂度：不会证。状态数和上面一样是O(n^{0.75}/\log{n}) 的，但是转移复杂度比较玄学，据说总复杂度是O(n^{0.75}/ \log{n}) 的，也有的说是 O(n^{1− \epsilon})的。
代码可能有误：
#include
using namespace std;
#define int long long
const int N = 1e10 + 5;
int block, itot, pos[N];
ull id[N], n, K, f[N];
inline int get_id(ull x) {
return pos[x <= block ? x : block + n / x];
}
inline void get_f() {
for (ull l = 1, r; l <= n; l = r + 1) {
ull zhi = n / l;
r = n / zhi;
id[++itot] = zhi;
pos[zhi <= block ? zhi : block + n / zhi] = itot;
f[itot] = zhi - 1;
}
for (int j = 1; 1ull * pri[j] * pri[j] <= n; ++j) {
for (int i = 1; id[i] >= 1ull * pri[j] * pri[j]; ++i) {
f[i] = f[i] - f[get_id(id[i] / pri[j])] + j - 1;
}
}
}
ull get_g(ull n, int j) {
if (pri[j] >= n) return 0;
ull res = (f[get_id(n)] - j) * (K + 1);//bug
for (int k = j + 1; 1ull * pri[k] * pri[k] <= n; ++k) {
ull tmp = pri[k];
for (int e = 1; tmp <= n; ++e, tmp = tmp * pri[k]) {
res += (K * e + 1) * (get_g(n / tmp, k) + (e > 1));
}
}
return res;
}
inline void work() {
read(n), read(K); block = sqrt(n);//bug
get_f();
ull res = get_g(n, 0) + 1;
printf("%llu\n", res);
}
例题讲解
（题目在文章最上面的配套题单里面）
B2132 素数对
这一题我们可以直接用文章最开始介绍的判断素数代码，没有必要用筛去做，从 1 遍历到 n - 2,如果 i 和 i + 2 都是素数，就直接输出，ans 加 1,最后如果 ans 等于 0的话,就输出empty。
Code:
#include
using namespace std;
#define int long long
bool isPrime(int x) {
if(x == 1){
return false;
}
if (x == 2 || x == 3 || x == 5 || x == 7) {
return true;
}
if (x % 6 != 1 && x % 6 != 5) {
return false;
}
int tmp = sqrt(x);
for (int i = 5; i <= tmp; i += 6) {
if (x % i == 0 || x % (i + 2) == 0) {
return false;
}
}
return true;
}
int n,ans;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n;
for(int i = 1; i <= n - 2; i++){
if(isPrime(i) == true && isPrime(i + 2) == true){
cout << i << " " << i + 2 << endl;
ans++;
}
}
if(ans == 0){
cout << "empty" << endl;
}
return 0;
}
B3939 [GESP样题 四级] 绝对素数
这一题数据水，10 < A < B < 100。
所以翻转数字可以用i % 10 * 10 + i / 10的方法。
Code:
#include
using namespace std;
#define int long long
bool isPrime(int x) {
if(x == 1){
return false;
}
if (x == 2 || x == 3 || x == 5 || x == 7) {
return true;
}
if (x % 6 != 1 && x % 6 != 5) {
return false;
}
int tmp = sqrt(x);
for (int i = 5; i <= tmp; i += 6) {
if (x % i == 0 || x % (i + 2) == 0) {
return false;
}
}
return true;
}
int a,b;
signed main(){
cin >> a >> b;
for(int i = a;i <= b;i++){
if(isPrime(i)){
if(isPrime(i % 10 * 10 + i / 10)){
cout << i << endl;
}
}
}
return 0;
}
P3912 素数个数
这一题就不能用文章开头讲的质数判断了，要用线性筛。
Code:
#include
using namespace std;
#define int long long
bool isPrime[100000005];
int n,ans;
signed main (){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n;
isPrime[1] = 1;
for(int i = 2;i * i <= n;i++){
if(isPrime[i] == 0) {
for(int j = i * i;j <= n;j += i){
isPrime[j] = 1;
}
}
}
for(int i = 1;i <= n;i++){
if(isPrime[i] == 0) {
ans++;
}
}
cout << ans << endl;
return 0;
}
P2092 数字游戏
这一题有些难度，我讲详细些。
具体思路：
假如这个数是一个素数，就直接升天输出。
如果这个数可以分成两个素数相乘，那么自己一定会升天输
若这个数比较复杂，可以分解成多个数，那么就输出最小的两个质因数的乘积。（因为文中要求输入第一次写出的可以制胜的最小数字）
大家都用queue，我~偏~不~。
Code:
#include
using namespace std;
#define int long long
int q,a[1000005];//存储质因数
int fun(int x){
int cnt = 0;//质因数的个数
for(int i = 2;i <= sqrt(x);i++){
while(x % i == 0){
a[++cnt] = i;
x /= i;
}
}
if(x > 1){//如果x大于1，说明现在它本身也是一个质数，也要存进来
a[++cnt] = x;
}
return cnt;
}
signed main(){
cin >> q;
if(fun(q) >= 3){//输出他最小的两个质因子的乘积
cout << "1\n" << a[1] * a[2] << endl;
}else if(fun(q) == 1){//是质数，自己升天
cout << "1\n0\n";
}else{//自己升天
cout << "2\n";
}
return 0;//bye~bye~
}
QwQ,点个赞再走呗~