我的代码在特定条件下停止

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.