[已解决]请大神们帮忙看看这个程序一直不停运行并且不输出结果是哪里出了问题

王尧

#include <stdio.h>
int main()
{
    long long a = 600851475143,b,c,num = 0;
    for(b = 2;b < a/2;b++)
    {
        if(!(a%b))
        {
            for(c = 2;c <= b/2;c++)
            {
                if(!(b%c))
                {
                    break;
                }
                else if(c == b/2 && b > num)
                {
                    num = b;
                }
            }
        }
    }
    printf("600851475143的最大质数因子是:%lld\n",num);
    return 0;
}

最佳答案

月排行榜 / 总排行榜

Croper

2019-5-3 10:46:00

楼主的方法时间复杂度太高了，
试试这个吧，应该是秒算的

1. #include <stdio.h>
   
2. #include <math.h>
   
3. #define MAX_PRIME_COUNT 100000
   
4. 
   
5. int prime(int);
   
6. int isprime(int);
   
7. 
   
8. int prime(int n){
   
9.         if (n>MAX_PRIME_COUNT) return -1;
   
10.         static int nums[MAX_PRIME_COUNT]={2};
    
11.         static int size=1;
    
12.         while (n>=size){
    
13.                 nums[size]=nums[size-1];
    
14.                 while (!isprime(++nums[size]));
    
15.                 ++size;
    
16.         }
    
17.         return nums[n];
    
18. }
    
19. 
    
20. int isprime(int num){
    
21.         int i;
    
22.         int s=sqrt(num);
    
23.         for (i=0;prime(i)<=s;++i){
    
24.                 if (num % prime(i)==0) return 0;
    
25.         }
    
26.         return 1;
    
27. }
    
28. 
    
29. int maxprimefactor(long long a){
    
30.         int ret=1;
    
31.         int isprime=0;
    
32.         while (!isprime){
    
33.                 int i;
    
34.                 int s=sqrt(a);
    
35.                 isprime=1;
    
36.                 for (i=0;prime(i)<=s;++i){
    
37.                         if (a % prime(i)==0){
    
38.                                 if (ret<prime(i)) ret=prime(i);
    
39.                                 a/=prime(i);
    
40.                                 isprime=0;
    
41.                                 //printf("%d ",prime(i));
    
42.                                 break;
    
43.                         }
    
44.                 }
    
45.         }
    
46.         if (ret<a) ret=a;
    
47.         return ret;
    
48. }
    
49. 
    
50. int main(){
    
51.         long long a=600851475143;
    
52.         int b=maxprimefactor(a);
    
53.         printf("%lld的最大质因数是%d",a,b);
    
54. }

复制代码

跳转到最佳答案楼层

ba21

不可否认你的电脑是超级计算机。
搞个小点的数先试吧。要不然就想办法优化代码

王尧

是因为数字太大了？ 小一点的数完全没问题的

bin554385863

楼主的代码我的电脑最多只能算到10亿，再多一个零都不行

wrpython

不知道~坐等别人来解答~

Croper

楼主的方法时间复杂度太高了，
试试这个吧，应该是秒算的

1. #include <stdio.h>
   
2. #include <math.h>
   
3. #define MAX_PRIME_COUNT 100000
   
4. 
   
5. int prime(int);
   
6. int isprime(int);
   
7. 
   
8. int prime(int n){
   
9.         if (n>MAX_PRIME_COUNT) return -1;
   
10.         static int nums[MAX_PRIME_COUNT]={2};
    
11.         static int size=1;
    
12.         while (n>=size){
    
13.                 nums[size]=nums[size-1];
    
14.                 while (!isprime(++nums[size]));
    
15.                 ++size;
    
16.         }
    
17.         return nums[n];
    
18. }
    
19. 
    
20. int isprime(int num){
    
21.         int i;
    
22.         int s=sqrt(num);
    
23.         for (i=0;prime(i)<=s;++i){
    
24.                 if (num % prime(i)==0) return 0;
    
25.         }
    
26.         return 1;
    
27. }
    
28. 
    
29. int maxprimefactor(long long a){
    
30.         int ret=1;
    
31.         int isprime=0;
    
32.         while (!isprime){
    
33.                 int i;
    
34.                 int s=sqrt(a);
    
35.                 isprime=1;
    
36.                 for (i=0;prime(i)<=s;++i){
    
37.                         if (a % prime(i)==0){
    
38.                                 if (ret<prime(i)) ret=prime(i);
    
39.                                 a/=prime(i);
    
40.                                 isprime=0;
    
41.                                 //printf("%d ",prime(i));
    
42.                                 break;
    
43.                         }
    
44.                 }
    
45.         }
    
46.         if (ret<a) ret=a;
    
47.         return ret;
    
48. }
    
49. 
    
50. int main(){
    
51.         long long a=600851475143;
    
52.         int b=maxprimefactor(a);
    
53.         printf("%lld的最大质因数是%d",a,b);
    
54. }

复制代码

HUMMER军

1. /*
   
2. 你这个题目的原型是质因数分解
   
3. 输入90,打印出90=2*3*3*5。
   
4. 代码如下
   
5. */
   
6. #include <stdio.h>
   
7. int main()
   
8. {
   
9.     int n,k;
   
10.     printf("请输入一个正整数：");
    
11.     scanf("%d",&n);
    
12.    
    
13.     printf("%d=",n);
    
14.    
    
15.     for(k=2;k<=n;k++)
    
16.     {
    
17.         while(n%k==0)
    
18.         {
    
19.             printf("%d",k);
    
20.             n=n/k;
    
21.             if(n!=1)
    
22.             {
    
23.                 printf("*");
    
24.             }
    
25.         }
    
26.         
    
27.     }
    
28.     printf("\n");
    
29.     return 0;
    
30. }
    
31. 
    
32. /*
    
33. 输出结果：
    
34. 请输入一个正整数：90
    
35. 90=2*3*3*5
    
36. */

复制代码

1. /*
   
2. 对上面的程序加以改进，只输出最后一个质因数即可
   
3. */
   
4. 
   
5. #include <stdio.h>
   
6. int main()
   
7. {
   
8.     long long int n,t,k;
   
9.     printf("请输入一个正整数：");
   
10.     scanf("%lld",&n);
    
11.     t=n;
    
12.    
    
13.     //printf("%d=",n);
    
14.    
    
15.     for(k=2;k<=n;k++)
    
16.     {
    
17.         while(n%k==0)
    
18.         {
    
19.             //printf("%d",k);
    
20.             n=n/k;
    
21.             if(n==1)
    
22.             {
    
23.                 printf("%lld的最大质因数是%lld\n",t,k);
    
24.             }
    
25.         }
    
26.         
    
27.     }
    
28.     return 0;
    
29. }
    
30. 
    
31. /*
    
32. 请输入一个正整数：90
    
33. 90的最大质因数是5
    
34. */

复制代码

HUMMER军

我提供的方法应该复杂度应该能接受吧！
每一次分解出来的质因数，都不会比前一个大！
比如输入90
第一次判断范围是在2-90之间，质因数是2
第二次判断范围在2-90/2（2-45）之间，质因数是3
第三次判断范围在2-45/3（2-15）之间，质因数是3
第四次判断范围在2-15/3（2-5）之间，质因数是5

王尧

Croper 发表于 2019-5-3 10:46
楼主的方法时间复杂度太高了，
试试这个吧，应该是秒算的

这个程序能计算出结果，但是代码有点看不懂。。。。。。这是第一段考核的题目。