[已解决]关于小甲鱼C语言阶段测试题目的问题

zyxzyx。

. 编写一个程序，求解 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 21:16:01

1. long long i=0,sum=600851475143;
   
2.     for(i=2;i<sum;i++)
   
3.     {
   
4.         if(sum%i==0)
   
5.         {
   
6.             sum=sum/i;
   
7.             i=1;
   
8.         }
   
9.     }
   
10.     printf("%lld",sum);

复制代码

跳转到最佳答案楼层

jhq999

1. long long i=0,sum=600851475143;
   
2.     for(i=2;i<sum;i++)
   
3.     {
   
4.         if(sum%i==0)
   
5.         {
   
6.             sum=sum/i;
   
7.             i=1;
   
8.         }
   
9.     }
   
10.     printf("%lld",sum);

复制代码

风车呼呼呼

答案代码：从大因子开始往回遍历，判断是否为质数，发现的第一个质数就是结果，并且直接break终止循环
你的代码：从小因子开始遍历，即使判断为质数，还是得往下继续，直到i=sum循环终止

这性能差距很明显吧。要是题目求最小质数因子，你的倒是满足要求

zyxzyx。

jhq999 发表于 2022-5-26 22:53

这个写法好妙

jhq999

zyxzyx。 发表于 2022-5-27 09:56
这个写法好妙

1、一个数的最小因子一定是质因子，最小因子对应的就是这个数的最大因子
2、一个数的最大因子的最大质因子也是这个数的最大质因子
3、根据上面两条套娃直到找到这个数最大因子的最大因子……的最大质因子

zyxzyx。

风车呼呼呼 发表于 2022-5-26 23:42
答案代码：从大因子开始往回遍历，判断是否为质数，发现的第一个质数就是结果，并且直接break终止循环
你 ...

答案代码不也是从小因子开始的吗
也是先找因子在判断因子是不是质数

zyxzyx。

jhq999 发表于 2022-5-27 10:02
1、一个数的最小因子一定是质因子，最小因子对应的就是这个数的最大因子
2、一个数的最大因子的最大质 ...

那我的代码跟他那个答案代码的差距在哪里
求大佬解答
都是从小的数开始先找因子再判断因子是不是质数

jhq999

zyxzyx。 发表于 2022-5-27 10:35
那我的代码跟他那个答案代码的差距在哪里
求大佬解答
都是从小的数开始先找因子再判断因子是不是质数

这么大的数你从最小挨个取余试得啥时候去
上面的已经给你回答了
      

风车呼呼呼

zyxzyx。 发表于 2022-5-27 10:34
答案代码不也是从小因子开始的吗
也是先找因子在判断因子是不是质数

好好看看判断质数那块的代码。。。你判断的是 i ，人家判断的是 num/i

风共我

为什么我参考程序跑出来的结果是个合数啊

zyxzyx。

风共我 发表于 2022-6-5 10:53
为什么我参考程序跑出来的结果是个合数啊

他给的答案好像最后一步输出的变量写错了
我帖子上的是改过的答案