AL-zami - 1 year ago 73

C Question

Here i am trying to implement sieve of erastosthene in c.The program works fine except one major problem.I manually set the first prime number to be of value 2.But at the end when i loop through all the prime numbers array and print them ,the first value becomes 1 instead of 2.Can't figure out why this problem arises.Any help would be much appreciated.

`#include<stdio.h>`

#include<math.h>

int main(){

int n = 64;

int i,j,limit=sqrt(n)+2,nPrime=0;

int prime[50]={0},mark[64]={0};

mark[1]=1;

prime[nPrime++] = 2;

printf("%d\n",prime[0]); // initialized to 2

for(i=4;i<=n;i=i+2){

mark[i] = 1;

}

for(i=3;i<=n;i=i+2){

if(!mark[i]){

prime[nPrime++] = i;

if(i<=limit){

for(j=i*i;j<=n;j=j+i*2){

mark[j]=1;

}

}

}

}

int k;

int size = sizeof(prime)/sizeof(prime[0]);

printf("%d\n",prime[0]); // changed to 1;

for(k=0;k<size && prime[k]!=0;k++){

printf("%d ",prime[k]);

}

}

Answer Source

The problem is in this loop:

```
for(i=4;i<=n;i=i+2) {
mark[i] = 1;
}
```

The condition should be `i < n`

, because with `<=`

it will take the value 64, and that would be out of bounds.

When you set `mark[64] = 1`

you are modifying memory that does not belong to the mark array, in this case it turn out to be the first element of the prime array. If you test out other indexes, you could end up getting a segfault.

If you set manually `mark[64] = 56`

, you will see that `prime[0] == 56`