Polda18 - 1 year ago 99
C Question

# Sieve of Eratosthenes C implementation error

So I am making next homework with input numbers to be dissolved to primes multiplication in output. I was confused when it showed up only prime number 2, so I did a proper control dump of the allocated primes array using this function:

``````long* eratosthen(long max) {
bool grid[max + 1];

for(long i = 0; i < max + 1; ++i) {
grid[i] = true;
}

for(long i = 2; i < max + 1; ++i) {
if(grid[i]) {
for(long j = i * 2; j < max + 1; ++j) {
grid[j] = false;
}
}
}

long *primes;
primes = (long*)malloc((max + 1) * sizeof(long));

long index = 0;
for(long i = 2; i < max + 1; ++i) {
if(grid[i]) {
primes[index++] = i;
}
}

return primes;
}
``````

For some unknown reason, the dump says
`2`
only and ends. Calling for dump is made up by following code:

``````int main(void) {
// Prime numbers get calculated first
long *primes;
primes = eratosthen(1000000);

// Control code
fprintf(stdout, "Control dump of primes array:\n");
for(long i = 0; i < sizeof(primes) / sizeof(long); ++i) {
fprintf(stdout, "%li\n", primes[i]);
}
int ret = 0;
/// ...
return ret;
}
``````

//EDIT: So after all your answers I'll update my question to current state. Main program:
int main(void) {
// Prime numbers get calculated first
long *primes;
primes = eratosthen(1000000);

``````    // Control code
fprintf(stdout, "Control dump of primes array:\n");
for( ; *primes != 0 ; primes++) {
fprintf(stdout, "%li\n", *primes);
}
int ret = 0;
}
``````

Generation of primes function:

``````long* eratosthen(long max) {
bool *grid;
grid = (bool*)malloc((max + 1) * sizeof(bool));

index = 0;
for(long i = 0; i < max + 1; ++i) {
*(grid + index) = true;
index++;
}

index = 2;
index_2 = 2;
for(long i = 2; i < max + 1; ++i) {
if(*(grid + index)) {
for(long j = i * 2; j < max + 1; j += i) {
*(grid + 2 * index_2) = false;
index_2++;
}
index++;
}
}

long *primes;
primes = (long *)malloc((max + 1) * sizeof(long));

index = 0;
for(long i = 0; i < max + 1; ++i) {
*(primes + index) = 0;
index++;
}

index = 0;
index_2 = 2;
for(long i = 2; i < max + 1; ++i) {
if(*(grid + index_2)) {
*(primes + index) = i;
index++;
index_2++;
}
}

// free the grid
free(grid);

return primes;
}
``````

Like said before, the Ubuntu terminal displays following line:

``````Neoprávněný přístup do paměti (SIGSEGV) (core dumped [obraz paměti uložen])
``````

translated like this:

``````Forbidden access to memory (SIGSEGV) (core dumped [memory image saved])
``````

What does it mean and how to get rid of that? :(

The simplest fix to your code is probably to add a sentinel value of 0 to the end of the array of primes, and to rewrite the check condition in `main()`. As explained extensively in the comments, your current test:

``````for(long i = 0; i < sizeof(primes) / sizeof(long); ++i) {
``````

is irremediably wrong. You must not attempt to use `sizeof` because it simply doesn't do what you want it to do.

This code works:

``````#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

static
long *eratosthen(long max)
{
bool grid[max + 1];

for (long i = 0; i < max + 1; ++i)
grid[i] = true;

for (long i = 2; i < max + 1; ++i)
{
if (grid[i])
{
for (long j = i * 2; j < max + 1; j += i)   // Key fix
grid[j] = false;
}
}

long *primes;
primes = (long *)malloc((max + 1) * sizeof(long));

long index = 0;
for (long i = 2; i < max + 1; ++i)
{
if (grid[i])
primes[index++] = i;
}
primes[index] = 0; // Sentinel

return primes;
}

int main(void)
{
// Prime numbers get calculated first
long *primes = eratosthen(1000000);

fprintf(stdout, "Control dump of primes array:\n");
for (long i = 0; primes[i] != 0; ++i)
{
printf("%7li", primes[i]);
if (i % 10 == 9)
putchar('\n');
}
putchar('\n');
return 0;
}
``````

I revised the code to print 10 numbers per line. I changed the condition in the loop in `main()`. And I made two key changes in the function — one to calculate multiples of primes correctly, and the other to add the sentinel at the end of the list of primes.

It produces a list of 78,498 primes starting with

``````      2      3      5      7     11     13     17     19     23     29
31     37     41     43     47     53     59     61     67     71
73     79     83     89     97    101    103    107    109    113
``````

and ending with:

`````` 999563 999599 999611 999613 999623 999631 999653 999667 999671 999683
999721 999727 999749 999763 999769 999773 999809 999853 999863 999883
999907 999917 999931 999953 999959 999961 999979 999983
``````

You might note that the code does not release `primes` — it arguably should. You might note that the space allocated for the primes greatly exceeds the space needed (one million vs less than eighty thousand); you could use `realloc()` to shrink the space allocated, or use a less conservative (or do I mean less profligate?) estimate on the number of entries needed.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download