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

lethez

求解一个问题：[阶段考核] 第一阶段考核（考核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;
}

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