lethez 发表于 2019-11-13 17:42:08

程序编译未报错，数字小可正常执行，数字大hang住

求解一个问题：[阶段考核] 第一阶段考核（考核S1E1~S1E16知识点）第二题

以下是我的代码，当数字小时执行无误，当按题目给的数字执行时，会hang住，不知道是什么原因？


#include <stdio.h>
#include <math.h>

//#define NUM 600851475143

int main()
{
      long long i,max=0,j,NUM = 600851475143;
      _Bool value;
      for (i=2;i<NUM/2;i++)
      {
                if (NUM % i == 0)
                {
                        for (j=2;j<=sqrt((double)i);j++)
                        {
                              if (i % j == 0)
                              {
                                        value = 0;
                                        break;
                              }
                              else
                                        value = 1;
                        }
                        if (value)
                        {
                              max = max > i ? max : i;
                        }
                }
      }
      
      printf("max prime factor = %lld\n",max);
      
      
      return 0;
}



--- SIGWINCH {si_signo=SIGWINCH, si_code=SI_KERNEL} ---

jackz007 发表于 2019-11-13 18:17:10

   楼主，你应该交代一下，这道题要干啥？

lethez 发表于 2019-11-14 10:49:24

2. 编写一个程序，求解 600851475143 的最大质数因子是多少？
每个合数都可以写成几个质数（素数）相乘的形式，这几个质数就都叫做这个合数的质数因子。
比如 13195 的质数因子有 5, 7, 13 和 29。

lethez 发表于 2019-11-14 10:52:11

jackz007 发表于 2019-11-13 18:17
楼主，你应该交代一下，这道题要干啥？

谢谢提醒~

2164930278 发表于 2019-11-16 09:39:54

代码写的挺好的，看不出有什么错误！

荣耀 发表于 2019-11-24 10:45:28

循环中的循环

D小小贱 发表于 2019-11-24 13:31:22

我看的时候就是一脸懵逼{:10_249:}

Croper 发表于 2019-11-24 14:18:47

本帖最后由 Croper 于 2019-11-24 14:42 编辑

楼主你这时间复杂度是O，太高了啊。
自己算一算，N=600851475143时你需要循环164666670424947200次；
如果每次循环需要0.1微秒,那么计算需要耗时16466667042秒，
合190586天，大概是522年。

等你算出来三体舰队已经到地球了。。
所以你还是优化下你的算法吧，

bin554385863 发表于 2019-11-24 14:26:21

Croper 发表于 2019-11-24 14:18
楼主你这时间复杂度是O，太高了啊。
自己算一算，N=600851475143时你需要循环164666670424947200次 ...

子子孙孙无穷匮焉，总有算出的一天>_<

lethez 发表于 2019-11-30 15:15:52

Croper 发表于 2019-11-24 14:18
楼主你这时间复杂度是O，太高了啊。
自己算一算，N=600851475143时你需要循环164666670424947200次 ...

已经优化了，前几天没看， 谢谢噢~

lethez 发表于 2019-11-30 15:23:16

另外这一题，小甲鱼的答案不对，87625999不是质数，正确答案应该是6857
页: [1]
查看完整版本: 程序编译未报错，数字小可正常执行，数字大hang住