所想如期而遇 发表于 2023-4-5 23:19:01

已有 2 人购买  本主题需向作者支付 5 鱼币 才能浏览 购买主题

isdkz 发表于 2023-4-5 23:22:20

这个程序实际上在寻找最大质数因子时已经隐含地考虑了i的质数性质。程序的基本思路是从i=2开始,判断num/i是否为整数且为质数。由于从小到大遍历i,当找到第一个满足条件的j时,可以确保i也是质数。这是因为如果i不是质数,那么i有一个小于它的因子i1,与此同时,j也有一个对应的因子j1(j1 = num / (i1 * i))。由于i1小于i,那么在之前的循环中就会发现(i1, j1)是一对满足条件的因子,而不是在当前的i。因此,当找到满足条件的j时,我们可以确定i也是质数。

第二个break确实是为了跳出内层的for循环。这个程序能实现求出最大的质数因子是因为:


[*]外层循环遍历了所有可能的i值,即从2开始逐步增加,然后计算对应的j值。
[*]对于每个i值,检查是否满足i * j == num。若满足,我们需要确保j是质数。
[*]内层循环检查j是否为质数。如果在循环中找到一个l使得j % l == 0,那么j就不是质数。这时设置flag为0并跳出内层循环。否则,如果内层循环结束时j没有被证明为非质数,那么j就是质数,此时i * j == num并且j是质数。
[*]根据前面的分析,我们可以确信i也是质数。当找到满足条件的j时,即找到了num的一个质因子分解,这时i和j都是质数。由于我们从小到大遍历i,所以在找到满足条件的j时,我们实际上找到了num的最大质因子。
[*]最后,程序输出i值并结束。注意,由于i从小到大遍历,因此找到的i * j == num且j为质数的情况下,i <= j,所以输出的i实际上是j,即num的最大质数因子。

桃花飞舞 发表于 2023-4-5 23:47:53

代码很整洁,很美观,看着亲切舒服。。可能已经默认了i为质因数,第二个break是跳出for循环,我也觉得要是最大质因数应该是j,j是由大到小的,如果j为质因数那一定是最大的,不可能是i,i是从小到大

小甲鱼 发表于 2023-4-6 05:44:54

这道题的答案已经修正哈 -> https://fishc.com.cn/thread-70153-1-1.html
页: [1]
查看完整版本: 求解 600851475143 的最大质数因子是多少?