蒟蒻君的数学学习之路2——质数相关算法

⭐前言

质数,是数学里很重要的东东。若ppp为质数,ppp>1>1>1的整数且ppp有且仅有111ppp两个因数。
今天,蒟蒻君将和大家一起学习质数相关算法(难度递增qwq)。


蒟蒻君的数学学习之路2——质数相关算法
蒟蒻君的数学学习之路2——质数相关算法

⭐一、质数判定

🎉 1.1 1.1 1.1 试除法

🚀思路

最常用的算法。

  1. 假设 n n n不是质数,则必有 a , b a,b a,b使得 n = a × b n = a \times b n=a×b
  2. a < b a < b a<b, 则 a ≤ n a \le \sqrt n an
  3. 枚举 a = 1 − n a = 1 – \sqrt n a=1n ,若所有 a a a均不被 n n n整除,则 n n n为质数,否则为合数。
  4. 注意特判 0 1 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 卡常写法

🚀思路

在法一的基础上可以进行以下优化:
nnn为质数,则nmod  2≠n \mod 2 \neq 0nmod2=0nmod  3≠n \mod 3 \neq 0nmod3=0,则nmod  6=1/5n \mod 6 = 1/5nmod6=1/5。跳过2−42 – 424,时间复杂度可提高到之前的13\frac{1}{3}31
注意特判n=2/3/5/7/11n=2/3/5/7/11n=2/3/5/7/11还有n=2/3/5k(k∈N)n=2/3/5k(k\in N)n=2/3/5k(kN)

时间复杂度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−1001 – 1001100这些数里筛出质数,那你还会一个一个数地试除吗 (当然你没有背过)
质数筛法适用于先预处理,然后多次查询的条件下。
下面我们来学习质数的两种筛法叭~
注意,质数筛法标程以洛谷P3383【模板】线性筛素数为例。

🎉 1.3 1.3 1.3 埃氏筛法

🚀思路

相信大家也都对这种方法不陌生。
比如我们要判断1−1001 – 1001100中选出所有质数,那么我们可以这样做:

  1. 先将 1 − 100 1 – 100 1100写在纸上。
  2. 我们在 2 2 2上画一个小圈圈,然后叉掉所有 2 2 2的倍数;
  3. 再在 3 3 3上画一个小圈圈,删掉所有 3 3 3的倍数;
  4. 现在你发现 4 4 4已经被删掉了,那么就可以在 5 5 5上画一个圈圈,然后删掉所有 5 5 5的倍数。
  5. 以此类推,直到 1 − 100 1 – 100 1100中所有数都被划掉或圈起为止,质数为所有被圈出来的数。

接下来我们来分析一下ta的时间复杂度。
因为所有数要么都被删除或圈出一次,则时间复杂度为O(n)O(n)O(n)
nonono
仔细思考可知,有些数会被删除多次,如666222333删除,则:

T(n)=O(∑p≤nnp)=O(∑p≤n1p)=O(nloglogn)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(pnpn)=O(pnp1)=O(nloglogn)
时间复杂度O(nloglogn)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("%d\n", p[k]);
	}
	return 0;
} 

🎉 1.4 1.4 1.4 欧拉筛法

🚀思路

相当于是埃氏筛法的优化版。
分析可知,n=p1a1×p2a2×p3a3×...×pmamn = p1^{a1} \times p2^{a2} \times p3^{a3} \times … \times pm^{am}n=p1a1×p2a2×p3a3×...×pmam只会被p1a1−1×p2a2×p3a3×...×pmamp1^{a1-1} \times p2^{a2} \times p3^{a3} \times … \times pm^{am}p1a11×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测试

🚀思路

巧妙但会出现失误的方法(但非常好用),适用于大数判断。
用到了一点后面的费马小定理。

  1. 算出整数 m m m使得 n = 2 k × m + 1 n = 2^{k} \times m+1 n=2k×m+1,随机 1 ≤ a < n 1 \le a < n 1a<n
  2. 对于 i < r ( i ∈ N ) i < r(i \in N) i<r(iN),若 a 2 i ∗ m m o d    n = n − 1 a^{2^{i}*m} \mod n=n-1 a2immodn=n1 a m m o d    n = 1 a^m \mod n=1 ammodn=1,则 n n n通过 a a a的测试;
  3. 选择多个 a a a,若全部通过则认为 n n n为质数。通过 t t t次测试, n n n为合数的概率为 1 4 t \frac{1}{4^{t}} 4t1
  4. 虽然还是有一定概率判断失误的,但这惊人的时间复杂度确实令人羡慕。如果你每次都用前7个素数测试,所有不超过341550071728320的数都不会判断失误。

注意:这里没有考虑直接乘会超出范围的情况(考虑的话加一点模拟就可以了)。
时间复杂度O(logn2)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——质数相关算法
蒟蒻君的数学学习之路2——质数相关算法

⭐二、相关定理

🎉 2.1 2.1 2.1 威尔逊定理

🚀结论

{若p为质数,(p−1)!≡−1(modp)若(p−1)!≡−1(modp),p为质数\begin{cases} 若p为质数,(p-1)!\equiv -1\pmod{p}\\ 若(p-1)!\equiv -1\pmod{p}, p为质数 \end{cases}{p,(p1)!1(modp)(p1)!1(modp),p

🚀证明

[2,p−2][2,p-2][2,p2]必被p−12\frac{p-1}{2}2p1对逆元覆盖。111的逆元为111,故此定理成立。

🎉 2.2 2.2 2.2 欧拉定理

🚀结论

欧拉函数:φ(n)φ(n)φ(n)表示满足1≤m≤n,m∈N1 \le m \le n,m \in N1mn,mNgcd(n,m)=1gcd(n,m)=1gcd(n,m)=1mmm的个数。
欧拉定理:a,m∈Na,m \in Na,mNgcd(a,m)=1gcd(a,m)=1gcd(a,m)=1,则aφ(m)≡1(modm)a^{φ(m)}\equiv1\pmod{m}aφ(m)1(modm)

🚀证明

{bφ(m)}\left \{ b_{φ(m)} \right \}{bφ(m)}1→m1 \to m1m中于mmm互质的数的集合。
我们发现bbb数组中所有数mod  m\mod mmodm余数各不相同,且余数都与mmm互质。
仔细观察后发现,a×b1,a×b2,a×b3,...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)也符合以上两个条件。
综合以上结论,∵gcd(a,m)=1,gcd(bi,m)=1∴gcd(a×bi,m)=1\because gcd(a,m)=1,gcd(b_i,m)=1 \therefore gcd(a \times b_i,m) = 1gcd(a,m)=1,gcd(bi,m)=1gcd(a×bi,m)=1
∵a×b1→φ(m)mod  n\because a \times b_{1 \to φ(m)} \mod na×b1φ(m)modn的结果是φ(m)φ(m)φ(m)个不同且与mmm互质的数、
∴\therefore这些数就是bbb了(真香)。
∴a×b1×a×b2×a×b3×...×a×bφ(m)≡b1×b2×b3×...×bφ(m)(modm)\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(modm)a^{φ(m)}\equiv1\pmod{m}aφ(m)1(modm)

🎉 2.3 2.3 2.3 费马小定理

🚀结论

若有ppp为质数,a∈Na \in NaN使得gcd(a,p)=1gcd(a,p)=1gcd(a,p)=1,则ap−1≡1(modp)a^{p-1}\equiv 1\pmod{p}ap11(modp)

🚀证明

看完了刚才的欧拉定理,费马小定理的证明应该很简单了叭~
∵p\because pp为质数 ∴φ(p)=p−1\thereforeφ(p)=p-1φ(p)=p1,然后代入即可证明。
其实,费马小定理就是欧拉定理的一个特例。

蒟蒻君的数学学习之路2——质数相关算法
蒟蒻君的数学学习之路2——质数相关算法

⭐三、分解质因数

🎉 3.1 3.1 3.1 试除法

🚀思路

遍历i=2−ni = 2 – \sqrt ni=2n,若iii是质数且iiinnn的因数,则让nnn不断除以iii,不能整除为止,使用常规算法判断质数(筛不筛复杂度都一样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算法

🚀思路

适用于大数分解。
我们每次寻找nnn的任意一个因数mmm,然后递归分解mmmnm\frac{n}{m}mn
最大的问题就是,如何找到一个因数?当然不是去试除,而是有点随机的试验。
我们随机取出一个数xxx,然后构造yyy,使得m∣(x−y),n∤(x−y)m \mid (x-y),n \nmid (x-y)m(xy),n(xy)
m=gcd(x−y,n)m=gcd(x-y,n)m=gcd(xy,n)。若结果为111的话我们就要继续不断调整yyy,否则就成功找到了一个因数。
对于调整yyy,一般策略为y=y2+ty=y^2+ty=y2+t(t自定)。
直到x=yx=yx=y,需要重新选取xxx
时间复杂度: O(n14)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;
}

蒟蒻君的数学学习之路2——质数相关算法
蒟蒻君的数学学习之路2——质数相关算法

版权声明:本文为博主蒟蒻一枚原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

原文链接:https://blog.csdn.net/yueyuedog/article/details/121595646

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
xiaoxingxing的头像xiaoxingxing管理团队
上一篇 2023年12月21日
下一篇 2023年12月4日

相关推荐