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

lethez

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

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

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. //#define NUM 600851475143
   
5. 
   
6. int main()
   
7. {
   
8.         long long i,max=0,j,NUM = 600851475143;
   
9.         _Bool value;
   
10.         for (i=2;i<NUM/2;i++)
    
11.         {
    
12.                 if (NUM % i == 0)
    
13.                 {
    
14.                         for (j=2;j<=sqrt((double)i);j++)
    
15.                         {
    
16.                                 if (i % j == 0)
    
17.                                 {
    
18.                                         value = 0;
    
19.                                         break;
    
20.                                 }
    
21.                                 else
    
22.                                         value = 1;
    
23.                         }
    
24.                         if (value)
    
25.                         {
    
26.                                 max = max > i ? max : i;
    
27.                         }
    
28.                 }
    
29.         }
    
30.       
    
31.         printf("max prime factor = %lld\n",max);
    
32.       
    
33.       
    
34.         return 0;
    
35. }

复制代码

strace查看

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

jackz007

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

lethez

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

lethez

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

谢谢提醒~

2164930278

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

荣耀

循环中的循环

D小小贱

我看的时候就是一脸懵逼

Croper

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

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

bin554385863

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

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

lethez

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

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

lethez

另外这一题，小甲鱼的答案不对，87625999不是质数，正确答案应该是6857