将一个正整数分解质因数，请问这是用的什么思维逻辑，万分感谢！

Question

while(k <= n) {
if(k == n) {System.out.println(n);break;}
else if( n % k == 0) {System.out.print(k + "*");n = n / k; }
else k++;
请问这是如何断定最后一个质因数就是递增后的k呢，谢谢了！

Answer 1

显然这段代码有个约束条件，就是输入的n应该是可以做因式分解的，否则这段代码无法保证正确性。

假设k从2开始递增，每次k不能整除n的时候递增k，当k可以整除n的时候说明k是n的因数，而且是质因数（因为如果k是合数的话，前面就已经判断并输出了，举个例子，如果k=6，那么k肯定无法整除现在的n，因为不可能有个数是6的倍数但不是2和3的倍数。前面当k=2和k=3的时候已经判断过了），这种循环保证了当k递增时，任何比k小的数（包括递增之前的k）都无法整除n了。
每次当k可以整除n的时候，输出k，并且n = n/k，从而使得新的n完成一步因数分解。
现在楼主再参考一下第一行说的约束条件，既然n是可以做因式分解的，任何比k小的数（包括k）都无法再整除n，那么递增（可能递增了不止一次）之后的k就是n最大的质因数。

举个例子，n=140
1. 循环开始，k=2, 此时不满足k==n但是满足因数条件（140%2==0）输出“2 ×” ， n赋值为70 (n = n/k)，进入下一次循环
2. 此时k=2， 此时不满足k==n但是满足因数条件（70%2==0），输出“2×”, n赋值为35
3. 接下来的循环里，k不再满足k==n或是因数条件（35%2 !=0 ），因此递增，直到k=5
4. 当k=5时，再次满足因数条件(35%5==0)，输出“5×”，n被赋值为7
5. 下次循环开始时，k=5，不满足k==n或者因数条件，递增，直到k=7
5. 此时k=7，满足循环结束条件k=n, 输出7，循环结束。
因此总的输出是 2x2x5x7