Komninos - 1 year ago 81
C++ Question

Sieve of eratosthenes not working C++

So I am trying to make a C++ program to generate all prime numbers till a certain point but for some reason, it prints all numbers as non-primes after 2.

``````int A[1000000];
void sieve(int till)
{
for(int i = 2; i < till; i++)
{
if(A[i] == 0)
{
for(int j = i*i; j < till; j+=i)
{
A[j - 1] = 1;
//printf("%i is NOT prime\n", ij);
}
}
}
}
``````

and in the main i do:

``````int N;
scanf("%i", &N);
sieve(N);
``````

but when I try to debug it says:

``````NOT PRIME 0
NOT PRIME 1
NOT PRIME 2
PRIME 3
NOT PRIME 4
PRIME 5
NOT PRIME 6
PRIME 7
NOT PRIME 8
PRIME 9
NOT PRIME 10
PRIME 11
NOT PRIME 12
NOT PRIME 13
``````

Can anybody figure what am I doing wrong?

This line:

``````A[j - 1] = 1;
``````

Should be:

``````A[j] = 1;
``````

So, now should works well:

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

int A[1000000];
void sieve(int till)
{
for(int i = 2; i < till; i++)
{
if(A[i] == 0)
{
for(int j = i*i; j < till; j+=i)
{
A[j] = 1;
}
}
}
}

int main()
{
int N,i;

scanf("%i", &N);

for (i = 0;i < N;i++)
A[i] = 0;

sieve(N);

for (i = 2;i < N;i++)
if (A[i])
printf("%i is not prime\n",i);
else
printf("%i is prime\n",i);
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download