[已解决]小甲鱼的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。

#include <stdio.h>

int main(void)
{
        unsigned long long c , d , k , n                        ;
        n = 600851475143                                        ;
        for(c = 0 , d = n , k = 2 ; k * k < d + 1 ;) {
                if(! (d % k)) {
                        if(! c) printf("%I64u = %I64u" , n , k) ;
                        else printf(" x %I64u" , k)             ;
                        d /= k                                  ;
                        c ++                                    ;
                } else {
                        k ++                                    ;
                }
        }
        if(! c) printf("%I64u is a prime .\n" , n)              ;
        else printf(" x %I64u\n" , d)                           ;
}

        编译、运行实况：

D:\[00.Exerciese.2022]\C>g++ -o x x.c

D:\[00.Exerciese.2022]\C>x
600851475143 = 71 x 839 x 1471 x 6857

D:\[00.Exerciese.2022]\C>

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

跳转到最佳答案楼层

jackz007

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

#include <stdio.h>

int main(void)
{
        unsigned long long c , d , k , n                        ;
        n = 600851475143                                        ;
        for(c = 0 , d = n , k = 2 ; k * k < d + 1 ;) {
                if(! (d % k)) {
                        if(! c) printf("%I64u = %I64u" , n , k) ;
                        else printf(" x %I64u" , k)             ;
                        d /= k                                  ;
                        c ++                                    ;
                } else {
                        k ++                                    ;
                }
        }
        if(! c) printf("%I64u is a prime .\n" , n)              ;
        else printf(" x %I64u\n" , d)                           ;
}

        编译、运行实况：

D:\[00.Exerciese.2022]\C>g++ -o x x.c

D:\[00.Exerciese.2022]\C>x
600851475143 = 71 x 839 x 1471 x 6857

D:\[00.Exerciese.2022]\C>

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

texttext

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

        编译、运行实况：
...

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