论坛 › C\C++交流 › 请问小甲鱼出的这个题的参考代码是不是错了

dogdoggodlike 发表于 2023-4-5 17:27:26

请问小甲鱼出的这个题的参考代码是不是错了

#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，然而这个数不属于质数，它是由71,839,1471相乘而来.
//题目是求600851475143 的最大质数因子（本人萌新，大佬勿喷）

isdkz 发表于 2023-4-5 17:40:07

确实，这个代码的答案是错误的。这里提供一个修改后的正确的代码：

#include <stdio.h>
#include <math.h>

int main() {
    long long num = 600851475143;
    long long maxPrimeFactor = 0;
    long long i;

    // 对2进行特殊处理
    while (num % 2 == 0) {
      maxPrimeFactor = 2;
      num /= 2;
    }

    // 处理其他奇数因子
    for (i = 3; i <= sqrt(num); i += 2) {
      while (num % i == 0) {
            maxPrimeFactor = i;
            num /= i;
      }
    }

    // 如果num大于2，说明num是一个大于sqrt(num)的质数
    if (num > 2) {
      maxPrimeFactor = num;
    }

    printf("%lld\n", maxPrimeFactor);

    return 0;
}

这个代码会得到正确的答案：6857。这是因为600851475143的质数因子是71、839、1471和6857，而最大的质数因子是6857。

歌者文明清理员 发表于 2023-4-5 17:57:11

@小甲鱼 @不二如是

小甲鱼 发表于 2023-4-5 20:31:26

这是第几节课的题目呢？

我找了一圈没有看到这道题丫？

sfqxx 发表于 2023-4-5 20:37:02

小甲鱼 发表于 2023-4-5 20:31
这是第几节课的题目呢？

我找了一圈没有看到这道题丫？

热乎的{:10_256:}

dogdoggodlike 发表于 2023-4-5 20:50:22

小甲鱼 发表于 2023-4-5 20:31
这是第几节课的题目呢？

我找了一圈没有看到这道题丫？

带你学c带你飞第一阶段考核题的答案

小甲鱼 发表于 2023-4-5 20:53:43

dogdoggodlike 发表于 2023-4-5 20:50
带你学c带你飞第一阶段考核题的答案

感谢指出，已经修正~

小甲鱼 发表于 2023-4-5 20:55:34

sfqxx 发表于 2023-4-5 20:37
热乎的

{:9_227:}

查看完整版本: 请问小甲鱼出的这个题的参考代码是不是错了