Polda18 - 1 year ago 61

C Question

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`

`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? :(

Answer Source

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.