第一阶段考核的第2题，不知解题思路，答案看不懂
题目：编写一个程序，求解 600851475143 的最大质数因子是多少？（每个合数都可以写成几个质数（素数）相乘的形式，这几个质数就都叫做这个合数的质数因子。
比如 13195 的质数因子有 5, 7, 13 和 29。）
1.能否说下该如何设计该程序？（解题思路）
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;
} 第1问，如果是我，我会这样做。用一个for循环i从一到原来的那个数,看i是不是原来的数的因数,如果是那就break。那么i一定是一个质数。用原来的数除以i，得到一个新的数。编写一个函数，用来检测一个数是否是质数。检测新的数是否是质数,如果不是,重复上述操作,只要把原来的数换成新的数。如果新的数是质数(新的数肯定比被除掉的数更大)，那么新的数就是所求的解(所以新的数是最大的因数)。第2问，那个代码好像就是这种意思。(当你遇到一段代码的时候，先想想自己会怎么做。然后按照你自己的想法推测于原来的代码的作用，你就看得懂代码了) 好吧，这段代码和我的想法有很大的不同。他是反过来想的 一个数由两个数相乘。让一个数最小，那么另一个数就是最大。如果最大的这个数是合数，说明他应该更小一点。那么让这个小的数更大一点就OK了，直到最大更大的那个数是质数。中间的一段代码都是判断该数是不是质数。 召唤风云 发表于 2020-2-7 23:22
一个数由两个数相乘。让一个数最小，那么另一个数就是最大。如果最大的这个数是合数，说明他应该更小一点。 ...
1.if (j % l == 0)
{
flag = 0;
break;
}//这段不是表示，J是合数就break吗？
2.printf("%lld\n", i);//为什么是输出变量i，i不是从最小的开始吗？ 第1问,如果j是合数，就不要它了。这就是flag的作用。第2问。把35,105带进去。发现应该输出j而不是i。但是我复制的时候有一个问题。我也不知道是什么原因。num的值永远都是0,然后我只能用宏定义，就好了。 如果你觉得你没问题，那就是代码有问题。 n的质数因子<=n的平方根，n=600851475143，平方根<800000，穷举出来答案不费什么时间空间 我只知道答案，、、因子是： 召唤风云 发表于 2020-2-8 13:00
第1问,如果j是合数，就不要它了。这就是flag的作用。第2问。把35,105带进去。发现应该输出j而不是i。但是我 ...
因为num被定义为long long，所以在编译的时候应该加上 -std=c99 坑得飞起 发表于 2020-2-8 16:00
n的质数因子
确实也是种思路，谢谢o(*￣▽￣*)o 召唤风云 发表于 2020-2-8 13:00
第1问,如果j是合数，就不要它了。这就是flag的作用。第2问。把35,105带进去。发现应该输出j而不是i。但是我 ...
for循环体的条件是（flag ！=0），应该可理解为当flag为1时就循环下去，为0时跳出来输出结果把，这里J是合数，令flag等于0，我想的是，它会直接终止这个大循环，直接输出结果？
那你认为flag的作用是什么？ 代码有问题，输入15的预期输出是5，实际输出3
这个题的解题思路实际上是分解质因数，属于学编程的经典题了
解法解析也有很多可以自己搜索资料
参考：https://blog.csdn.net/mrbourne/article/details/20315123
解决了分解质因数的问题，求最大就很容易了 for (i = 2, j = num/i; flag != 0; i++, j = num/i, ★flag = 1★),所以flag != 0没用。只有if (flag)
{
break;
}
这句才可以终止循环。只有素数可以 召唤风云 发表于 2020-2-8 19:09
for (i = 2, j = num/i; flag != 0; i++, j = num/i, ★flag = 1★),所以flag != 0没用。只有if (flag)
...
就是说：flag = 0；break；这句可理解为：flag = 0 ；flag = 1；break；这样吗？ Sparin 发表于 2020-2-9 15:02
就是说：flag = 0；break；这句可理解为：flag = 0 ；flag = 1；break；这样吗？
注意看循环最后一句。先执行flag=1,再判断,flag!=0,所以循环一定会继续。只有if (flag)
{
break;
}
这句才可以终止循环。只有素数可以。上面循环判断的条件，可以说根本就没有用。最后一句让flag重新等于1。反正这句话的作用就是这样。一定是只有素数他才可以得到最终结果。 召唤风云 发表于 2020-2-9 15:25
注意看循环最后一句。先执行flag=1,再判断,flag!=0,所以循环一定会继续。只有if (flag)
...
在for语句里不是先判断再进行循环吗？ SHRS23 发表于 2020-2-8 19:04
代码有问题，输入15的预期输出是5，实际输出3
这个题的解题思路实际上是分解质因数，属于学编程的经典题 ...
还要质因数是素数，思路是不是找个循环体从2开始除，等除数等于自身，余数才为0时才跳出循环，否则再将商作为被除数继续进入这个循环体，可以这样理解吗？ Sparin 发表于 2020-2-9 15:33
在for语句里不是先判断再进行循环吗？
for(a;b;c){d}。先进行a。再判断b。不成立则循环终止。成立就执行d。然后执行c。再判断b。然后就是重复。 Sparin 发表于 2020-2-9 15:37
还要质因数是素数，思路是不是找个循环体从2开始除，等除数等于自身，余数才为0时才跳出循环，否则再将商 ...
质数就是素数，是这意思{:10_279:}
页:
[1]
2