分解质因数

：

算术基本定理：

算术基本定理可表述为：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积。

首先根据 算术基本定理 可以知道，一个合数可以由多个比他小的质数相乘而得，而这些质数就是他的质因数。

并且，例如一个数 x是 n 的因数，并且是合数，那么问一个问题。是否存在一个质数是 x 的质因数，而不是 n 的质因数？答案是不可能的哈

证明：

很明显因为 n/x = k，那么 x 的质因数组成 x 的时候只要再乘以 k 就可以得到 n，因此可以得出一个结论：n 的因数的质因数，肯定也是 n 的质因数。

那么能不能得到一个结论就是，n 的任何一个因数 x假如他是合数，那么他绝对可以由 n 的小于x的质因数所相乘而得

答案是可以的哈

证明：

根据上面的结论推导一下就可以了。n 的因数如果是合数，那么他绝对可以由比他小的质因数组合而成，同时这些质因数是 n 的质因数，那么不就可以得到上面问题的结论。

因此最后我们又可以得到一条结论：一个数的因数，如果排序的话，最开始的因数肯定是质因数，后面才有合数。

可不可以这么推论呢？可以的。

证明：

还是根据第一条理论。假如n 的因数除了 1 之外第一个因数是合数，那么他绝对可以由一些质因数组合而成，那么这些数是比他小的，且是 n 的质因数，因此，这些数也是 n 的因数，并且是质数。

**数 x 是数 n 的因数，且是合数，那么 n 的质因数不一定是 x 的质因数，而 x 的质因数一定是 n 的质因数。**因此当将 n 的所有比x 小的质因数都除尽的时候，因此当 i 为 x 的时候自然是无法进行整除的。

因此现在可以证明，从小到大遍历数 n 的因数，并且每次都除尽的话，那么只会遍历到数 n 的质因数，而不会是合数

最后可以得出，每次if(n%i==0) 成立的时候 i 一定是 n 的质因数。