C++ 模板：唯一分解定理、辗转相除法、埃氏筛与线性筛（含质因数分解示例）
下面给出一套实用的 C++ 模板，包含：
- 辗转相除法（求 gcd / lcm）
- 试除法的质因数分解（适合小到中等 n）
- 使用埃氏筛预生成素数（并用于分解）
- 线性筛（线性时间生成素数，并可得到每个数的最小质因子
minPrime，用于 O(log n) 分解） - 演示
main()中的用法示例
代码带有注释，复制到竞赛/练习模板中即可使用。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;// ----------------- 辗转相除法 gcd / lcm -----------------
ll gcd_ll(ll a, ll b) {if (a < 0) a = -a;if (b < 0) b = -b;while (b) {ll t = a % b;a = b;b = t;}return a;
}ll lcm_ll(ll a, ll b) {if (a == 0 || b == 0) return 0;return a / gcd_ll(a, b) * b; // 注意顺序防止溢出
}// ----------------- 试除法质因数分解 -----------------
// 适用于 n <= ~1e12 的单次分解（若 n 很大或多次分解建议用预生成素数或线性筛）
vector<pair<ll,int>> factorize_trial(ll n) {vector<pair<ll,int>> res;if (n < 0) { n = -n; /* 可以把 -1 单独处理 */ }for (ll p = 2; p * p <= n; ++p) {if (n % p == 0) {int cnt = 0;while (n % p == 0) {n /= p;++cnt;}res.emplace_back(p, cnt);}}if (n > 1) res.emplace_back(n, 1);return res;
}// ----------------- 埃氏筛（Sieve of Eratosthenes）-----------------
// 返回所有 <= n 的质数向量，时间约 O(n log log n)
vector<int> sieve_eratosthenes(int n) {if (n < 2) return {};vector<char> isPrime(n + 1, true);isPrime[0] = isPrime[1] = false;for (int p = 2; (ll)p * p <= n; ++p) {if (isPrime[p]) {for (int j = p * p; j <= n; j += p) isPrime[j] = false;}}vector<int> primes;for (int i = 2; i <= n; ++i) if (isPrime[i]) primes.push_back(i);return primes;
}// 使用用埃氏筛生成的 primes 对一个数做分解（若 n <= maxPrime^2）
vector<pair<ll,int>> factorize_with_primes(ll n, const vector<int>& primes) {vector<pair<ll,int>> res;for (int p : primes) {if ((ll)p * p > n) break;if (n % p == 0) {int cnt = 0;while (n % p == 0) {n /= p;++cnt;}res.emplace_back(p, cnt);}}if (n > 1) res.emplace_back(n, 1);return res;
}// ----------------- 线性筛（Linear sieve）-----------------
// 返回 primes 向量，并生成 minPrime 数组：minPrime[x] = x 的最小质因子（x >= 2）
// 时间复杂度 O(n)
pair<vector<int>, vector<int>> linear_sieve(int n) {vector<int> primes;vector<int> minPrime(n + 1, 0); // minPrime[i] = 0 表示还未设置for (int i = 2; i <= n; ++i) {if (minPrime[i] == 0) {minPrime[i] = i;primes.push_back(i);}for (int p : primes) {ll v = 1LL * p * i;if (v > n) break;minPrime[v] = p; // 保证每个合数只被其最小质因子标记一次if (p == minPrime[i]) {// 保持线性：当 p 为 i 的最小质因子时，p * i 的最小质因子就是 p，且后续 breakbreak;}}}return {primes, minPrime};
}// 使用 minPrime 数组对 n 做分解（若 n <= size(minPrime)-1）
vector<pair<int,int>> factorize_with_minPrime(int n, const vector<int>& minPrime) {vector<pair<int,int>> res;if (n <= 1) return res;while (n > 1) {int p = minPrime[n];int cnt = 0;while (n % p == 0) {n /= p;++cnt;}res.emplace_back(p, cnt);}return res;
}// ----------------- 示例 main -----------------
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);// gcd / lcm 示例ll a = 84, b = 30;cout << "gcd(" << a << "," << b << ") = " << gcd_ll(a, b) << "\n";cout << "lcm(" << a << "," << b << ") = " << lcm_ll(a, b) << "\n\n";// 试除分解示例ll n1 = 360; // 360 = 2^3 * 3^2 * 5auto f1 = factorize_trial(n1);cout << n1 << " trial factorization: ";for (auto &pr : f1) cout << pr.first << "^" << pr.second << " ";cout << "\n\n";// 埃氏筛并用 primes 做分解（适合对多个 n 分解，且 n 的质因数较小）int limit = 1000000; // 预先筛到 1e6auto primes = sieve_eratosthenes(limit);cout << "primes up to " << limit << " : count = " << primes.size() << "\n";ll n2 = 999983LL * 2; // 示例auto f2 = factorize_with_primes(n2, primes);cout << n2 << " factorized with precomputed primes: ";for (auto &pr : f2) cout << pr.first << "^" << pr.second << " ";cout << "\n\n";// 线性筛示例（并用 minPrime 快速分解 <= limit）int nLimit = 2000000;auto res = linear_sieve(nLimit);auto &prlist = res.first;auto &minPrime = res.second;cout << "Linear sieve up to " << nLimit << ", primes count = " << prlist.size() << "\n";int x = 1234560; // 必须 x <= nLimitauto fx = factorize_with_minPrime(x, minPrime);cout << x << " factorized with minPrime: ";for (auto &pr : fx) cout << pr.first << "^" << pr.second << " ";cout << "\n";return 0;
}
复杂度与使用建议（小结）
gcd：O(log min(a,b))。- 试除分解（trial）：O(√n)（常用于单个 n 且 n 不太大）。
- 埃氏筛（sieve_eratosthenes）：O(n log log n) 生成所有 <= n 的素数；用来对多个数进行分解时效率高（只要质因子不超过 sieve 的上限）。
- 线性筛（linear_sieve）：O(n)，并得到
minPrime，对 ≤ n 的任意数分解复杂度是 O(log n)（按质因子数计）。
)
