C中Eratosthenes算法的筛选

好的，所以我创建的这个函数使用Sieve of 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函数中存在一些问题，但我不确定是什么。

预期产出：

有8个素数小于或等于19

 2 3 5 7 11 13 17 19  

我的输出： 

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

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

1. 错误的删除过程if (sieve[multiple]) { array sieve index有偏差
2. (*array) = sieve; 泄漏just-malloced内存，并让*array指向一个在函数返回时不再存在的局部变量 – 你会得到一个悬空指针。
3. 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]); 

无论是否为0 ，都要打印sieve的内容，并打印出不存在的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"); 

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