质数

设 $n \ge 2$ 为整数，若所有满足 $1 \lt k \lt n$ 的整数 $k$ 都不是 $n$ 的约数，则称 $n$ 为质数或素数，否则称 $n$ 为合数。

$1$ 既不是质数，也不是合数。

质数个数

定义 $π(n)$ 为不大于 $n$ 的质数个数，可以证明： $π(n)=O(\frac{n}{logn})$

唯一分解定理

设 $n \ge 2$ 为整数，则有唯一的分解式 $n=\prod_{i=1}^{m} p_i^{k_i}$

其中 $p_1 \lt p_2 \lt \dots \lt p_m$ 为质数，$k_i$ 为正整数。 可以证明 $m=O(log \ logn)$。

质因数分解

分解方法一：

vector<int> factor(int n) {
    vector<int> f;
    for (int i = 2; i <= n; ++i) {
        while (n % i == 0) {
            f.push_back(i);
            n /= i;
        }
    }
    return f;
}

分解方法二：

vector<int> factor(int n) {
    vector<int> f;
    for (int i = 2; i * i <= n; ++i) {
        while (n % i == 0) {
            f.push_back(i);
            n /= i;
        }
    }
    if (n > 1) f.push_back(n);
    return f;
}

分解方法三：

vector<int> p; // 质数表
vector<int> factor(int n) {
    vector<int> f;
    for (int i = 0; i < p.size(); ++i) {
        if (p[i] * p[i] > n) break;
        while (n % p[i] == 0) {
            f.push_back(p[i]);
            n /= p[i];
        }
    }
    if (n > 1) f.push_back(n);
    return f;
}

复杂度分析

方法一的复杂度为 $O(n)$ 方法二的复杂度为 $O(\sqrt{n})$ 方法三的复杂度为 $O(\frac{\sqrt{n}}{logn})$

数学知识：n最多包含一个大于√n的质因子。例如6=2×3，√6=2.44949，存在一个>√6的质因子3 比如： 1000007 因式分解 29 * 34483 因数 1, 29, 34483, 1000007

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com