算术基本定理
任何一个大于 的正整数都能唯一分解为有限个质数的乘积，可写作：
，其中
都是正整数，
都是质数，且满足
。
试除法
时间复杂度为
image.png
// 试除法分解质因数
void divide(int n)
{
m = 0;
for(int i = 2; i * i <= n; i++)
{
if(n % i == 0) // i是质数
{
p[++m] = i, c[m] = 0;
while(n % i == 0) n /= i, c[m]++; // 除掉所有的i
}
}
if(n > 1) p[++m] = n, c[m] = 1; // n是质数
for(int i = 1; i <= m; i++) cout << p[i] << '^' << c[i] << endl;
}
算术基本定理的推论
在算术基本定理中，若正整数 被唯一分解为
，其中
都是正整数，
都是质数，且满足
，
则 的正约数集合可写作：
的正约数个数为：
的所有正约数的和为：
求 的正约数集合：试除法
时间复杂度为
// 试除法求N的约数集合
int factor[1600], m = 0;
for(int i = 1; i * i <= n; i++)
{
if(n % i == 0)
{
factor[++m] = i;
if(i != n / i) factor[++m] = n / i;
}
}
for(int i = 1; i <= m; i++) cout << factor[i] << endl;
试除法的推论
一个整数 的约数个数上界为
求 每个数的正约数集合：倍数法
若用“试除法”分别求出 每个数的正约数集合，时间复杂度过高，为
。
可以反过来考虑，对于每个数 ，
中以
为约数的数就是
的倍数
。
时间复杂度为 。
// 倍数法求1~N每个数的约数集合
vector<int> factor[500010];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n / i; j++)
factor[i * j].push_back(i);
for(int i = 1; i <= n; i++)
{
for(int j = 0; j < factor[i].size(); j++)
printf("%d ", factor[i][j]);
puts("");
}
倍数法的推论
每个数的约数个数的总和大约为
。.
