引言

本文主要解决的问题是如何将一个数分解成多个质因子的乘积，并求出各个质因子的个数

算数基本定理：
任何一个大于 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 即可