[已解决]求最大质数因子

Mr.liuqingjun

#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),类似无反应这种情况，都有可能是什么原因导致的呢？

最佳答案

月排行榜 / 总排行榜

jackz007

2019-12-10 14:56:44

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

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. prime(long long n)
   
5. {
   
6.         long long k , p                                                                                 ;
   
7.         int r = 0                                                                                       ;
   
8.         if(n > 1) for(r = 1 , p = sqrt(n) , k = 2 ; k < p + 1 && r ; k ++) if(! (n % k) && k < n) r = 0 ;
   
9.         return r                                                                                        ;
   
10. }
    
11. 
    
12. main(void)
    
13. {
    
14.         long long d , k , m = 600851475143 , p                                                          ;
    
15.         for(d = 0 , p = sqrt(m) , k = 2 ; k < p + 1 ; k ++) if(! (m % k)){
    
16.                 if(prime(k) && k > d) d = k                                                             ;
    
17.                 if(prime(m / k) && m / k > d) d = m / k                                                 ;
    
18.         }
    
19.         printf("%lld\n" , d)                                                                            ;
    
20. }

复制代码

        编译、运行实况：

1. C:\Bin>g++ -o x x.c
   
2. 
   
3. C:\Bin>x
   
4. 6857
   
5. 
   
6. C:\Bin>

复制代码

        所以，最大质数因子就是：6857

跳转到最佳答案楼层

superbe

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

jackz007

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

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. prime(long long n)
   
5. {
   
6.         long long k , p                                                                                 ;
   
7.         int r = 0                                                                                       ;
   
8.         if(n > 1) for(r = 1 , p = sqrt(n) , k = 2 ; k < p + 1 && r ; k ++) if(! (n % k) && k < n) r = 0 ;
   
9.         return r                                                                                        ;
   
10. }
    
11. 
    
12. main(void)
    
13. {
    
14.         long long d , k , m = 600851475143 , p                                                          ;
    
15.         for(d = 0 , p = sqrt(m) , k = 2 ; k < p + 1 ; k ++) if(! (m % k)){
    
16.                 if(prime(k) && k > d) d = k                                                             ;
    
17.                 if(prime(m / k) && m / k > d) d = m / k                                                 ;
    
18.         }
    
19.         printf("%lld\n" , d)                                                                            ;
    
20. }

复制代码

        编译、运行实况：

1. C:\Bin>g++ -o x x.c
   
2. 
   
3. C:\Bin>x
   
4. 6857
   
5. 
   
6. C:\Bin>

复制代码

        所以，最大质数因子就是：6857