分解正整数的质因数

首先，由 算术基本定理可知，任何一个大于1的正整数，都可以分解成若干个质数的乘积，并且这种乘积的形式是唯一的。

所以，对于整数分解，如果先从最小的质数n=2开始进行分解，如果能整除，就只取商，直到不能除时，n++，然后判断n是否大于现在的商。如果大于，结束程序。否则继续循环。

核心代码很短，只有10行左右。

void prim(unsigned long long m)
{
    unsigned long long n = 2;
    while(m >= n)
    {
        while(m % n) n++;
        std::cout << n << " ";
        m /= n;
    }
    endl(std::cout);
}

下面来证明一下算法的正确性。就是证明输出的所有数都是m的因子，且它们相乘等于m。 同时，它们都是质数。

由 算术基本定理可知，任何一个大于1的正整数，都可以分解成若干个质数的乘积，并且这种乘积的形式是唯一的。

首先，通过程序我们直接可知的是，对于输出的n，一定是m的因子。

其次，由于只有在m可以整除n的时候，才用m /= n; 故当所有的n输出后，所有的数字相乘 肯定等于m。

最后，这才是难点。证明所有输出的数字均为质数。

我们用反证法来证明。

<