CODEWITHSUNDEEP
c++primes
Komninos
Komninos

Reputation: 96

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?

EDIT: The A int table is automatically intialized to 0s as it is outside the main class.

Upvotes: 1

Views: 244

Answers (3)

Raman
Raman

Reputation: 2785

There are many issues with your code.

  1. int A[1000000];

    You haven't initialized the array. you should initialize A[0]=1, A[1]=1 and all other indexes to 0.

  2. for(int j = i*i; j < till; j+=i)

    i*i may lead to integer overflow. you should probably use j=i+i to decrease your chances of overflow.

  3. A[j - 1] = 1;

    Not sure you are using proper array indexes.

Upvotes: 0

nim_10
nim_10

Reputation: 496

Very easy. We have a few trivial case:

  1. 0 more than two divisors, so it's not prime
  2. 1 has only one divisor, so it's not prime
  3. 2 is the only even number which is prime

So, basically we should not calculate the even numbers. We are interested in only odd numbers.

We will mark all non prime numbers as 1.

int A[1000000];
void sieve(int till)
{
    // mark all even numbers (except 2) as not prime
    for(int i = 4; i < till; i += 2)
    {
        A[i] = 1;
    }

    // now calculate not primes for only odd numbers
    for(int i = 3; i < till; i += 2 )
    {
        if(A[i] == 0)
        {
            for(int j = i*i; j < till; j+=(i+i))
            {
                A[j] = 1;
            }
        }
    }
}

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

    for(int i = 2; i < N; i++)
    {
        if(A[i] == 1) printf("%d is not prime\n", i);
        else printf("%d is prime\n", i);
    }

    return 0;
}

Upvotes: 1

amchacon
amchacon

Reputation: 1961

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

Upvotes: 0

Related Questions