用C埃拉托色尼算法的筛(Sieve of Eratosthenes algorithm in C)

好了，所以该功能我创建使用埃拉托塞尼的筛的算法来计算所有的质数<= 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功能，但我不能确定是什么。

Intended Output:

There are 8 prime numbers less than or equal to 19

2  3  5  7  11  13  17  19  

My Output: 

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

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

错误删除过程if (sieve[multiple]) {阵列筛索引具有偏压
(*array) = sieve; 泄漏刚刚malloc内存，并让*array点到停止时的函数返回存在一个局部变量-你会得到一个悬摆指针。
if(sieve[i] != NULL)应该使用0，而不是NULL，你不具有指针数组。

不过，我也不太清楚如何解决已经发现了我的悬摆指针/内存问题。除此之外，我不知道是否有我的代码内的任何其他的我也不太清楚有错误的，为什么我在我的输出添加的0的......不用担心不同的输出样式，只是额外的数字号码。谢谢如果你能帮助我这个！

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.

你在平方根大致停止，这是很好的。

        {
            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)为。

Answer 2:

要打印的数字是一个筛子，所以不属于主要如下设置为0尝试打印所有号码

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

你也应该不会返回本地阵列sieve通过array参数，因为它位于堆栈上，这将不再可用的功能的回归。

文章来源: Sieve of Eratosthenes algorithm in C