引言
本文主要解决的问题是如何将一个数分解成多个质因子的乘积，并求出各个质因子的个数
算数基本定理：
任何一个大于 1 的自然数 N，如果 N 不为质数，那么 N 可以唯一分解为有限个质数的乘积\[N = p_1^{a_1}p_2^{a_2}p_3^{a_3} \cdots p_n^{a_n} \]
该算法的目的就是求解该式中的 \(p_i\) 和 \(a_i\)
该算法先结合代码理解比较好理解
代码
void Divide(int x)
{
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
int s = 0;
while (x % i == 0) x /= i, s ++ ;
std::cout << i << ' ' << s << "\n";
}
if (x > 1) std::cout << x << ' ' << 1 << "\n";
return ;
}
算法原理
首先第一层循环从 1 遍历，判断 i 是否为 x 的质因子。
若 x % i == 0，则 i 一定为 x 的质因子。
证明：
设 i 为合数，那么根据算数基本定理，其能分解为多个质因子相乘的形式，其质因子一定比 i 小
由于 i 是从小到大遍历，所以 i 的质因子一定在前面就被遍历到
所以 i 不是合数，只能为质数
随后求出 i 的个数，并将 x 不断除以该质因子直至除净，就可以得到其中的一个质因子 a 和数量 p
最后若 x 大于 1，就说明 x 本身即为质因子，输出 x 即可