Мой код останавливается при определенном условии

Question

В этом коде я вводил номер тестового примера t, а затем вводил t чисел (n). Затем мой код печатает n-е простое число. В первой строке функции, prime(), если я пишу if(a > 43000) return; Тогда код работает отлично. Но если я напишу if(a >= 165000) return; там же, кодовые блоки говорят, что программа перестала работать. Но я не понимаю, почему.

#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. Это означает, что вы выделяете память на десятки тысяч целых чисел, когда (по внешнему виду вашего метода) все, что вам действительно нужно, равно 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.