我的代碼在特定條件下停止

Question

在此代碼中，我輸入一個測試用例編號t，然後輸入t個數字（n）。然後我的代碼打印第n個素數。在函數的第一行中，prime（），如果我寫if(a > 43000) return;然後代碼完美地工作。但是如果我在同一個地方寫if(a >= 165000) return;，codeblocks說該程序已停止工作。但我不明白爲什麼。

#include <iostream> 
#include <cmath> 
using namespace std; 
int p[15000]; 
void prime(int a, int i) 
{ 
    if(a >= 165000) return; 
    else { 
     int q = 0; 
     int s=sqrt(a), d=3; 
     while(d<=s){ 
      if(a % d == 0) { 
       q = 1; 
      } 
      d += 2; 
     } 
     if(q == 0) { 
      p[i] = a; 
      i++; 
      a += 2; 
      prime(a, i); 
     } 
     else { 
      a += 2; 
      prime(a, i); 
     } 
    } 
} 
int main() 
{ 
    p[0]=2; 
    prime(3, 1); 
    int k, T; 
    cin >> T; 
    for(int i = 1; i <= T; i++){ 
     cin >> k; 
     cout << p[k - 1] << endl; 
    } 
    return 0; 
} 

Answer 1

首先，我要指出的是，你的陣列p只有15000元，而且15001個素數是163847。這意味着如果您在退出之前檢查a >= 165000，最終會嘗試填充數組範圍之外的索引。

其次，每個人都很正確，你應該小心做遞歸。對於每次運行prime()，您將爲5個新整數變量a,i,q, s和d分配空間。這意味着當你從你的方法的外觀上看，你正在爲成千上萬的整數分配內存。

因爲它看起來像這些值是獨立於所有其他迭代的，所以你可以使用情侶技巧。首先，對於q，s和d，將它們聲明爲全局變量，它們只會被分配一次。其次，通過將prime(int a, int i)更改爲prime(int &a, int &i)，您不會爲每個循環分配a和i的內存。這將更改您的代碼如下所示：

#include <iostream> 
#include <cmath> 
using namespace std; 

const int max_size = 15000 ; 
int p[max_size]; 
int q ; 
int s ; 
int d ; 

void prime(int &a, int &i) 
{ 
    if (i>=max_size) return ; 

    q = 0; 
    s=sqrt(a) ; 
    d=3; 

    while(d<=s){ 
     if(a % d == 0) { 
      q = 1; 
     } 
     d += 2; 
    } 
    if(q == 0) { 
     p[i] = a; 
     i++; 
     a += 2; 
     prime(a, i); 
    } 
    else { 
     a += 2; 
     prime(a, i); 
    } 

} 

int main() 
{ 
    p[0]=2; 
    int a(3), i(1) ; 
    prime(a, i); 
    int k, T; 
    cin >> T; 
    for(int i = 1; i <= T; i++){ 
     cin >> k; 
     // You should do a check of whether k is larger than 
     // the size of your array, otherwise the check on p[k-1] 
     // will cause a seg fault. 
     if (k>max_size) { 
      std::cout << "That value is too large, try a number <= " << max_size << "." << std::endl; 
     } else { 
      cout << p[k - 1] << endl; 
     } 
    } 

    return 0; 
} 

一對夫婦的其他變化：

• ，而不是填充數組，直到你達到一個特定的素數，我已經改變了你的檢查，以便它將填充該數組，直到達到最大條目數。
• 我還包括檢查用戶是否傳遞了「p」數組範圍之外的索引號。否則會產生分段錯誤。

現在這個編譯並運行給出：

$ g++ prime_calc.cpp -o prime_calc 
$ ./prime_calc 
3 
1500 
12553 
15000 
163841 
15001 
That value is too large, try a number <= 15000.