Komninos Komninos - 2 months ago 17
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?

Answer

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);
}