texttext 发表于 2022-10-18 11:04:45

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

本帖最后由 texttext 于 2022-10-18 11:22 编辑

原题是求解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

本帖最后由 jackz007 于 2022-10-18 11:35 编辑

      因为这个数超过了 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:\\C>g++ -o x x.c

D:\\C>x
600851475143 = 71 x 839 x 1471 x 6857

D:\\C>
       这个代码确实很快，确实要不了 3 秒钟

texttext 发表于 2022-10-18 11:32:09

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

      编译、运行实况：
...

编译器能给个提示，数字太大内存溢出就好了 {:5_94:}
页: [1]
查看完整版本: 小甲鱼的C第一阶段考察的超大数做质因子分解，为啥时间很长？