這段代碼爲什麼會進入無限循環

我是從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

這段代碼爲什麼會進入無限循環

回答

相關問題