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

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

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

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. int main() {
   
5.     long long num = 600851475143;
   
6.     long long maxPrimeFactor = 0;
   
7.     long long i;
   
8. 
   
9.     // 对2进行特殊处理
   
10.     while (num % 2 == 0) {
    
11.         maxPrimeFactor = 2;
    
12.         num /= 2;
    
13.     }
    
14. 
    
15.     // 处理其他奇数因子
    
16.     for (i = 3; i <= sqrt(num); i += 2) {
    
17.         while (num % i == 0) {
    
18.             maxPrimeFactor = i;
    
19.             num /= i;
    
20.         }
    
21.     }
    
22. 
    
23.     // 如果num大于2，说明num是一个大于sqrt(num)的质数
    
24.     if (num > 2) {
    
25.         maxPrimeFactor = num;
    
26.     }
    
27. 
    
28.     printf("%lld\n", maxPrimeFactor);
    
29. 
    
30.     return 0;
    
31. }
    

复制代码

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

跳转到最佳答案楼层

isdkz

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

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. int main() {
   
5.     long long num = 600851475143;
   
6.     long long maxPrimeFactor = 0;
   
7.     long long i;
   
8. 
   
9.     // 对2进行特殊处理
   
10.     while (num % 2 == 0) {
    
11.         maxPrimeFactor = 2;
    
12.         num /= 2;
    
13.     }
    
14. 
    
15.     // 处理其他奇数因子
    
16.     for (i = 3; i <= sqrt(num); i += 2) {
    
17.         while (num % i == 0) {
    
18.             maxPrimeFactor = i;
    
19.             num /= i;
    
20.         }
    
21.     }
    
22. 
    
23.     // 如果num大于2，说明num是一个大于sqrt(num)的质数
    
24.     if (num > 2) {
    
25.         maxPrimeFactor = num;
    
26.     }
    
27. 
    
28.     printf("%lld\n", maxPrimeFactor);
    
29. 
    
30.     return 0;
    
31. }
    

复制代码

这个代码会得到正确的答案：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
热乎的