用C埃拉托色尼算法筛 [英] Sieve of Eratosthenes algorithm in C
问题描述
好了，所以这个功能，我创建使用埃拉托色尼算法的筛来计算所有的素数＆LT; = N。此函数存储素数，并在参数素数的计数。
当函数退出，质数应指向动态分配内存的一块保存所有质数＆LT; = NUM。 *计数将有质数的计数。
下面是我的功能 getPrimes ：
无效getPrimes（INT NUM，为int *计数，诠释**阵列）{
（*次数）=（NUM - 1）;
INT筛[NUM-1]，primenums = 0，索引，fillnum，多个; //填入数字阵列到用户的结束号码，NUM。
对于（指数= 0，fillnum = 2; fillnum＆LT; = NUM;指数++，fillnum ++）{
筛[指数] = fillnum;
} / *启动划掉开始2，因为1个非素数
并非素数。然后，它会删除所有这些倍数之和
移动到该心不是划掉的下一个号码，这是一个质数。 * /
对于（; primenums＆LT;开方（NUM）; primenums ++）//通过数组散步。
{
//检查该号码为空，这意味着它划掉
如果（筛[primenums]！= 0）{
//如果没有划掉它开始删除其数倍。
对于（多=（筛[primenums]）;
多个＆LT; NUM;
多重+ =筛[primenums]）{
//隧道倍数出来
//和递减计数移动到下一个数字
筛[多重+ primenums] = 0;
- （*计数）;
}
}
}
时int k;
对于（K = 0; K＆LT;民; k ++）
的printf（％d个\\ N，筛[K]）; 的printf（％d个\\ N，*计）;
阵列=的malloc（sizeof的（INT）*（NUM + 1））;
断言（数组）;
（*数组）=筛;
}
现在，这里是预期的输出和我的输出。正如你所看到的东西是我的 getPrimes 函数中的错误，但我不能确定什么。
预期输出：有8个素数小于或等于192 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
下面是人们向我指出，到目前为止三个问题：
- 错误删除过程
如果（筛[多]）{数组筛指数有偏差 -
（*数组）=筛;泄漏刚刚malloc内存，并让*阵列指向当函数返回存在的停止局部变量 - 你会得到一个悬空指针 -
如果（筛[I]！= NULL）应使用0，不为空，你没有指针数组。
不过，我也不太清楚如何解决已经发现了我的悬摆指针/内存问题。除此之外，我不知道是否有我的code内别的，因为我不是太肯定有错误，为什么我在我的输出添加的0 ...不用担心不同的输出格式的数字，只是多余的号码。谢谢如果你能帮助我这个！
无效getPrimes（INT NUM，为int *计数，诠释**阵列）{
（*次数）=（NUM - 1）;
INT筛[NUM-1]，primenums = 0，索引，fillnum，多个;
您是通过 NUM 声明 NUM-1 元素的数组，从2的数字。这没关系。
//填入数字阵列到用户的结束号码，NUM。
对于（指数= 0，fillnum = 2; fillnum＆LT; = NUM;指数++，fillnum ++）{
筛[指数] = fillnum;
}
您正在填充它与关联的数字，也还可以。
每个插槽 / *开始渡出开始以2，因为1不是素非质数。
然后，它会删除所有这些倍数之和
移动到该心不是划掉的下一个号码，这是一个质数。 * /
对于（; primenums＆LT;开方（NUM）; primenums ++）//通过数组散步。
你在平方根大致停止，这是很好的。
{
如果（筛[primenums]！= 0）{//检查是否该数字为NULL这意味着它划掉 对于（多=（筛[primenums]）;多＆LT; NUM;多+ =筛[primenums]）
//如果没有划掉它开始删除其数倍。
{//隧道倍数并递减计数移动到下一个数字
筛[多重+ primenums] = 0;
您在这儿有问题。你只停止循环时多＆GT; = NUM ，但你写指数多重+ primenums ，而且常常是过去的数组的末尾。例如， NUM = 19 和 primenums == 1 （横跨出3的倍数）最后写是指数 18 + 1 ，但最后一个有效的指数 NUM - 2 = 17
1点的索引偏差已得到修复。但
- （*计）;
您会无条件地递减 *计数这里，在前面的code你只减少它时，筛[多] 是不是已经划掉。这是正确的做法。我建议
为（多= primenums +筛[primenums];多＆LT; NUM - 1;多+ =筛[primenums]）{
如果（筛[多]）{
筛[多] = 0;
- （*计数）;
}
}
将它简单一点。
}
}
}
时int k;
对于（K = 0; K＆LT;民; k ++）
的printf（％d个\\ N，筛[K]）;
您要打印筛的内容，无论其是否为 0 或没有，你也打印出筛[NUM - 1] ，它不存在。让它
的（K = 0; K＆LT; NUM-1; ++ K）{
如果（筛[K]）{
的printf（％d个\\ N，筛[K]）;
}
}
只打印素数。
的printf（％d个\\ N，*计）;
阵列=的malloc（sizeof的（INT）*（NUM + 1））;
断言（数组）;
（*数组）=筛;
}
替换（*数组）=筛与
INT I = 0;
对于（K = 0; K＆LT; NUM-1; ++ K）{
如果（筛[K]）{
（*数组）[I] =筛[K];
++我;
}
}
只写了素数为 *阵列。另外，你需要不分配（NUM + 1）* sizeof的（INT），但只有 *计数*的sizeof（INT）为
Okay, so this function I created uses the Sieve of Eratosthenes algorithm to compute all the primes <= n. This function stores the prime numbers and the count of primes in the parameters.
When the function exits, primes should be pointing to a chunk of dynamically allocated memory that holds all the primes <= num. *count will have the count of primes.
Here is my function 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;
}
Now, here is the intended output and my output. As you can see, something is wrong within my getPrimes function but I am unsure as to what.
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
Here are 3 problems that people have pointed out to me so far:
- Wrong delete process
if (sieve[multiple]) {array sieve index has bias (*array) = sieve;leaks the just-malloced memory, and lets*arraypoint to a local variable that ceases to exist when the function returns - you'll get a dangling pointer.if(sieve[i] != NULL)should use 0, not NULL, you're not having an array of pointers.
However, I'm not too sure how to fix the dangling pointer/memory issue that has been spotted out for me. Besides that, I was wondering if there was anything else within my code that has errors as I am not too sure why my numbers in my output are adding the 0's...don't worry about the different output style, just the extra numbers. Thanks if you can help me out with this!
void getPrimes(int num, int* count, int** array){
(*count) = (num - 1);
int sieve[num-1], primenums = 0, index, fillnum, multiple;
You're declaring an array of num-1 elements, for the numbers from 2 through num. That's okay.
//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;
}
You're filling each slot with the number it associated with, also okay.
/* 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.
You're stopping roughly at the square root, that's good.
{
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;
You're having a problem here. You only stop the loop when multiple >= num, but you're writing to the index multiple + primenums, and that is often past the end of the array. For example, with num == 19, and primenums == 1 (which crosses out the multiples of 3), the last write is to index 18 + 1, but the last valid index is num - 2 = 17.
The indexing bias of point 1 has been fixed. But
--(*count);
You're unconditionally decrementing *count here, in the earlier code you only decremented it when sieve[multiple] was not already crossed out. That is the correct way. I suggest
for(multiple = primenums + sieve[primenums]; multiple < num - 1; multiple += sieve[primenums]) {
if (sieve[multiple]) {
sieve[multiple] = 0;
--(*count);
}
}
to have it a bit simpler.
}
}
}
int k;
for(k=0; k < num; k++)
printf("%d \n", sieve[k]);
You're printing the contents of sieve regardless of whether it is 0 or not, and you also print out sieve[num - 1], which does not exist. Make it
for(k = 0; k < num-1; ++k) {
if (sieve[k]) {
printf("%d\n", sieve[k]);
}
}
to print only the primes.
printf("%d \n", *count);
array = malloc(sizeof(int) * (num + 1));
assert(array);
(*array) = sieve;
}
Replace the (*array) = sieve with
int i = 0;
for(k = 0; k < num-1; ++k) {
if (sieve[k]) {
(*array)[i] = sieve[k];
++i;
}
}
to write only the primes to *array. Also, you need not allocate (num + 1)*sizeof(int), but only *count * sizeof(int) for that.
这篇关于用C埃拉托色尼算法筛的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
