质数判断、质因子分解、质数筛
质数判断
判断较小的数是否为质数
试除法 $O(\sqrt n)$
1
2
3
4
5
6
7
8
9
10
bool isPrime(int n){
if(n <= 1)
return false;
for(int i = 2; i * i <= n; i++){
if(n % i == 0){
return false;
}
}
return true;
}
判断较大的数是否为质数(Miller-Rabin素性测试) $O(s * \log^3 n)$
判断n是否是质数，Miller-Rabin测试大概过程:
- 每次选择
1~n-1范围上的随机数字，或者指定一个比n小的质数，进行测试 - 测试过程的数学原理不用纠结，不重要，因为该原理除了判断质数以外，不再用于别的方面
- 原理:费马小定理、Carmichael(卡米切尔数)、二次探测定理(算法导论31章)、乘法同余、快速幂
- 经过s次Miller-Rabin测试，s越大出错几率越低，但是速度t也会越慢，一般测试20次以内即可
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
#include <bits/stdc++.h>
using namespace std;
typedef __int128 ll;
typedef pair<int, int> pii;
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');
}
template<typename T> inline void print(T x, char ed = '\n') {
write(x), putchar(ed);
}
ll t, n;
ll qpow(ll a, ll b, ll mod) { // 快速幂
ll ret = 1;
while(b) {
if(b & 1) ret = (ret * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return ret % 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;
}
int main() {
t = read<ll>();
while(t --) {
n = read<ll>();
if(miller_rabin(n)) puts("Yes");
else puts("No");
}
return 0;
}
质因子分解
获得一个数的(非)重复质因子 $O(\sqrt n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> getPrimeFactors(int n){
vector<int> res;
for(int i = 2; i * i <= n; i++){
if(n % i == 0){
// 要重复则将下行放入while循环内，并去掉if
res.push_back(i);
while(n % i == 0){
n /= i;
}
}
}
if(n > 1){ // 最后一个质因子
res.push_back(n);
}
return res;
}
按公因数计算最大组件大小
思路： 质因数分解+存第一次出现的质因子+并查集
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
unordered_map<int, int> first; // 存第一次出现的质因子{x : i}
vector<int> fa;
vector<int> sz;
void init(int n){
sz.assign(n, 1);
fa.resize(n + 1);
for(int i = 0; i < n; i++){
fa[i] = i;
}
}
int find(int x){
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
bool merge(int x, int y){
int fx = find(x);
int fy = find(y);
if(fx == fy){
return false;
}
fa[fx] = fy;
sz[fy] += sz[fx];
return true;
}
int size(int x){
return sz[x];
}
void factors(int n, int idx){
for(int i = 2; i * i <= n; i++){
if(n % i == 0){
if(first.count(i) == 0){
first[i] = idx; // 第一次出现的质因子
}else{
merge(first[i], idx);
}
while(n % i == 0){
n /= i;
}
}
}
if(n > 1){
if(first.count(n) == 0){
first[n] = idx;
}else{
merge(first[n], idx);
}
}
return;
}
int largestComponentSize(vector<int>& nums) {
init(nums.size());
for(int i = 0; i < nums.size(); i++){
factors(nums[i], i);
}
return *max_element(sz.begin(), sz.end());
}
质数筛
埃式筛 $O(n \log \log n)$
求[0, MAXN - 1]内的所有质数
1
2
3
4
5
6
7
8
9
10
11
12
cosnt int MAXN = 1e6 + 10;
vector<bool> isPrime(MAXN, true);
void sieve(){
isPrime[0] = isPrime[1] = false;
for(int i = 2; i * i < MAXN; i++){
if(isPrime[i]){
for(int j = i * i; j < MAXN; j += i){ // < MAXN 防止溢出
isPrime[j] = false;
}
}
}
}
欧拉筛 $O(n)$
求[0, MAXN - 1]内的所有质数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int MAXN = 1e6 + 10;
vector<bool> isPrime(MAXN, true);
vector<int> primes;
void sieve(){
isPrime[0] = isPrime[1] = false;
for(int i = 2; i < MAXN; i++){
if(isPrime[i]){
primes.push_back(i); // 存入质数列表
}
for(int p : primes){
if(1ll * i * p >= MAXN){
break; // 防止溢出和越界
}
isPrime[i * p] = false; // 标记合数
if(i % p == 0){ // 关键：保证线性时间复杂度
break;
}
}
}
}
