[已解决]小甲鱼的C第一阶段考察的超大数做质因子分解，为啥时间很长？

texttext

原题是求解600851475143的最大质数因子， 我的代码如下：

这段代码在数字不是很大的时候，比如7位数，还是可以运行的。但是一旦超过7位数，就不行了。 但是小甲鱼说如果3秒钟不出答案，肯定就不对。 那位大神指点一下，代码有什么问题？



long long number = 851143;
long long maxfactor = 1;
_Bool flag = 1;

for (long long i = 2; i < number; i++)
{

        if (number % i == 0)
        {
            flag = 1;
            
        
        for (long long j = 2; j <= sqrt(i); j++)
        {
            if (i % j == 0)
            {
                flag = 0; //i is not a prime factor
                break;
            }
        }
        
        if (flag) //prime factor
            {
               
                if (i >= maxfactor)
                {
                    maxfactor = i;
                }
            }
        }
   
}
printf("max prime factor is %d\n", maxfactor);

最佳答案

月排行榜 / 总排行榜

jackz007

2022-10-18 11:23:00

        因为这个数超过了 int 的表达范围，所以，需要全程改用 long long。

1. #include <stdio.h>
   
2. 
   
3. int main(void)
   
4. {
   
5.         unsigned long long c , d , k , n                        ;
   
6.         n = 600851475143                                        ;
   
7.         for(c = 0 , d = n , k = 2 ; k * k < d + 1 ;) {
   
8.                 if(! (d % k)) {
   
9.                         if(! c) printf("%I64u = %I64u" , n , k) ;
   
10.                         else printf(" x %I64u" , k)             ;
    
11.                         d /= k                                  ;
    
12.                         c ++                                    ;
    
13.                 } else {
    
14.                         k ++                                    ;
    
15.                 }
    
16.         }
    
17.         if(! c) printf("%I64u is a prime .\n" , n)              ;
    
18.         else printf(" x %I64u\n" , d)                           ;
    
19. }

复制代码

        编译、运行实况：

1. D:\[00.Exerciese.2022]\C>g++ -o x x.c
   
2. 
   
3. D:\[00.Exerciese.2022]\C>x
   
4. 600851475143 = 71 x 839 x 1471 x 6857
   
5. 
   
6. D:\[00.Exerciese.2022]\C>

复制代码

       这个代码确实很快，确实要不了 3 秒钟

跳转到最佳答案楼层

jackz007

        因为这个数超过了 int 的表达范围，所以，需要全程改用 long long。

1. #include <stdio.h>
   
2. 
   
3. int main(void)
   
4. {
   
5.         unsigned long long c , d , k , n                        ;
   
6.         n = 600851475143                                        ;
   
7.         for(c = 0 , d = n , k = 2 ; k * k < d + 1 ;) {
   
8.                 if(! (d % k)) {
   
9.                         if(! c) printf("%I64u = %I64u" , n , k) ;
   
10.                         else printf(" x %I64u" , k)             ;
    
11.                         d /= k                                  ;
    
12.                         c ++                                    ;
    
13.                 } else {
    
14.                         k ++                                    ;
    
15.                 }
    
16.         }
    
17.         if(! c) printf("%I64u is a prime .\n" , n)              ;
    
18.         else printf(" x %I64u\n" , d)                           ;
    
19. }

复制代码

        编译、运行实况：

1. D:\[00.Exerciese.2022]\C>g++ -o x x.c
   
2. 
   
3. D:\[00.Exerciese.2022]\C>x
   
4. 600851475143 = 71 x 839 x 1471 x 6857
   
5. 
   
6. D:\[00.Exerciese.2022]\C>

复制代码

       这个代码确实很快，确实要不了 3 秒钟

texttext

jackz007 发表于 2022-10-18 11:23
因为这个数超过了 int 的表达范围，所以，需要全程改用 long long。

        编译、运行实况：
...

编译器能给个提示，数字太大内存溢出就好了