Mr.liuqingjun 发表于 2019-12-8 21:37:56

求最大质数因子

#include<stdio.h>
main (){
       long long int i,j,k;
        j = 600851475143;
        i = 2;
        k = 1;
        while(i < j){
                if(j % i == 0){
                        j = j / i;
                        k = j;
                        i = 1;
                }
                else{
                        i ++;
                }
        }
        printf("%lld",k);


        return 0;
}
请问各位鱼友，这样求最大质数因子有什么问题吗？为啥运行后cmd窗口只有一个下划线再闪没有任何其他反应（vc2010),类似无反应这种情况，都有可能是什么原因导致的呢？

superbe 发表于 2019-12-9 21:00:21

while(i < j){
                if(j % i == 0){
                        j = j / i;
                        k = j;
                        //i = 1;//这一行不要
                }

jackz007 发表于 2019-12-10 14:56:44

本帖最后由 jackz007 于 2019-12-10 16:26 编辑

      楼主这样写代码非常浪费资源，我试了一下，光 0 ～ 600851475143 的空循环都要跑 40 分钟以上， 更何况还有其它操作，非常的耗费时间。
      既然是找乘法因子，为什么不可以通过循环在 2 ~ sqrt(600851475143) 的范围内找？假设在此范围内找到一个因子 k，那么600851475143 / k 也同时是因子，当循环完成的时候，会枚举到 600851475143 的每一个乘法因子，并不会遗漏任何一个。这样操作，循环次数会大幅度减少，代码效率会显著提高，而需要寻找的目标数可以在瞬间被找到。
#include <stdio.h>
#include <math.h>

prime(long long n)
{
      long long k , p                                                                                 ;
      int r = 0                                                                                       ;
      if(n > 1) for(r = 1 , p = sqrt(n) , k = 2 ; k < p + 1 && r ; k ++) if(! (n % k) && k < n) r = 0 ;
      return r                                                                                        ;
}

main(void)
{
      long long d , k , m = 600851475143 , p                                                          ;
      for(d = 0 , p = sqrt(m) , k = 2 ; k < p + 1 ; k ++) if(! (m % k)){
                if(prime(k) && k > d) d = k                                                             ;
                if(prime(m / k) && m / k > d) d = m / k                                                 ;
      }
      printf("%lld\n" , d)                                                                            ;
}
      编译、运行实况：
C:\Bin>g++ -o x x.c

C:\Bin>x
6857

C:\Bin>

      所以，最大质数因子就是：6857
页: [1]
查看完整版本: 求最大质数因子