2

我的代码在这里遇到了一个非常奇怪的问题。当我使用手动打印语句输出 int *primesArr 的值时，它（看似）有效，但如果我尝试使用 for 循环这样做，它会失败。我通过 gdb 运行它，发现它在我将数组中的下一个单元格设置为值“k”的地方崩溃，这仅在数字为素数时发生。第一次迭代成功（即 2 设置为 primesArr[0]），然后在尝试增加数组时程序 Segfaults。但这仅在使用 for 循环时发生。当我创建单独的打印语句时，我的程序按预期工作。我不确定在使用 for 循环时如何/为什么要访问尚未分配的内存。我确定我在某个地方犯了一些业余错误，这可能与我传递指针的方式有关...... 但我无法确定它的确切根源。我将不胜感激，并提前感谢您。

#include<stdio.h>

int genPrimes(int seed, int *test){
    int inNumPrimes=0;
    for(int k=0; k<=seed; k++){//k is number being checked for primeness
        int cnt=0;
        for(int i=1; i<=k; i++){//'i' is num 'k' is divided by
            if(k%i == 0){
                cnt++;
                if(cnt > 2){
                    break;
                }
                }else{
            }

        }
        if(cnt == 2){
            printf("%i IS PRIME\n",k);
            *test=k;
            test++;//according to gdb, the problem is somewhere between here
            inNumPrimes++;//and here. I'd wager I messed up my pointer somehow
        }
        //printf("%i\n",k);
    }
    return inNumPrimes;
}

int main(){
    int outNumPrimes=0;
    int *primesArr;
    int n = 0;
    n=20;

    outNumPrimes=genPrimes(n, primesArr);
    printf("Congratulations!  There are %i Prime Numbers.\n",outNumPrimes);

    //If you print using this for loop, the SEGFAULT occurs.  Note that it does not matter how high the limit is; its been set to many values other than 5. It will eventually be set to 'outNumPrimes'
    //for(int a=0; a<5; a++){
    //printf("%i\n",primesArr[a]);
    //}

    //If you print the array elements individually, the correct value--a prime number--is printed.  No SEGFAULT.
    printf("%i\n",primesArr[0]);
    printf("%i\n",primesArr[1]);
    printf("%i\n",primesArr[2]);
    printf("%i\n",primesArr[3]);
    printf("%i\n",primesArr[4]);
    printf("%i\n",primesArr[5]);
    printf("%i\n",primesArr[6]);
    printf("%i\n",primesArr[7]);
    //
    return 0;
}

带有手动语句的输出：

$ ./a.out 
2 IS PRIME
3 IS PRIME
5 IS PRIME
7 IS PRIME
11 IS PRIME
13 IS PRIME
17 IS PRIME
19 IS PRIME
Congratulations!  There are 8 Prime Numbers.
2
3
5
7
11
13
17
19

现在使用 for 循环：

$ ./a.out 
2 IS PRIME
Segmentation fault
4

3 回答 3

6

您正在将未初始化的指针传递给您的素数函数。你得到的行为是不确定的，这就是为什么这看起来如此神秘。变量 primesArr 可能指向任何地方。

对于像这样的简单案例，最好使用std::vector<int>

于 2012-05-14T01:44:59.760 回答
5

线

int *primesArr;

声明primesArr为指针变量，但不为其分配任何内存。由于该genPrimes()函数希望将其视为将填充素数的空数组，因此您可以main()在调用之前分配内存genPrimes()：

int primesArr[MAX_PRIMES];

或者

int *primesArr = malloc(MAX_PRIMES * sizeof(int));

然而，在这两种情况下，您必须保证它MAX_PRIMES足够大以容纳所有genPrimes()找到的素数，否则代码将像现在一样产生错误。

其他提示：

1：复杂性

唯一cnt必要的原因是它可以被和k整除。如果你改变1k

for (int i=1; i<=k; i++) {  // 'i' is the number 'k' is divided by

至

for (int i=2; i<k; ++i) {  // 'i' is the number 'k' is divided by

那么这两种情况都被消除了，一旦找到ifor which的值，循环就可以退出k%i == 0。

2：效率

考试

for (int i=2; i<k; ++i) {  // 'i' is the number 'k' is divided by

由于两个原因，仍然非常低效。首先，不需要测试每个偶数；如果k > 2和(k % 2) == 0，则k不能是素数。因此，您可以通过明确检查 2（素数）或可被 2（非素数）整除，然后使用

for (int i = 3;  i < k;  i += 2) {  // 'i' is the number 'k' is divided by

但是你可以让这更有效，因为你可以在到达后停止sqrt(k)。为什么？如果k能被某个数整除，那么它也一定能被（因为= ）i整除。如果, then和循环已经退出。所以你只需要k/ii * k/iki > sqrt(k)k/i < sqrt(k)

int r = (int) sqrt(k);
for (int i = 3;  i <= r;  i += 2) {  // 'i' is the number 'k' is divided by

如果sqrt()不可用，您可以使用

for (int i = 3;  i*i <= k;  i += 2) {  // 'i' is the number 'k' is divided by

3：风格

只是一件简单的事情，但不是

int n = 0;
n=20;

你可以简单地写

int n = 20;
于 2012-05-14T01:49:59.970 回答
1

您的 primesArr 变量未初始化。

将指针声明为

int *ptr;

只需声明一个指向 int 的指针。但是，指针本身并不指向任何东西。很像声明

int val;

不初始化 val。因此，您需要为 primesArr 指针分配内存以指向（new在堆栈上或堆栈上，例如int primesArr[N]whereN是一些大数字。

但是，由于您不知道您将从 genPrimes 函数中获得多少素数，并且您没有说 STL 是不可能的，所以我会考虑使用 astd::vector<int>作为您的 genPrimes 函数的输入：

int genPrimes(int seed, std::vector<int>& test)

而且，从函数内部，您可以执行以下操作：

test.push_back(k)
于 2012-05-14T01:52:59.740 回答