质数
定义
设整数\(p\ne0,\pm1\)。如果 p除了平凡约数外没有其他约数，那么称p 为 素数（不可约数)。
若整数 \(a\ne0,\pm1\)。且 a不是素数，则称a为 合数。
若整数的因数是素数，则该素数称为该整数的素因数
性质
大于 1 的整数 a是合数，等价于存在整数 (d,e)（(1<d,e<a)）使得
\[ a \;=\; d \times e. \]若素数 p有大于 1 的约数 (d)，则 \(d \;=\; p.\)（即素数只有 1 和它自身为约数）
任意大于 1 的整数 a都可以表示为素数的乘积：
\[ a \;=\; p_1 p_2 \cdots p_k. \]对于合数 a，一定存在素数 \(p \le \sqrt{a}\)使得 \(p \mid a.\)
素数有无穷多个。
所有大于 3 的素数都可以表示为
\[ 6n \pm 1,\quad n\in\mathbb{Z}. \]
判断质数
较小数据范围
从第一个质数2开始验证，一个个验证待测数n是否能被每个数整除，若任何一个可以整除n，则不是质数
注意，只需要验证到\(\sqrt{n}\)即可
因为若一个数x已经验证无法整除n，则对应的\(\frac{n}{x}\)之后的数无需验证，因为此时这之后的因子与x相乘的结果一定大于n，一直到\(\sqrt{n}\)，\(\frac{n}{\sqrt{n}}=\sqrt{n}\)，故该后面的都不需要验证
1
2
3
4
5
6
7
bool isPrime(long long n){
if(n<=1) return false;
for(long long i = 2; i*i<=n;i++){
if(n%i==0) return false;
}
return true;
}较大数据范围
对于较大的数字，可以使用Miller-Rabin测试
过程：
- 每次选择1~n-1上的随机数字，或者指定一个比n小的质数进行测试
- 经s次（一般20次以内）得到，s越出错概率越低，速度越慢
对于Java用户，其BigInteger类型内自带了一个判断质数的方法isProbablePrime(s)，使用的测试方法就包含了Miller-Rabin测试，对于大于1e9的数据也不会出现溢出
对于CPP用户，需要使用__int128
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef __int128 ll;
typedef pair<int,int> PII;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
ll n;
template<typename T> inline T read() {
T x = 0, f = 1; char ch = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch - '0');
return x * f;
}
template<typename T> inline void write(T x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
ll qpow(ll a, ll n, ll mod){
ll re = 1;
while(n){
if(n&1) re = (re*a)%mod;
a = (a*a)%mod;
n>>=1;
}
return re%mod;
}
vector<ll> p ={2,3,5,7,11,13,17,19,23,29,31,37};
bool miller_rabin(ll n){
if(n<3||n%2==0) return n==2;
ll u = n-1, t = 0;
while(u%2==0) u/=2, t++;
for(auto a:p){
if(n==a) return 1;
if(n%a==0) return 0;
ll v = qpow(a, u, n);
if (v==1) continue;
ll s = 1;
for(; s<=t;s++){
if(v==n-1) break;
v = (v*v)%n;
}
if(s>t) return 0;
}
return 1;
}
void solve() {
n = read<ll>();
if(miller_rabin(n)) puts("Yes");
else puts("No");
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll tomorin=read<ll>();
while (tomorin--) solve();
return 0;
}质因数分解
对于数n，因数是成对分布的，故可以枚举每一个数i到\(\sqrt{n}\)，若是合数说明i是他的一个质因子，让\(\frac{n}{i}\)，直到无法再除，证明将当前质因子对应的因数除尽，再试下一个i
1
2
3
4
5
6
7
8
9
void f(int n){
for (int i = 2; i*i<=n;i++){
if(n%i==0){
cout << i << endl;
while(n%i==0) n/=i;
}
}
if(n>1) cout << n << endl;
}注意，若已经有一个素数表，时间复杂度将会从\(O(\sqrt{N})\)下降为\(O(\frac{\sqrt{N}}{\ln N})\)
质数筛
埃氏筛
用一个vis数组标记是质数还是合数，默认都是质数
从第一个质数2开始，计算\(2\times2\)，\(2\times3\cdots\)，这些数肯定是合数，将这些数对应的vis标记为合数，再遍历操作下一个质数
注意：每次标记只需要从质数\(i\times i\)开始往后每次加\(i\)即可，因为前面的肯定被小于该数的质数标记过了
另外，由于偶数除了2都是合数，我们可以选择跳过偶数来让内存和操作需求都减半
另另外，由于bitset的连续读写效率，我们可以将bool数组改为bitset来将布尔值压到一个bit中，可以显著减少内存消耗，这种方法称为位级压缩
时间复杂度：\(O(n\log(\log n))\)
1
2
3
4
5
6
7
8
9
10
vector<bool> prime(N, true);
void ehrlich(int n){
for (int i = 2;i*i<=n;i++){
if(prime[i]){
for(int j = i*i;j<=n;j+=i){
prime[j]=false;
}
}
}
}若只是计数，埃氏筛还可以改进：我们可以预估质数数量，若发现更多合数就减掉
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 注意此时true表示合数
vector<bool> prime(N, false);
int ehrlich(int n){
int cnt = (n+1)/2; // 默认偶数都是合数
// 只需要判断奇数
for (int i = 3;i*i<=n;i+=2){
if(!prime[i]){
// 只需要判断奇数
for(int j = i*i;j<=n;j+=2*i){
if(!prime[j]){
prime[j]=true;
cnt--;
}
}
}
}
}欧拉筛
埃氏筛也有重复筛的情况，因此会慢一些
而欧拉筛保证了每个合数只被自己的最小质因子筛掉
时间复杂度\(O(n)\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<bool> prime(N, true);
void eular(int n){
int tprime[n/2+1];
int cnt = 0;
for (int i = 2;i<=n;i++){
if(prime[i]){
tprime[cnt++]=i;
}
for(int j = 0; j<cnt;j++){
if(i*tprime[j]>n)break;
prime[i*tprime[j]]=false;
if(i%tprime[j]==0) break;
}
}
}分段筛法
普通的线性筛在数据范围很大的时候会超时或耗尽内存，此时我们需要使用分段筛
思想：用普通筛筛出\(\sqrt{n}\)内的所有质数，然后将所需区间[l, r]分成一段或多段，并对段进行标记，用筛出的质数标记段中合数，并统计没被标记的质数即可
步骤：设右区间为r
- 计算\(\sqrt{r}\)，用筛筛出这之内的数
- 定义布尔数组标记合数（初始都设为false，表示为可能质数），长度为\(r-l+1\)
- 对每个质数
- 若
1ll*p*p>r则可以提前break，因为超出区间右端 - 计算[l,
r]中第一个需要标记的位置
start = max(1LL*p*p, ((l + p - 1) / p) * 1LL * p)，即从区间第一个p的倍数开始，p小的时候也可以避免把p本身标掉 - 从start开始以p步长标记
start-l位置为合数，数组标记为true
- 若
- 对于
l==1时，需要特殊处理数组0下标为合数，因为1不是质数 - 最后统计数组中false的位置就是质数
注意：
- 要开longlong，避免乘法溢出
- 若r和r-l都很大，可以考虑分为多个块，对每个块都进行流程
code例：
洛谷P1835 素数密度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
vector<bool> prime(N, true);
ll tprime[N];
bool vis[N]={};
ll cnt = 0;
// 观察到数据规模2^31，如果单纯用线性筛会导致爆内存
// 这时需要分段筛法
void eular(ll n){
for(ll i =2;i<=n;i++){
if(prime[i]){
tprime[++cnt] = i;
}
for(ll j = i+i;j<=cnt;j+=i){
if(i*tprime[j]>n) break;
prime[i*tprime[j]]=false;
if(i%tprime[j]==0)break;
}
}
}
void solve() {
ll l, r;
cin >> l >> r;
// 首先晒出√2^31内的质数，然后用这些质数作为因子来在l-r范围内筛出合数并标记（i*p为合数）
// 遍历l-r，没有标记的就是质数
eular(50000);
if (l==1) vis[0]=1; // 特判l=1
for(int i = 1;i<=cnt;i++){
ll p = tprime[i];
for(ll j = max(2ll, (l-1)/p+1)*p;j<=r;j+=p){ // 计算在区间 [l,r] 中，应该从哪个数开始把质数 p 的倍数标记为合数（分段筛的起点）
if(j-l>=0) vis[j-l]=true; // 将l-r移动至0-(r-l)范围内，防止过大的下标爆数组
}
}
ll ans = 0;
for(ll i = 0;i<=r-l;i++)if(!vis[i]) ans++;
cout<<ans;
}筛法求约数个数
用\(d\)表示\(i\)的约数个数，\(num_i\)表示\(i\)的最小质因子出现次数
约数个数定理
定理
若 \(n = \displaystyle\prod_{i=1}^{m}
p_i^{c_i}\)，则 \(d(n)
\;=\;\prod_{i=1}^{m}(c_i + 1)\,.\)
证明
对每个质因子 \(p_i^{c_i}\)，它的约数有
\(p_i^0,\;p_i^1,\;\dots,\;p_i^{c_i}\)共
\(c_i+1\) 个。由乘法原理可知， \(n=\prod_{i=1}^{m}p_i^{c_i}\)的约数总数就是
\(\prod_{i=1}^{m}(c_i+1)\,.\)
实现
由于\(d_i\)是积性函数，所以我们可以使用线性筛
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
vector<int> pri; // 存储筛出的素数列表
bool not_prime[N]; // 标记合数
int d[N]; // d[i] 表示 i 的约数个数
int num[N]; // num[i] 表示 i 分解后，最低位质因子 p 在 i 中的幂次
void pre(int n) {
d[1] = 1; // 1 的约数个数为 1
for (int i = 2; i <= n; ++i) {
if (!not_prime[i]) {
// i 是素数
pri.push_back(i);
d[i] = 2; // 素数 i 的约数只有 1 和 i 自身，共 2 个
num[i] = 1; // i = p^1, 此处最低质因子 p 的幂次为 1
}
// 用已知的素数列表，对 i 进行线性筛
for (int p : pri) {
if (i * p > n) break;
not_prime[i * p] = true; // 标记 i*p 为合数
if (i % p == 0) {
// 情况一：p 是 i 的最低质因子，i = … * p^k
// 那么 i*p = … * p^(k+1)，尾质因子 p 的幂次加 1
num[i * p] = num[i] + 1;
// 如果 i 的约数个数为 d[i]，且 i 中 p 的幂次为 num[i]，
// 那么 i*p 中 p 的幂次就是 num[i]+1
// 根据约数个数公式：若 n = p1^a1 * p2^a2 *…，d(n)=∏(ai+1)
// 我们可以在已知 d[i] 的基础上做局部更新：
// d[i*p] = d[i] / (num[i] + 0) * (num[i] + 1)
d[i * p] = d[i] / num[i] * (num[i] + 1);
break; // 线性筛保证每个合数只被最小质因子对应的 p 处理一次
} else {
// 情况二：p 不是 i 的最低质因子，在 i*p 中 p^1 首次出现
num[i * p] = 1;
// 新加了一个质因子 p，故约数个数 d[i*p] = d[i] * 2
d[i * p] = d[i] * 2;
}
}
}
}筛法求约数和
\(f_i\) 表示 \(i\) 的约数和，\(g_i\) 表示 \(i\) 的最小质因子的 \(p^0 + p^1 + p^2 + \cdots + p^k \,.\)
用线性筛在 \(O(n)\) 时间内计算出
\(1\sim n\) 每个正整数的约数和 \(f[i]\)，其中
- \(f[i]=\sum_{d\mid i}d\)；
- \(g[i]\) 表示将 \(i\) 分解为最小质因子 \(p\) 的幂乘以其它部分后，单独对这段 \(p^k\) 求和： \[
g[i]=1 + p + p^2 + \cdots + p^k\,,
\] 其中 \(p^k\parallel i\)，且
\(p\) 是 \(i\) 的最小质因子。
借助下面这个分块性质：
\[
\text{若 }i=p^k\times x\text{ 且 }\gcd(p,x)=1,\quad
f(i)=\bigl(1+p+\cdots+p^k\bigr)\times f(x)=g[i]\times f(x)\,,
\] 我们可以在线性筛中同时维护 \(g[i]\) 与 \(f[i]\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
vector<int> pri; // 存储已筛出的素数列表
bool not_prime[N]; // 合数标记
int g[N], f[N]; // g[i]：i 中最小质因子 p 的 1+p+...+p^k 和
// f[i]：i 的约数和
void pre(int n) {
// 初始化：1 的约数和为 1，g[1]=1
g[1] = f[1] = 1;
for (int i = 2; i <= n; ++i) {
if (!not_prime[i]) {
// i 是素数 p
pri.push_back(i);
// 对于素数 p：
// g[p] = 1 + p
// f[p] = 1 + p
g[i] = i + 1;
f[i] = i + 1;
}
// 用已筛出的素数列表对 i 进行线性筛
for (int p : pri) {
if (i * p > n) break;
int ip = i * p;
not_prime[ip] = true; // 标记合数
if (i % p == 0) {
// 情况一：p 是 i 的最小质因子，即 i = p^k * x
// 那么 ip = p^(k+1) * x，x 与 p 互素
// g[i] = 1 + p + ... + p^k
// 则 g[ip] = 1 + p + ... + p^k + p^(k+1) = g[i]*p + 1
g[ip] = g[i] * p + 1;
// f[ip] = f(x) * g[ip]，而 f[i] = f(x)*g[i]
// 故 f[ip] = f[i] / g[i] * g[ip]
f[ip] = f[i] / g[i] * g[ip];
// 线性筛关键：找到 i 的最小质因子后立即 break
break;
} else {
// 情况二：p 不是 i 的最小质因子，i 与 p 互素
// ip 增加了一个新的质因子 p^1
// g[ip] = 1 + p
// f[ip] = f[i] * f[p] = f[i] * (1+p)
g[ip] = 1 + p;
f[ip] = f[i] * f[p];
}
}
}
}