质数判断、质因子分解、质数筛

质数判断、质因子分解、质数筛

判断质数常规方法

• 时间复杂度 O(根号n)

bool isPrime(long n) {
    if (n <= 1) return false;
    long sq = sqrt(n);
    for (int i = 2; i <= sq; ++i)
        if (n % i == 0)
            return false;
    return true;
}

U148828 素数判断(Miller-Rabin模板)

判断较大的数字是否是质数。

判断 n 是否是质数，Miller-Rabin 测试大概过程：

1，每次选择 1 ~ n-1 范围上的随机数字，或者指定一个比 n 小的质数，进行测试

2，测试过程的数学原理不用纠结，不重要，因为该原理除了判断质数以外，不再用于别的方面

3，原理：费马小定理、Carmichael (卡米切尔数)、二次探测定理(算法导论 31 章)、乘法同余、快速幂

4，经过 s 次 Miller-Rabin 测试，s 越大出错几率越低，但是速度也会越慢，一般测试 20 次以内即可

• 时间复杂度 O(s * ((logn) ^ 3))

#include <bits/stdc++.h>

using namespace std;

typedef __int128 ll;

// __int128 无法用 cin 读入，只能手写读入函数
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);
}

// 快速幂，返回 n 的 p 次方 % mod
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};

// 单次测试的函数，返回 n 是不是合数
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() {
    ll t = read<ll>();
    while (t--) {
        ll n = read<ll>();
        if (miller_rabin(n)) puts("Yes");
        else puts("No");
    }
    return 0;
}

质因子分解

#include <bits/stdc++.h>

using namespace std;

// 时间复杂度 O(根号n)
void printPrimeFactor(int n) {
    int sq = sqrt(n);
    for (int i = 2; i <= sq; ++i) {
        if (n % i == 0) {
            cout << i << endl;
            // 把这个因子除尽
            while (n % i == 0) n /= i;
        }
    }
    // 剩下最后一个因子
    if (n > 1) cout << n << endl;
}

int main() {
    printPrimeFactor(4012100);
}

• 其他质因子分解方法：Pollard's rho algorithm

952. 按公因数计算最大组件大小

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    int maxV = 100001;
    int maxN = 20001;
    // factors[a] = b: a 这个质数因子，最早被下标 b 的数字拥有
    vector<int> factors;
    // father[i] 为 nums[i] 所在集合的代表元素
    vector<int> father;
    // 记录集合大小
    vector<int> size;

    void build(int n) {
        factors.clear();
        size.clear();
        father.clear();

        factors.resize(maxV, -1);
        father.resize(n);
        // 初始状态以自己为集合
        for (int i = 0; i < n; ++i)
            father[i] = i;
        // 每个集合只有一个元素
        size.resize(maxN, 1);
    }

    int find(int x) {
        // 路径压缩
        if (x != father[x])
            father[x] = find(father[x]);
        return father[x];
    }
    
    void un1on(int a, int b) {
        int fa = find(a);
        int fb = find(b);
        if (fa == fb) return;
        // a 所在集合并入 b 所在集合
        father[fb] = fa;
        size[fa] += size[fb];
    }

    // 时间复杂度 O(n * 根号v)
    int largestComponentSize(vector<int> &nums) {
        int n = nums.size();
        build(n);

        for (int i = 0; i < n; i++) {
            int num = nums[i];
            int sq = sqrt(num);
            for (int factor = 2; factor <= sq; factor++) {
                if (num % factor == 0) {
                    if (factors[factor] == -1) {
                        // 因子 factor 最早被下标 i 的数字拥有
                        factors[factor] = i;
                    } else {
                        // 并入共同拥有因子 factor 的集合中
                        un1on(factors[factor], i);
                    }
                    // 除尽这个因子
                    while (num % factor == 0) num /= factor;
                }
            }
            if (num > 1) {
                if (factors[num] == -1) {
                    factors[num] = i;
                } else {
                    un1on(factors[num], i);
                }
            }
        }

        int res = 0;
        for (int i = 0; i < n; i++)
            res = max(res, size[i]);
        return res;
    }
};

204. 计数质数

• 埃氏筛：时间复杂度 O(n * log(logn))

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    // 埃氏筛统计 [0, n] 范围内的质数个数
    // 时间复杂度 O(n * log(logn))
    int ehrlich(int n) {
        if (n <= 1) return 0;
        // visit[i] = false，代表 i 是质数，初始时认为都是质数
        vector<bool> visit(n + 1, false);
        // 遇到质数 i，就把后面到 n 位置所有以 i 为因子的合数标记成合数
        for (int i = 2, sq = sqrt(n); i <= sq; i++)
            if (!visit[i])
                for (int j = i * i; j <= n; j += i)
                    visit[j] = true;
        int res = 0;
        for (int i = 2; i <= n; i++)
            // 可以在此收集质数
            if (!visit[i]) res++;
        return res;
    }

    int countPrimes(int n) {
        return ehrlich(n - 1);
    }
};

• 埃氏筛改进

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    // 埃氏筛统计 [0, n] 范围内的质数个数
    // 时间复杂度 O(n * log(logn))
    int ehrlich(int n) {
        if (n <= 1) return 0;
        // visit[i] = false，代表 i 是质数，初始时认为都是质数
        vector<bool> visit(n + 1, false);
        // 遇到质数 i，就把后面到 n 位置所有以 i 为因子的合数标记成合数
        // 估计的质数数量为奇数的个数，再算上 2 这个质数，如果发现更多合数，那么 cnt--
        int cnt = (n + 1) / 2;
        // 跳过偶数
        for (int i = 3, sq = sqrt(n); i <= sq; i += 2) {
            if (visit[i]) continue;
            // 也要跳过偶数
            for (int j = i * i; j <= n; j += 2 * i) {
                if (!visit[j]) {
                    visit[j] = true;
                    cnt--;
                }
            }
        }
        return cnt;
    }

    int countPrimes(int n) {
        return ehrlich(n - 1);
    }
};

• 欧拉筛：时间复杂度 O(n)

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    // 欧拉筛统计 [0, n] 范围内的质数个数
    // 时间复杂度 O(n)
    int euler(int n) {
        // visit[i] = false，代表 i 是质数，初始时认为都是质数
        vector<bool> visit(n + 1, false);
        // prime 数组收集所有的质数，收集的个数是 cnt，数组一定是递增的
        vector<int> prime(n / 2 + 1);
        int cnt = 0;
        for (int i = 2; i <= n; i++) {
            // 没被标记成合数，就是质数，存入 prime 数组
            if (!visit[i]) prime[cnt++] = i;
            // 遍历 prime 数组
            for (int j = 0; j < cnt && i * prime[j] <= n; j++) {
                // 合数只会被他的最小质因子标记成合数
                visit[i * prime[j]] = true;
                // i 为 4，prime[j] 为 2 时：
                // 如果继续下去，就会执行 visit[3 * 4] = true，也就是 12 被 3 标记成合数，但实际应该由 2 标记
                // i % prime[j] == 0 说明 i >= prime[j]，由于 prime 数组递增，prime[j+1] > prime[j]，可以推出 prime[j] 更小，更适合作为标记者
                // 因为由 i * prime[j+1] 得到的积，完全可以由这个比他俩都小或等于的 prime[j] 与另一个因子（是谁无所谓，反正不会比 prime[j] 还小）相乘得到
                // 4 % 2 == 0，说明 4 >= 2，由于 prime 数组递增，prime[j+1]（也就是3） > prime[j]（也就是2），可以推出 2 更小，更适合作为标记者
                // 因为由 4 * 3 得到的积 12，完全可以由这个比他俩都小的 2 与另一个因子相乘得到
                if (i % prime[j] == 0) break;
            }
        }
        return cnt;
    }

    int countPrimes(int n) {
        return euler(n - 1);
    }
};