蒟蒻君的数学学习之路2——质数相关算法
⭐前言
质数,是数学里很重要的东东。若
p
p
p为质数,
p
p
p为
>
1
>1
>1的整数且
p
p
p有且仅有
1
1
1和
p
p
p两个因数。
今天,蒟蒻君将和大家一起学习质数相关算法(难度递增qwq)。
⭐一、质数判定
?
1.1
1.1
1.1 试除法
?思路
最常用的算法。
- 假设
n
n
a
,
b
a,b
n
=
a
×
b
n = a times b
- 令
a
<
b
a < b
a
≤
n
a le sqrt n
- 枚举
a
=
1
−
n
a = 1 - sqrt n
a
a
n
n
n
n
- 注意特判
0
0
1
1
时间复杂度:
O
(
n
)
O(sqrt n)
O(n
);
空间复杂度:
O
(
1
)
O(1)
O(1)。
?代码
inline bool isprime(int n) {
if (n < 2) {
return false;
}
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) {
return false;
}
}
return true;
}
?
1.2
1.2
1.2 卡常写法
?思路
在法一的基础上可以进行以下优化:
若
n
n
n为质数,则
n
m
o
d
2
≠
0
n mod 2 neq 0
nmod2=0且
n
m
o
d
3
≠
0
n mod 3 neq 0
nmod3=0,则
n
m
o
d
6
=
1
/
5
n mod 6 = 1/5
nmod6=1/5。跳过
2
−
4
2 - 4
2−4,时间复杂度可提高到之前的
1
3
frac{1}{3}
31。
注意特判
n
=
2
/
3
/
5
/
7
/
11
n=2/3/5/7/11
n=2/3/5/7/11还有
n
=
2
/
3
/
5
k
(
k
∈
N
)
n=2/3/5k(kin N)
n=2/3/5k(k∈N)。
时间复杂度:
O
(
n
)
O(sqrt n)
O(n
),只是常数有些变化;
空间复杂度:
O
(
1
)
O(1)
O(1)。
?代码
inline bool isprime(int n) {
if (n < 2) {
return false;
}
if (n == 2 || n == 3 || n == 5 || n == 7 || n == 11) {
return true;
}
if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0) {
return false;
}
for (int i = 1; i <= n / 6 + 1; ++i) { // 枚举n = 6 * i +/- 1
if (i * 6 >= sqrt(n) + 5) {
break;
}
if ((n % (i * 6 + 1) == 0) || (n % (i * 6 + 5) == 0)) {
return false;
}
}
return true;
}
如果让你从
1
−
100
1 - 100
1−100这些数里筛出质数,那你还会一个一个数地试除吗 (当然你没有背过)?
质数筛法适用于先预处理,然后多次查询的条件下。
下面我们来学习质数的两种筛法叭~
注意,质数筛法标程以洛谷P3383【模板】线性筛素数为例。
?
1.3
1.3
1.3 埃氏筛法
?思路
相信大家也都对这种方法不陌生。
比如我们要判断
1
−
100
1 - 100
1−100中选出所有质数,那么我们可以这样做:
- 先将
1
−
100
1 - 100
- 我们在
2
2
2
2
- 再在
3
3
3
3
- 现在你发现
4
4
5
5
5
5
- 以此类推,直到
1
−
100
1 - 100
接下来我们来分析一下ta的时间复杂度。
因为所有数要么都被删除或圈出一次,则时间复杂度为
O
(
n
)
O(n)
O(n)。
nonono
仔细思考可知,有些数会被删除多次,如
6
6
6被
2
2
2和
3
3
3删除,则:
T
(
n
)
=
O
(
∑
p
≤
n
n
p
)
=
O
(
∑
p
≤
n
1
p
)
=
O
(
n
l
o
g
l
o
g
n
)
T(n)=O(displaystyle sum_{p le n} frac{n}{p})=O(displaystyle sum_{p le n} frac{1}{p})=O(nloglogn)
T(n)=O(p≤n∑pn)=O(p≤n∑p1)=O(nloglogn);
时间复杂度:
O
(
n
l
o
g
l
o
g
n
)
O(nloglogn)
O(nloglogn);
空间复杂度:
O
(
n
)
O(n)
O(n)。
?代码
注意:此方法时间复杂度较高,需使用scanf/printf/ios :: sync_with_stdio(0)方可AC。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e8 + 5;
bool vis[N];
int p[N], cnt;
void init(int n) {
vis[1] = true;
for (int i = 2; i <= n; ++i) {
if (vis[i]) {
continue;
}
p[++cnt] = i;
for (long long j = 1ll * i * i; j <= n; j += i) {
vis[j] = true;
}
}
}
int main() {
int n, q;
scanf("%d %d", &n, &q);
init(n);
while (q--) {
int k;
scanf("%d", &k);
printf("%dn", p[k]);
}
return 0;
}
?
1.4
1.4
1.4 欧拉筛法
?思路
相当于是埃氏筛法的优化版。
分析可知,
n
=
p
1
a
1
×
p
2
a
2
×
p
3
a
3
×
.
.
.
×
p
m
a
m
n = p1^{a1} times p2^{a2} times p3^{a3} times ... times pm^{am}
n=p1a1×p2a2×p3a3×...×pmam只会被
p
1
a
1
−
1
×
p
2
a
2
×
p
3
a
3
×
.
.
.
×
p
m
a
m
p1^{a1-1} times p2^{a2} times p3^{a3} times ... times pm^{am}
p1a1−1×p2a2×p3a3×...×pmam划掉,不用考虑别的了。
时间复杂度:
O
(
n
)
O(n)
O(n);
空间复杂度:
O
(
n
)
O(n)
O(n)。
?代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e8 + 5, M = 1e6 + 5;
bool P[N];
int n, q;
vector<int> p;
void init() {
memset(P, true, sizeof P);
P[1] = false;
p.push_back(0);
for (int i = 2; i <= n; ++i) {
if (P[i]) {
p.push_back(i);
}
for (int j = 1; j <= p.size() && i * p[j] <= n; ++j) {
P[i * p[j]] = false;
if (i % p[j] == 0) {
break;
}
}
}
}
int main() {
cin >> n >> q;
init();
while (q--) {
int k;
cin >> k;
cout << p[k] << 'n';
}
return 0;
}
?
1.5
1.5
1.5 Miller-Rabin测试
?思路
巧妙但会出现失误的方法(但非常好用),适用于大数判断。
用到了一点后面的费马小定理。
- 算出整数
m
m
n
=
2
k
×
m
+
1
n = 2^{k} times m+1
1
≤
a
<
n
1 le a < n
- 对于
i
<
r
(
i
∈
N
)
i < r(i in N)
a
2
i
∗
m
m
o
d
n
=
n
−
1
a^{2^{i}*m} mod n=n-1
a
m
m
o
d
n
=
1
a^m mod n=1
n
n
a
a
- 选择多个
a
a
n
n
t
t
n
n
1
4
t
frac{1}{4^{t}}
- 虽然还是有一定概率判断失误的,但这惊人的时间复杂度确实令人羡慕。如果你每次都用前7个素数测试,所有不超过341550071728320的数都不会判断失误。
注意:这里没有考虑直接乘会超出范围的情况(考虑的话加一点模拟就可以了)。
时间复杂度:
O
(
l
o
g
n
2
)
O(logn^2)
O(logn2);
空间复杂度:
O
(
1
)
O(1)
O(1)。
?代码
int qpow(int x, int y, int p) {
int res = 1;
while (y) {
if (y & 1) {
(res *= x) %= p;
}
(x *= x) %= p;
y >>= 1;
}
return res;
}
inline bool isprime(int n) {
if (n <= 2) {
return n == 2;
}
for (int i = 0; i < 10; ++i) {
int a = rand() % (n - 2) + 2; // 最小为2
if (qpow(a, n, n) != a) {
return false;
}
}
return true;
}
⭐二、相关定理
?
2.1
2.1
2.1 威尔逊定理
?结论
{
若
p
为
质
数
,
(
p
−
1
)
!
≡
−
1
(
m
o
d
p
)
若
(
p
−
1
)
!
≡
−
1
(
m
o
d
p
)
,
p
为
质
数
begin{cases} 若p为质数,(p-1)!equiv -1pmod{p}\ 若(p-1)!equiv -1pmod{p}, p为质数 end{cases}
{若p为质数,(p−1)!≡−1(modp)若(p−1)!≡−1(modp),p为质数
?证明
[
2
,
p
−
2
]
[2,p-2]
[2,p−2]必被
p
−
1
2
frac{p-1}{2}
2p−1对逆元覆盖。
1
1
1的逆元为
1
1
1,故此定理成立。
?
2.2
2.2
2.2 欧拉定理
?结论
欧拉函数:
φ
(
n
)
φ(n)
φ(n)表示满足
1
≤
m
≤
n
,
m
∈
N
1 le m le n,m in N
1≤m≤n,m∈N且
g
c
d
(
n
,
m
)
=
1
gcd(n,m)=1
gcd(n,m)=1时
m
m
m的个数。
欧拉定理: 若
a
,
m
∈
N
a,m in N
a,m∈N且
g
c
d
(
a
,
m
)
=
1
gcd(a,m)=1
gcd(a,m)=1,则
a
φ
(
m
)
≡
1
(
m
o
d
m
)
a^{φ(m)}equiv1pmod{m}
aφ(m)≡1(modm)。
?证明
设
{
b
φ
(
m
)
}
left { b_{φ(m)} right }
{bφ(m)}为
1
→
m
1 to m
1→m中于
m
m
m互质的数的集合。
我们发现
b
b
b数组中所有数
m
o
d
m
mod m
modm余数各不相同,且余数都与
m
m
m互质。
仔细观察后发现,
a
×
b
1
,
a
×
b
2
,
a
×
b
3
,
.
.
.
a
×
b
φ
(
m
)
{a times b_1,a times b_2,a times b_3,...a times b_{φ(m)}}
a×b1,a×b2,a×b3,...a×bφ(m)也符合以上两个条件。
综合以上结论,
∵
g
c
d
(
a
,
m
)
=
1
,
g
c
d
(
b
i
,
m
)
=
1
∴
g
c
d
(
a
×
b
i
,
m
)
=
1
because gcd(a,m)=1,gcd(b_i,m)=1 therefore gcd(a times b_i,m) = 1
∵gcd(a,m)=1,gcd(bi,m)=1∴gcd(a×bi,m)=1。
∵
a
×
b
1
→
φ
(
m
)
m
o
d
n
because a times b_{1 to φ(m)} mod n
∵a×b1→φ(m)modn的结果是
φ
(
m
)
φ(m)
φ(m)个不同且与
m
m
m互质的数、
∴
therefore
∴这些数就是
b
b
b了(真香)。
∴
a
×
b
1
×
a
×
b
2
×
a
×
b
3
×
.
.
.
×
a
×
b
φ
(
m
)
≡
b
1
×
b
2
×
b
3
×
.
.
.
×
b
φ
(
m
)
(
m
o
d
m
)
therefore a times b_1 times a times b_2 times a times b_3 times ... times a times b_{φ(m)} equiv b_1 times b_2 times b_3 times ... times b_{φ(m)} pmod{m}
∴a×b1×a×b2×a×b3×...×a×bφ(m)≡b1×b2×b3×...×bφ(m)(modm)
a
φ
(
m
)
≡
1
(
m
o
d
m
)
a^{φ(m)}equiv1pmod{m}
aφ(m)≡1(modm)
?
2.3
2.3
2.3 费马小定理
?结论
若有
p
p
p为质数,
a
∈
N
a in N
a∈N使得
g
c
d
(
a
,
p
)
=
1
gcd(a,p)=1
gcd(a,p)=1,则
a
p
−
1
≡
1
(
m
o
d
p
)
a^{p-1}equiv 1pmod{p}
ap−1≡1(modp)。
?证明
看完了刚才的欧拉定理,费马小定理的证明应该很简单了叭~
∵
p
because p
∵p为质数
∴
φ
(
p
)
=
p
−
1
thereforeφ(p)=p-1
∴φ(p)=p−1,然后代入即可证明。
其实,费马小定理就是欧拉定理的一个特例。
⭐三、分解质因数
?
3.1
3.1
3.1 试除法
?思路
遍历
i
=
2
−
n
i = 2 - sqrt n
i=2−n
,若
i
i
i是质数且
i
i
i是
n
n
n的因数,则让
n
n
n不断除以
i
i
i,不能整除为止,使用常规算法判断质数(筛不筛复杂度都一样qwq)。
时间复杂度:
O
(
n
)
O(n)
O(n);
空间复杂度:
O
(
1
)
O(1)
O(1)。
?代码
#include <bits/stdc++.h>
using namespace std;
inline bool isprime(int n) {
if (n < 2) {
return false;
}
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) {
return false;
}
}
return true;
}
int main() {
int n;
cin >> n;
for (int i = 1; i * i <= n; ++i) {
if (n % i == 0 && isprime(i)) {
while (n % i == 0) {
cout << i << ' ';
n /= i;
}
}
}
if (isprime(n)) {
cout << n << 'n';
}
return 0;
}
?
3.2
3.2
3.2 Pollard Rho算法
?思路
适用于大数分解。
我们每次寻找
n
n
n的任意一个因数
m
m
m,然后递归分解
m
m
m和
n
m
frac{n}{m}
mn。
最大的问题就是,如何找到一个因数?当然不是去试除,而是有点随机的试验。
我们随机取出一个数
x
x
x,然后构造
y
y
y,使得
m
∣
(
x
−
y
)
,
n
∤
(
x
−
y
)
m mid (x-y),n nmid (x-y)
m∣(x−y),n∤(x−y)
则
m
=
g
c
d
(
x
−
y
,
n
)
m=gcd(x-y,n)
m=gcd(x−y,n)。若结果为
1
1
1的话我们就要继续不断调整
y
y
y,否则就成功找到了一个因数。
对于调整
y
y
y,一般策略为
y
=
y
2
+
t
y=y^2+t
y=y2+t(t自定)。
直到
x
=
y
x=y
x=y,需要重新选取
x
x
x。
时间复杂度:
O
(
n
1
4
)
O(n^{frac{1}{4}})
O(n41);
空间复杂度:
O
(
n
)
O(n)
O(n)。
?代码
#include <bits/stdc++.h>
using namespace std;
int x[1 << 7];
queue<int> q;
int qpow(int x, int y, int p) {
int res = 1;
while (y) {
if (y & 1) {
(res *= x) %= p;
}
(x *= x) %= p;
y >>= 1;
}
return res;
}
bool isprime(int n) {
if (n <= 2) {
return n == 2;
}
int t = n - 1, sum = 0;
int times = 20;
while (!(t & 1)) {
++sum;
t >>= 1;
}
while (times--) {
int a = rand() % (n - 2) + 2;
x[0] = qpow(a, t, n);
for (int i = 1; i <= sum; ++i) {
x[i] = x[i - 1] * x[i - 1] % n;
if (x[i] == 1 && x[i - 1] != 1 && x[i - 1] != n - 1) {
return false;
}
}
if (x[sum] != 1) {
return false;
}
}
return true;
}
int Pollard_Rho(int n, int t) {
int x = rand() % (n - 1) + 1, y = x;
int i = 1, j = 2;
while (true) {
++i;
x = (x * x % n + t) % n;
int m = __gcd((y - x + n) % n, n);
if (m != 1 && m != n) {
return m;
}
if (x == y) {
return n;
}
if (i == j) {
y = x;
j <<= 1;
}
}
}
void calc(int n, int t) {
if (n == 1) {
return ;
}
if (isprime(n)) {
q.push(n);
return ;
}
int m = n, k = t;
while (m >= n) {
m = Pollard_Rho(m, t--);
}
calc(m, k);
calc(n / m, k);
}
int main() {
int n;
cin >> n;
calc(n, 110);
while (q.size()) {
cout << q.front() << ' ';
q.pop();
}
return 0;
}