质数"/>

筛法求质数

文章目录

• 例题
• 求质数
• • Q1
  • Q2

例题

LGOJ P3383 【模板】线性筛素数
LGOJ P1865 A % B Problem

求质数

下面我们来讲解如何求质数

Q1

我们如何判断一个数 k k k是否为质数呢？
可以采用试除法

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

时间复杂度 O ( n ) O(n) O(n)

优化?
我们发现，若 [ 2 , n ] [2,\sqrt n] [2,n ​]以内的所有数都无法整除 n n n，那么 [ n + 1 , n − 1 ] [\sqrt n+1,n-1] [n ​+1,n−1]以内的所有数也自然无法整除 n n n，故可以优化：

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

时间复杂度 O ( n ) O(\sqrt n) O(n ​)

另外，如果我们预处理出了 n \sqrt n n ​内的质数表，只试除质数，时间复杂度将会变为 O ( n l o g 2 n ) O(\frac{\sqrt n}{log_2n}) O(log2​nn ​​)

还有一种比较高效的判断大质数的算法:Miller-Rabin算法，大家可百度自行学习

Q2

我们如何求 n n n以内的所有质数呢？
方法1：对 n n n以内的所有质数进行试除，时间复杂度 O ( n n l o g 2 n ) O(n\frac {\sqrt n} {log_2n}) O(nlog2​nn ​​)，太过低效
方法2：埃氏筛法，时间复杂度 O ( n l o g l o g n ) O(nloglogn) O(nloglogn)
代码大概长这样（由于小学老师都会讲，在此不赘述）

void pr() {ispr[1]=false;for(int i=2;i*i<=N;i++)if(ispr[i]) {for(int j=2;i*j<=N;j++) {ispr[i*j]=false;}}
}

时间复杂度的论证不太好做，大家可以自行网上找（滑稽）
方法3：欧拉线性筛：
时间复杂度 O ( n ) O(n) O(n)
其实和埃氏筛法的 O ( n l o g l o g n ) O(nloglogn) O(nloglogn)没差多少
它解决了埃氏筛法重复筛合数的问题。
上代码

void getpr()
{memset(ispr, true, sizeof ispr);ispr[1] = false;for(rg int i = 2; i < MAXN; i++){if(ispr[i]) pr[++cnt] = i;for(rg int j = 1; j <= cnt && i * pr[j] < MAXN; j++){ispr[i * pr[j]] = false;if(i % pr[j] == 0) break;}}
}

为什么呢？
任何一个合数都可以表示成一个质数和一个数的乘积

设当前判断的数 A A A是一个合数，且 A = x y A=xy A=xy，其中 x x x也是一个合数
则可设
x = a b x = ab x=ab (假设 a a a是质数，有 a &lt; x a &lt; x a<x)
故可得 A = x y = a b y = a Z A=xy=aby=aZ A=xy=aby=aZ (其中 Z = b y Z=by Z=by是个比 x x x更大的合数)

即一个合数( x x x)与一个质数( y y y)的乘积可以表示成一个更大的合数( Z Z Z)与一个更小的质数( a a a)的乘积，那样我们到每一个数，都处理一次，这样处理的次数是很少的，因此可以在线性时间内得到解。
（上述证明摘抄自dormantbs 的博客洛谷博客）