[已解决]请问小甲鱼出的这个题的参考代码是不是错了

dogdoggodlike

#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。

跳转到最佳答案楼层

isdkz

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

#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。

歌者文明清理员

@小甲鱼 @不二如是

小甲鱼

这是第几节课的题目呢？

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

sfqxx

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

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

热乎的

dogdoggodlike

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

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

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

小甲鱼

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

感谢指出，已经修正~

小甲鱼

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