论坛 › 新手乐园 › 关于小甲鱼阶段考核测试答案中代码结果不正确讨论

fuaowei 发表于 2023-2-15 14:05:09

关于小甲鱼阶段考核测试答案中代码结果不正确讨论

本题目要求是求出6008514751432的最大质子因数，小甲鱼代码如下：

#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;
}

该代码结果87625999，对该数进行质数检查，结果检查得出该数不是一个质数，即不满足题目要求；

其实按照数学逻辑来讲是不需要对除数做一个质数判断的，上述代码出发点存在一定的问题，首先我们定义的计数器'i'也就是除数是从2这个数开始递增的，初始化数2本身属于一个质数，当判断num%2！=0时，其实我们已经可以得到结论，该数没有质数因子2，当num%3！=0时，同样得到结论，该数没有质数因子3。由此我们发现假如一个num没有质数因子2和3时，那么必然有num%(2^n*3^n)！=0(n为自然数)。

因此我们对num直接从2递增循环做余数判断，如果余数为0，即证明i为其因数，并临时存贮num/(i^n)和i的结果，循环相除，所有因数被除以后，直到得到最后的num=1，那么他的上一次存贮的i即为最大质数因子；代码如下：
#include<stdio.h>
#include<math.h>

int main()
{
        long long num=600851475143,temp;
        double j;
        int k=1;
       
        j=pow(num,0.5);
       
        for(int i=2;i<=j;i++)
        {
                if(num%i==0)
                {
                        temp=i;
                        while(!(num%i))
                        {
                                num=num/i;
                        }
                }
        }
        printf("%d\n",temp);
       
        return 0;
       
}

查看完整版本: 关于小甲鱼阶段考核测试答案中代码结果不正确讨论