CODEWITHSUNDEEP
c++algorithm
CroCo
CroCo

Reputation: 5741

How to implement the sieve of Eratosthenes algorithm

I would like to implement Sieve of Eratosthenes algorithm. The pseudocode as provided in the preceding link is 

Input: an integer n > 1

Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.

for i = 2, 3, 4, ..., not exceeding √n:
  if A[i] is true:
    for j = i^2, i^2+i, i^2+2i, i^2+3i, ..., not exceeding n :
      A[j] := false

Output: all i such that A[i] is true.

The first problem is dealing with indices. What I've done simply is to match the index with the location of data for the sake of simplicity. My following figure depicts this issue.

enter image description here

My code is not generating prime numbers according to the aforementioned algorithm. This is my implementation 

#include <iostream>
#include <vector>
#include <cmath>


int main()
{
    int n(30);
    std::vector<bool> A;

    for( int i(2); i <= n+2; ++i )
        A.push_back(true);

    for ( int i(2); i <= sqrt(n); ++i ){
        if ( A[i] == true ){
            int a(0);
            for (  int j(i*i); j <= n; j += a*i ){
                A[j] = false;
                ++a;
            }
        }
    }
    for ( int i(2); i < A.size(); ++i ){
        if ( A[i] == true )
            std::cout << i  << " ";
    } 
    std::cout << std::endl;

    return 0;
}

The result is 

2 3 5 7 8 11 13 14 15 17 19 20 21 22 23 26 28 29

Why my code doesn't yield the right answer? Any hints?

Upvotes: 0

Views: 169

Answers (2)

CiaPan
CiaPan

Reputation: 9570

The problem is in this loop:

        for (  int j(i*i); j <= n; j += a*i ){
            A[j] = false;
            ++a;
        }

You should either increment j by i with no a multiplier:

        for (  int j(i*i); j <= n; j += i ){
            A[j] = false;
        }

or calculate a brand new value for j with incrementing a:

        for (  int a(0), j(i*i); j <= n; j = i*i + ++a*i ){
            A[j] = false;
        }

but not mix the two approaches.

Upvotes: 5

marlam
marlam

Reputation: 610

The inner for-loop is making too large steps. The correct solution is to make the step j += i, the variable a is not needed.

#include <iostream>
#include <vector>
#include <cmath>

int main()
{
    int n(30);
    std::vector<bool> A;

    for( int i(2); i <= n+2; ++i )
        A.push_back(true);

    for ( int i(2); i <= sqrt(n); ++i ){
        if ( A[i] == true ){
            for (  int j(i*i); j <= n; j += i ){
                A[j] = false;
            }
        }
    }
    for ( int i(2); i < A.size(); ++i ){
        if ( A[i] == true )
            std::cout << i  << " ";
    }
    std::cout << std::endl;

    return 0;
}

Live Demo

Upvotes: 2

Related Questions