鱼C论坛

 找回密码
 立即注册
查看: 1336|回复: 3

[已解决]求解 600851475143 的最大质数因子是多少?

[复制链接]
发表于 2023-4-5 23:19:01 | 显示全部楼层 |阅读模式
购买主题 已有 2 人购买  本主题需向作者支付 5 鱼币 才能浏览
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 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的最大质数因子。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-4-5 23:47:53 | 显示全部楼层
代码很整洁,很美观,看着亲切舒服。。可能已经默认了i为质因数,第二个break是跳出for循环,我也觉得要是最大质因数应该是j,j是由大到小的,如果j为质因数那一定是最大的,不可能是i,i是从小到大
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-4-6 05:44:54 | 显示全部楼层
这道题的答案已经修正哈 -> https://fishc.com.cn/thread-70153-1-1.html
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-6-17 09:52

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表