3

好的，所以我创建的这个函数使用 Eratosthenes 算法来计算所有素数 <= n。该函数在参数中存储素数和素数。

当函数退出时，素数应该指向一块动态分配的内存，其中包含所有素数<= num。 *count将有素数的计数。

这是我的功能getPrimes：

void getPrimes(int num, int* count, int** array){
    (*count) = (num - 1);
    int sieve[num-1], primenums = 0, index, fillnum, multiple;

    //Fills the array with the numbers up to the user's ending number, num.
    for(index = 0, fillnum = 2; fillnum <= num; index++, fillnum++){
        sieve[index] = fillnum;
    }

    /* Starts crossing out non prime numbers starting with 2 because 1 
       is not a prime. It then deletes all of those multiples and 
       moves on to the next number that isnt crossed out, which is a prime. */
    for (; primenums < sqrt(num); primenums++)  //Walks through the array.
    {
        //Checks if that number is NULL which means it's crossed out
        if (sieve[primenums] != 0) {
            //If it is not crossed out it starts deleting its multiples.
            for (multiple = (sieve[primenums]); 
                 multiple < num; 
                 multiple += sieve[primenums]) {  
                //Crossing multiples out 
                //and decrements count to move to next number
                sieve[multiple + primenums] = 0;
                --(*count);
            }
        }
    }
    int k;
    for(k=0; k < num; k++)
        printf("%d \n", sieve[k]);

    printf("%d \n", *count);
    array = malloc(sizeof(int) * (num + 1));
    assert(array);
    (*array) = sieve;
}

现在，这是预期的输出和我的输出。如您所见，我的getPrimes功能中有问题，但我不确定是什么。

预期输出：

小于或等于 19 的素数有 8 个

2 3 5 7 11 13 17 19  

我的输出：

2
3
0
5
0
7
0
0
0
11
0
13
0
0
0
17
0
19
0
0

到目前为止，人们向我指出了以下 3 个问题：

  1. 错误的删除过程if (sieve[multiple]) {数组筛子索引有偏差
  2. (*array) = sieve;泄漏刚刚分配的内存，并让我们*array指向一个在函数返回时不再存在的局部变量——你会得到一个悬空指针。
  3. if(sieve[i] != NULL)应该使用 0，而不是 NULL，你没有指针数组。

但是，我不太确定如何解决已为我发现的悬空指针/内存问题。除此之外，我想知道我的代码中是否还有其他错误，因为我不太清楚为什么我的输出中的数字添加了 0...不要担心不同的输出样式，只是额外的数字. 谢谢你能帮我解决这个问题！

4

2 回答 2

3 
void getPrimes(int num, int* count, int** array){
    (*count) = (num - 1);
    int sieve[num-1], primenums = 0, index, fillnum, multiple;

您正在num-1为从 2 到 的数字声明一个元素数组num。没关系。

    //Fills the array with the numbers up to the user's ending number, num.
    for(index = 0, fillnum = 2; fillnum <= num; index++, fillnum++){
        sieve[index] = fillnum;
    }

您正在用与之关联的数字填充每个插槽，也可以。

     /* Starts crossing out non prime numbers starting with 2 because 1 is not a prime.
        It then deletes all of those multiples and 
        moves on to the next number that isnt crossed out, which is a prime. */
     for (; primenums < sqrt(num); primenums++) //Walks through the array.

您大致停在平方根处，这很好。

        {
            if (sieve[primenums] != 0){ //Checks if that number is NULL which means it's crossed out

                   for (multiple = (sieve[primenums]); multiple < num; multiple += sieve[primenums])
                      //If it is not crossed out it starts deleting its multiples.
                   {  //Crossing multiples out and decrements count to move to next number
                            sieve[multiple + primenums] = 0;

你这里有问题。您仅在 时停止循环multiple >= num，但您正在写入 index multiple + primenums，并且通常超过数组的末尾。例如，使用num == 19, and primenums == 1（删除 3 的倍数），最后一次写入是对 index 18 + 1，但最后一个有效索引是num - 2 = 17.

第 1 点的索引偏差已修复。但

                            --(*count);

您在这里无条件地递减，在之前的代码中，您只是在尚未被划掉*count时才递减它。sieve[multiple]这才是正确的方法。我建议

for(multiple = primenums + sieve[primenums]; multiple < num - 1; multiple += sieve[primenums]) {
    if (sieve[multiple]) {
         sieve[multiple] = 0;
         --(*count);
    }
}

让它更简单一点。

                   }
            }
        }
        int k;
        for(k=0; k < num; k++)
            printf("%d \n", sieve[k]);

sieve无论是否存在，您都在打印内容0，并且还打印出sieve[num - 1]不存在的内容。做了

for(k = 0; k < num-1; ++k) {
    if (sieve[k]) {
        printf("%d\n", sieve[k]);
    }
}

只打印素数。

            printf("%d \n", *count);
        array = malloc(sizeof(int) * (num + 1));
         assert(array);
         (*array) = sieve;
}

替换(*array) = sieve为

int i = 0;
for(k = 0; k < num-1; ++k) {
    if (sieve[k]) {
        (*array)[i] = sieve[k];
        ++i;
    }
}

只写素数到*array。此外，您不需要 allocate (num + 1)*sizeof(int)，而只是*count * sizeof(int)为此。

于 2013-03-29T23:03:42.363 回答
2

您要打印的数字属于筛子，因此所有非质数都设置为 0。尝试按以下方式打印

for (k = 0; k < num; k++)
if (sieve[k] != 0)
{
        printf(" %d\n", sieve[k]);
}
printf("\n");

此外，您不应sieve通过array参数返回本地数组，因为它位于堆栈上，并且在函数返回时将不再可用。

于 2013-03-29T23:05:21.783 回答