特定の条件でコードが停止する

Question

このコードでは、テストケース番号tを入力してt個の数値（n）を入力します。次に、私のコードはn番目の素数を出力します。関数の1行目で、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のチェックを行うと、配列の境界外にある配列のインデックスを埋めることになります。

第2に、再帰を行う際には注意が必要です。 prime()を実行するたびに、5つの新しい整数変数a,i、q、s、およびdのためのスペースを割り当てています。これは、（あなたのメソッドの見た目から）本当に必要なものが5個であれば、何万個もの整数のメモリを割り当てていることを意味します。

これらの値は他のすべての反復とは無関係なので、カップルのトリック。まず、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.