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

coura

#include <stdio.h>
#include <math.h>

int main()
{
        long long i, j, k, l, num = 600851475143;
        _Bool flag = 1;
        
        for (i = 2, j = num / i; flag != 0; i++, j = num / i, flag = 1)
        {
                if(i * j == num)
                {
                        k = sqrt((double)j);
                        for (l = 2; l <= k; l++)
                        {
                                if(j %l == 0)
                                {
                                        flag = 0;
                                        break;
                                }
                        }
                        if(flag)
                        {
                                break;
                        }
                }
        }
        
        printf("%lld\n", i);
        
        return 0;
}

以上就是标准答案了，我有两个地方不懂
第一：为什么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，答案错了！