这段代码为什么会进入无限循环

我是从3到2147483647运行的for循环（+已经长整型的限制）。

但这个代码挂起，无法找出原因？

#include<time.h> 
#include<stdio.h> 
int isPrime1(long t) 
{ 
    long i; 
    if(t==1) return 0; 
    if(t%2==0) return 0; 
    for(i=3;i<t/2;i+=2) 
    { 
     if(t%i==0) return 0; 
    } 
    return 1; 
} 
int main() 
{ 
    long i=0; 
    time_t s,e; 

    s = time(NULL); 
    for(i=3; i<2147483647; i++) 
    { 
     isPrime1(i); 
    } 
    e = time(NULL); 
    printf("\n\t Time : %ld secs", e - s); 
    return 0; 
}

来源

2013-04-21 VishalDevgire

你确定它确实挂起，它不是，它只是需要很长的时间来执行？ – FatalError 2013-04-21 16:32:16

你确定它实际上被困在一个循环中，而不仅仅是很长的执行？ – Thibaut 2013-04-21 16:32:28

我不认为这是一个无限循环。你只需要超过2147483647循环，就是这样。太重了 – 2013-04-21 16:32:39

它最终会终止，但是当你内嵌的isPrime1功能将需要一段时间，如果你看看你的循环，你有这样的：

for(i=3; i<2147483647; i++) 
    for(j=3;j<i/2;j+=2)

这大概是N * N/4 = O（n^2）。你的循环计数太高。

来源

2013-04-21 16:36:04 Thibaut

这里试试这个，看看它是否真的无限循环

int main() 
{ 
    long i=0; 
    time_t s,e; 

    s = time(NULL); 
    for(i=3; i<2147483647; i++) 
    { 
     isPrime1(i); 

     //calculate the time execution for each loop 
     e = time(NULL); 
     printf("\n\t Time for loop %d: %ld secs", i, e - s); 
    } 

    return 0; 
}

来源

2013-04-21 16:36:24

这取决于系统和编译器。在Linux上，使用GCC 4.7.2并编译为gcc -O2 vishaid.c -o vishaid程序立即返回，并且编译器通过删除它们（我检查生成的汇编代码为gcc -O2 -S -fverbose-asm，然后main甚至不称为isPrime1）优化了所有对isPrime1的调用。 GCC是正确的：由于isPrime1没有副作用，其结果没有被使用，它的呼叫可以被删除。然后for循环有一个空体，所以也可以优化。

^{学习的教训是，基准优化的二进制代码时，你最好在你的代码中的一些真正的副作用。}

此外，算术告诉我们，如果一个i没有小于其平方根的因子，那么它就是素数。所以，更好的代码：

int isPrime1(long t) { 
    long i; 
    double r = sqrt((double)t); 
    long m = (long)r; 
    if(t==1) return 0; 
    if(t%2==0) return 0; 
    for(i=3;i <= m;i +=2) 
    if(t%i==0) return 0; 
    return 1; 
}

在我的系统（X86-64 /于Debian /希德与酷睿i7 3770K基于英特尔处理器上运行该程序的核心是在3.5GHz的）long -s是64位。所以我编写

int main() 
{ 
    long i = 0; 
    long cnt = 0; 
    time_t s, e; 

    s = time (NULL); 
    for (i = 3; i < 2147483647; i++) 
    { 
     if (isPrime1 (i) && (++cnt % 4096) == 0) { 
     printf ("#%ld: %ld\n", cnt, i); 
     fflush (NULL); 
     } 
    } 
    e = time (NULL); 
    printf ("\n\t Time : %ld secs\n", e - s); 
    return 0; 
}

约4分钟后，它仍然大量印线，包括

#6819840: 119566439 
#6823936: 119642749 
#6828032: 119719177 
#6832128: 119795597

我猜它可能需要几个小时才能完成。 30分钟后，它仍然是随地吐痰（慢）

#25698304: 486778811 
#25702400: 486862511 
#25706496: 486944147 
#25710592: 487026971

实际上，该方案4根据需要小时16分钟完成。最后输出是

#105086976: 2147139749 
#105091072: 2147227463 
#105095168: 2147315671 
#105099264: 2147402489 

    Time : 15387 secs

顺便说一句，该程序仍然是真正的低效率：本primes程序/usr/games/primes从bsdgames包应答更快

% time /usr/games/primes 1 2147483647 | tail 
2147483423 
2147483477 
2147483489 
2147483497 
2147483543 
2147483549 
2147483563 
2147483579 
2147483587 
2147483629 
/usr/games/primes 1 2147483647 
    10.96s user 0.26s system 99% cpu 11.257 total

和它仍然印刷105097564线（最感通过tail跳过）

如果你有兴趣的素数生成，读几微米ath书（如果你对效率感兴趣，它仍然是一个研究课题;你仍然可以获得关于该主题的博士学位）。从Wikipedia上的sieve of erasthothenes和primality test页开始。

最重要的是，首先编译程序调试信息和所有警告（即gcc -Wall -g在Linux上），学会使用调试（即gdb在Linux上）。然后，您可以打断你的调试计划（Ctrl-Cgdb下，然后让它与cont命令继续gdb）后约一分钟，二，然后观察，在主要的i计数器是缓慢增加。也许还需要分析信息（-pg选项为gcc，然后使用gprof）。当编码复杂的算术事物时，阅读有关它们的优秀数学书籍是非常值得的（并且素数测试是一个非常复杂的主题，是大多数密码算法的核心）。

来源

2013-04-21 16:36:55

这只是发生，因为他在这种情况下没有对返回值做任何事情，因为它是一个最小的例子。对于一个真正的程序，他可能对返回值感兴趣;） – Thibaut 2013-04-21 16:38:56

我知道这一点，但我想吸引原始海报到一些关于优化和基准测试的有趣点。 – 2013-04-21 17:18:37

这是测试一个素数非常低效的方法，这就是为什么它似乎挂起。在网上搜索更高效的算法，如埃拉托色尼的筛

来源

2013-04-21 16:39:09

这段代码为什么会进入无限循环

回答

相关问题