Appearance
若无特殊说明,本章涉及的变量皆为正整数。
定义
若
算数基本定理
任意正整数
分解质因数
试除法
将
分解成 算数基本定理 的形式,如
枚举
cpp
const int N = 1e6;
vector<int> P, C;
void factor(int n) {
for (int i = 2; i <= sqrt(n); i ++) {
if (n % i == 0) {
P.push_back(i), C.push_back(1);
while (n % i == 0)
n /= i, C.back() ++;
}
}
if (n != 1) {
P.push_back(n);
C.push_back(1);
}
}
倍数法
求
中各整数的因数集 ,如
对各整数依次进行 试除法 效率差,此时考虑枚举每个数
的倍数必有因数 。
枚举
时间复杂度为
cpp
const int N = 1e6;
vector<int> fact[N];
void factor(int n) {
for (int i = 1; i <= n; i ++) {
for (int j = 1; i * j <= n; j ++) {
fact[i * j].push_back(i);
}
}
}