[已解决]第一阶段考核第2题，针对答案，我有两处疑问，求大佬带萌新，想听听你们的理解

coura

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. int main()
   
5. {
   
6.         long long i, j, k, l, num = 600851475143;
   
7.         _Bool flag = 1;
   
8.        
   
9.         for (i = 2, j = num / i; flag != 0; i++, j = num / i, flag = 1)
   
10.         {
    
11.                 if(i * j == num)
    
12.                 {
    
13.                         k = sqrt((double)j);
    
14.                         for (l = 2; l <= k; l++)
    
15.                         {
    
16.                                 if(j %l == 0)
    
17.                                 {
    
18.                                         flag = 0;
    
19.                                         break;
    
20.                                 }
    
21.                         }
    
22.                         if(flag)
    
23.                         {
    
24.                                 break;
    
25.                         }
    
26.                 }
    
27.         }
    
28.        
    
29.         printf("%lld\n", i);
    
30.        
    
31.         return 0;
    
32. }

复制代码

以上就是标准答案了，我有两个地方不懂
第一：为什么i为最大质数因子？
最大质数因子i是87625999，而另一个质数因子为6857。那么for循环，i++先取到6857，此时j=87625999。
那么打印出来的i不应该是最大质数因子，这是我的第一个疑问。

第二：为什么中间要有if(i * j = num)?
在初始值中已经明确j = num / i，那么在循环体中还有其他可能吗？，比如呢？我试过把其注释掉，答案就变成了6，这差异也太大了吧。

最佳答案

月排行榜 / 总排行榜

monkey-D

2021-10-7 21:29:36

没仔细研究，但你的问题第一i取到了6857这时肯定是不满足break出大for循环条件的，这是数学问题；第二long类型仍属于整形，有小数会自动向下取整，注释掉之后会有本来不应该进入的i进入判断导致错误。

跳转到最佳答案楼层

monkey-D

没仔细研究，但你的问题第一i取到了6857这时肯定是不满足break出大for循环条件的，这是数学问题；第二long类型仍属于整形，有小数会自动向下取整，注释掉之后会有本来不应该进入的i进入判断导致错误。

coura

monkey-D 发表于 2021-10-7 21:29
没仔细研究，但你的问题第一i取到了6857这时肯定是不满足break出大for循环条件的，这是数学问题；第二long ...

第二个问题我明白了，
j = num / i与j * i = num是不能划等号的，前者得到的 j 可能是取整的结果，那么j * i 此时就不等于num了。

但是但是……
第一个问题我还是百思不得其解，因为87625999和6857都是两个素数，
当 i =6857时，j = 87625999是质数，内层循环不执行，所以flag = 1,在最后的if语句中跳出大循环。
所以i++到6857时就跳出去了，此时不是最大质数因子……

是这样吗，求指出问题，谢谢大佬

monkey-D

coura 发表于 2021-10-7 23:28
第二个问题我明白了，
j = num / i与j * i = num是不能划等号的，前者得到的 j 可能是取整的结果，那么j ...

进入了啊进入了啊，i×j=num，6857×87625999=600851475143，进入了内层for循环导致falg=0导致不跳出去，就算j是素数sqrt也是自动取整的怎么就没有进入内层for循环了

coura

monkey-D 发表于 2021-10-7 21:29
没仔细研究，但你的问题第一i取到了6857这时肯定是不满足break出大for循环条件的，这是数学问题；第二long ...

还是谢谢您的讲解

万事屋

唉。。虽然你已经把最佳答案给了一个奇怪的答案，但是我还是帮你解答一下你的疑问好了。。。
87625999=71*891*1471，并不是质数，所以答案是6857。
其实，小甲鱼老师给出的这题的标准答案的算法不是很好，第一重for循环要跑到87625999才能跑出答案。
求最大质因子完全可以不断用600851475143从小到大除以所有可以除断的质数（当然，编程的时候不需要判断除数是不是质数，只要能除断就一直除就行），这样第一重for循环只要跑到1471就能出答案，花费的运算量不到标准答案运算量的10000分之一。

蓝咕咕

万事屋 发表于 2022-2-6 01:24
唉。。虽然你已经把最佳答案给了一个奇怪的答案，但是我还是帮你解答一下你的疑问好了。。。
87625999=71* ...

71*891*1471=93056931啊，不过87625999确实不是质数

164342146

1234169 * 71 = 87625999，答案错了！