第一阶段考核第2题，针对答案，我有两处疑问，求大佬带萌新，想听听你们的理解
#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，这差异也太大了吧。
{:10_243:} {:10_243:} {:10_243:} 本帖最后由 monkey-D 于 2021-10-7 21:30 编辑
没仔细研究，但你的问题第一i取到了6857这时肯定是不满足break出大for循环条件的，这是数学问题；第二long类型仍属于整形，有小数会自动向下取整，注释掉之后会有本来不应该进入的i进入判断导致错误。 monkey-D 发表于 2021-10-7 21:29
没仔细研究，但你的问题第一i取到了6857这时肯定是不满足break出大for循环条件的，这是数学问题；第二long ...
第二个问题我明白了，
j = num / i与j * i = num是不能划等号的，前者得到的 j 可能是取整的结果，那么j * i 此时就不等于num了{:10_257:}。
但是但是……
第一个问题我还是百思不得其解，因为87625999和6857都是两个素数，
当 i =6857时，j = 87625999是质数，内层循环不执行，所以flag = 1,在最后的if语句中跳出大循环。
所以i++到6857时就跳出去了，此时不是最大质数因子……
是这样吗，求指出问题，谢谢大佬{:10_266:} 本帖最后由 monkey-D 于 2021-10-8 10:10 编辑
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循环了 monkey-D 发表于 2021-10-7 21:29
没仔细研究，但你的问题第一i取到了6857这时肯定是不满足break出大for循环条件的，这是数学问题；第二long ...
还是谢谢您的讲解{:10_266:} 唉。。虽然你已经把最佳答案给了一个奇怪的答案，但是我还是帮你解答一下你的疑问好了。。。
87625999=71*891*1471，并不是质数，所以答案是6857。
其实，小甲鱼老师给出的这题的标准答案的算法不是很好，第一重for循环要跑到87625999才能跑出答案。
求最大质因子完全可以不断用600851475143从小到大除以所有可以除断的质数（当然，编程的时候不需要判断除数是不是质数，只要能除断就一直除就行），这样第一重for循环只要跑到1471就能出答案，花费的运算量不到标准答案运算量的10000分之一。 本帖最后由 蓝咕咕 于 2022-7-17 11:26 编辑
万事屋 发表于 2022-2-6 01:24
唉。。虽然你已经把最佳答案给了一个奇怪的答案，但是我还是帮你解答一下你的疑问好了。。。
87625999=71* ...
71*891*1471=93056931啊，不过87625999确实不是质数 1234169 * 71 = 87625999，答案错了！
页:
[1]