鱼C论坛

 找回密码
 立即注册
查看: 77|回复: 2

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

[复制链接]
最佳答案
0 
发表于 2019-12-8 21:37:56 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
#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),类似无反应这种情况,都有可能是什么原因导致的呢?
最佳答案
2019-12-10 14:56:44
本帖最后由 jackz007 于 2019-12-10 16:26 编辑

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

  3. prime(long long n)
  4. {
  5.         long long k , p                                                                                 ;
  6.         int r = 0                                                                                       ;
  7.         if(n > 1) for(r = 1 , p = sqrt(n) , k = 2 ; k < p + 1 && r ; k ++) if(! (n % k) && k < n) r = 0 ;
  8.         return r                                                                                        ;
  9. }

  10. main(void)
  11. {
  12.         long long d , k , m = 600851475143 , p                                                          ;
  13.         for(d = 0 , p = sqrt(m) , k = 2 ; k < p + 1 ; k ++) if(! (m % k)){
  14.                 if(prime(k) && k > d) d = k                                                             ;
  15.                 if(prime(m / k) && m / k > d) d = m / k                                                 ;
  16.         }
  17.         printf("%lld\n" , d)                                                                            ;
  18. }
复制代码

        编译、运行实况:
  1. C:\Bin>g++ -o x x.c

  2. C:\Bin>x
  3. 6857

  4. C:\Bin>
复制代码


        所以,最大质数因子就是:6857
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
131 
发表于 2019-12-9 21:00:21 | 显示全部楼层
while(i < j){
                if(j % i == 0){
                        j = j / i;
                        k = j;
                        //i = 1;  //这一行不要
                }
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
1049 
发表于 2019-12-10 14:56:44 | 显示全部楼层    本楼为最佳答案   
本帖最后由 jackz007 于 2019-12-10 16:26 编辑

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

  3. prime(long long n)
  4. {
  5.         long long k , p                                                                                 ;
  6.         int r = 0                                                                                       ;
  7.         if(n > 1) for(r = 1 , p = sqrt(n) , k = 2 ; k < p + 1 && r ; k ++) if(! (n % k) && k < n) r = 0 ;
  8.         return r                                                                                        ;
  9. }

  10. main(void)
  11. {
  12.         long long d , k , m = 600851475143 , p                                                          ;
  13.         for(d = 0 , p = sqrt(m) , k = 2 ; k < p + 1 ; k ++) if(! (m % k)){
  14.                 if(prime(k) && k > d) d = k                                                             ;
  15.                 if(prime(m / k) && m / k > d) d = m / k                                                 ;
  16.         }
  17.         printf("%lld\n" , d)                                                                            ;
  18. }
复制代码

        编译、运行实况:
  1. C:\Bin>g++ -o x x.c

  2. C:\Bin>x
  3. 6857

  4. C:\Bin>
复制代码


        所以,最大质数因子就是:6857
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐上一条 /1 下一条

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号

GMT+8, 2020-1-22 07:08

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表