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

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呢,谢谢了!

4个回答

显然这段代码有个约束条件,就是输入的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

就是一个一个的除看是否能整除,直到K的值不小于n,如果都没有能整除得数,说明n是质数,符合质数的定义,不过应该是k<=(根号n)才对这样效率更高,因为n开平方的值是他能整除的最大的数

qq_33242378
qq_33242378 他是如何断定最后一个质因数就是递增后的k呢
4 年多之前 回复
这个从根本上看是找出n的最小质因数,因为质数最小为2,所以k的初始值为2,n肯定是大于等于2才有意思,比如:n=12,第一次进入判断,得到12的最小质因数为2,这时n变成了6,第二次进入判断,得到6的最小质因数为2,这时n变为3,第三次进入判断,这时3不能被2整除,所以k++,k变成3,第四次进入判断,3的最小质因数为3,这时n变成1,跳出循环,结束,所以输出了2*2*3
u013181058
圣-雄霸天下 回复qq_33242378: 第四步写错了,应该是判断3==3,输出n,跳出循环,前3步得到2*2*,第四步得到3,合起来就是2*2*3了
4 年多之前 回复
qq_33242378
qq_33242378 他是如何断定最后一个质因数就是递增后的k呢
4 年多之前 回复
    int k,n;
    k=2;
    scanf("%d",&n);
    while(k <= n) {
    if(k == n||n==2) 
    {
        Systrm.out.println(k);
        break;
    }
    else if( n % k == 0) 
    {
            Systrm.out.print(k+"*");
        n = n / k;
        k=2;
    } 
    else k++;
    }

就是从二起一个一个的除,能整除,n=n/k;再将n继续从2除起,

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐