关于小甲鱼C语言阶段测试题目的问题
本帖最后由 zyxzyx。 于 2022-5-26 21:16 编辑. 编写一个程序，求解 600851475143 的最大质数因子是多少？
上面这个是题目
/*先判断是不是除数，在判断除数是不是质数*/
#include<stdio.h>
int main()
{
long long i,d,a,re,sum=600851475143;
_Bool flag=1;
for(i=2;i<sum;i++)
{
if(sum%i==0)
{
for(a=2;a<=i/2;a++)
{
if(i%a==0)
{
flag=0;
break;
}
}
if(flag)
{
re=i;
}
else
{
flag=1;
}
}
}
printf("%d",re);
return 0;
}
这个是我的代码，但是我运行代码迟迟没有结果，当我把sum的值改小，就是去求一个更小的数的最大质因数的时候就可以出结果，
我觉得可能是我算法上的缺陷，但是我不知道我的算法比答案代码的算法差在哪里。求解答
下面是答案的代码
#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", j);
return 0;
}
本帖最后由 jhq999 于 2022-5-26 23:00 编辑
long long i=0,sum=600851475143;
for(i=2;i<sum;i++)
{
if(sum%i==0)
{
sum=sum/i;
i=1;
}
}
printf("%lld",sum); 答案代码：从大因子开始往回遍历，判断是否为质数，发现的第一个质数就是结果，并且直接break终止循环
你的代码：从小因子开始遍历，即使判断为质数，还是得往下继续，直到i=sum循环终止
这性能差距很明显吧。要是题目求最小质数因子，你的倒是满足要求 jhq999 发表于 2022-5-26 22:53
这个写法好妙 本帖最后由 jhq999 于 2022-5-27 10:07 编辑
zyxzyx。 发表于 2022-5-27 09:56
这个写法好妙
1、一个数的最小因子一定是质因子，最小因子对应的就是这个数的最大因子
2、一个数的最大因子的最大质因子也是这个数的最大质因子
3、根据上面两条套娃直到找到这个数最大因子的最大因子……的最大质因子 风车呼呼呼 发表于 2022-5-26 23:42
答案代码：从大因子开始往回遍历，判断是否为质数，发现的第一个质数就是结果，并且直接break终止循环
你 ...
答案代码不也是从小因子开始的吗
也是先找因子在判断因子是不是质数 jhq999 发表于 2022-5-27 10:02
1、一个数的最小因子一定是质因子，最小因子对应的就是这个数的最大因子
2、一个数的最大因子的最大质 ...
那我的代码跟他那个答案代码的差距在哪里
求大佬解答
都是从小的数开始先找因子再判断因子是不是质数 本帖最后由 jhq999 于 2022-5-27 11:24 编辑
zyxzyx。 发表于 2022-5-27 10:35
那我的代码跟他那个答案代码的差距在哪里
求大佬解答
都是从小的数开始先找因子再判断因子是不是质数
这么大的数你从最小挨个取余试得啥时候去
上面的已经给你回答了
zyxzyx。 发表于 2022-5-27 10:34
答案代码不也是从小因子开始的吗
也是先找因子在判断因子是不是质数
好好看看判断质数那块的代码。。。你判断的是 i ，人家判断的是 num/i 为什么我参考程序跑出来的结果是个合数啊 风共我 发表于 2022-6-5 10:53
为什么我参考程序跑出来的结果是个合数啊
他给的答案好像最后一步输出的变量写错了
我帖子上的是改过的答案
页:
[1]