C语言中的埃拉托色尼筛法算法

Question

好的，所以我创建的这个函数使用埃拉托色尼筛法算法来计算所有小于等于 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]) {数组sieve索引存在偏差 2. (*array) = sieve;泄漏了刚分配的内存，并让* array 指向一个当函数返回时不存在的局部变量-您将获得一个悬空指针。 3. if(sieve[i] != NULL)应该使用0而不是NULL，因为您没有一个指针数组。

然而，我不太确定如何解决被指出的悬挂指针/内存问题。除此之外，我想知道我的代码中是否还有其他错误，因为我不太确定为什么我的输出数字会添加0...不要担心输出样式不同，只需要额外的数字。如果您能帮助我解决这个问题，谢谢！

- Hetero Myde

Answer 1

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.

你差不多在平方根的附近停了下来，这很好。

该句话涉及到 IT 技术内容。

        {
            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时才停止循环，但是你写到了索引multiple + primenums，这通常超出了数组的末尾。例如，当num == 19，primenums == 1（划掉3的倍数）时，最后一次写入的是索引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中。此外，您无需分配(num + 1)*sizeof(int)，而只需要为*count * sizeof(int)分配内存即可。

- Daniel Fischer

---

非常好的回答！非常详尽和有帮助。 - Hetero Myde

Answer 2

你打印的数字是筛子的数字，所以所有不是质数的数字都被设置为0。尝试按以下方式打印。

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

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

- Bryan Olivier

---

你的回答实际上解决了我的问题...但是现在我对于任何大于99的数字都会得到一个分段错误。 - Hetero Myde