[已解决]带你学c带你飞测试题第2 题

不知君

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

int main()
{
        long long a,b,c,i;
        b=1;
        while(b!=600851475143)
        {
                a=2;
                i=1;
                for(;i<=a-1;i++,a++)
                {
                        if(a%i==0)
                        {
                                c=a;
                                b=b*a;
                        }
                }
        }
        printf("600851475143最大质数为%lld\n",c);
        return 0;
       
}
和小甲鱼的解题思路不同，但运行不了，想知道为啥

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2022-4-23 15:21:31

不知君 发表于 2022-4-23 17:20
大佬，就是这种情况，应该用怎么样的思路呢

反向思路，一般都会先判断因数，再判断是否为质数，这样做只会重复很多次同样的循环。
可以试试先找质数，从 2 开始，再判断是否是因数（与 600851475143 除整）便可。

1. #include <stdio.h>
   
2. 
   
3. int isPrime (int n) {
   
4.     if (n == 2 || n == 3) return 1;
   
5.     for (int i = 2; i * i < n; i++) {
   
6.         if (!(n % i)) return 0;
   
7.     }
   
8.     return 1;
   
9. }
   
10. 
    
11. int foo (long long n) {
    
12.     int prime = 2;
    
13.     while (n > 1) {
    
14.         while (!(n % prime)) {
    
15.             n /= prime;
    
16.         }
    
17.         if (n == 1) break;
    
18.         do {
    
19.             prime++;
    
20.         } while (!isPrime(prime));
    
21.     }
    
22.     return prime;
    
23. }
    
24. 
    
25. int main()
    
26. {
    
27.     printf("%d", foo(600851475143));
    
28. 
    
29.     return 0;
    
30. }
    

复制代码

跳转到最佳答案楼层

傻眼貓咪

不知君 发表于 2022-4-23 17:20
大佬，就是这种情况，应该用怎么样的思路呢

反向思路，一般都会先判断因数，再判断是否为质数，这样做只会重复很多次同样的循环。
可以试试先找质数，从 2 开始，再判断是否是因数（与 600851475143 除整）便可。

1. #include <stdio.h>
   
2. 
   
3. int isPrime (int n) {
   
4.     if (n == 2 || n == 3) return 1;
   
5.     for (int i = 2; i * i < n; i++) {
   
6.         if (!(n % i)) return 0;
   
7.     }
   
8.     return 1;
   
9. }
   
10. 
    
11. int foo (long long n) {
    
12.     int prime = 2;
    
13.     while (n > 1) {
    
14.         while (!(n % prime)) {
    
15.             n /= prime;
    
16.         }
    
17.         if (n == 1) break;
    
18.         do {
    
19.             prime++;
    
20.         } while (!isPrime(prime));
    
21.     }
    
22.     return prime;
    
23. }
    
24. 
    
25. int main()
    
26. {
    
27.     printf("%d", foo(600851475143));
    
28. 
    
29.     return 0;
    
30. }
    

复制代码

傻眼貓咪

首先，你先要明白为什么这么多数字不用，偏偏要用 600851475143 这个数字？
因为这个数字足够大，其质数因子也相当大，这表示一般算法肯定不通，循环肯定超时（你试想想，需要循环多少次？）

不知君

傻眼貓咪 发表于 2022-4-23 16:13
首先，你先要明白为什么这么多数字不用，偏偏要用 600851475143 这个数字？
因为这个数字足够大，其质数因 ...

大佬，就是这种情况，应该用怎么样的思路呢

yushenga

前来学习

不知君

傻眼貓咪 发表于 2022-4-23 17:42
反向思路，一般都会先判断因数，再判断是否为质数，这样做只会重复很多次同样的循环。
可以试试先找质 ...

好的