Home > Articles, Data Structures & Algorithms > Implementation of algorithm for finding primes with the sieve of Eratosthenes.

Implementation of algorithm for finding primes with the sieve of Eratosthenes.

The aim of this program is to assign to a[i] the value 1 if i is a prime number and the value 0 if not. Initially, all elements of the array take the value 1 to indicate that there are no numbers which are known not to be prime. Then all elements of the array corresponding to indexes that are known not to be primes (multiples of known primes) take the value 0. If a[i] has the value 1 even after all multiples of smaller primes have taken the value 0, we know that i is a prime number.

Because the program uses an array whose elements are of the simplest type (values 0 and 1), we would save space if we used an explicit array of digits, not a list of integers. Also, some programming environments may require the array declared as global variable if N is large, although we could allocate memory for the array dynamically.

You should know that the implementation of the algorithm does not take into account issues of data input validation or proper management of dynamic memory (e.g. avoiding memory leaks) because it is only necessary to highlight the logic of the algorithm.

#include <iomanip>
#include <iostream>
using namespace std;

const int N = 1000;

int
main () {
  int i, a[N];

  cout << setw (5) << setfill ('0') << "1" << endl;

  for (i = 2; i < N; i++) a[i] = 1;

  for (i = 2; i < N; i++)
    if (a[i])
      for (int j = i; j*i < N; j++)
        a[i*j] = 0;

  for (i = 2; i < N; i++)
    if (a[i])
      cout << setw (5) << setfill ('0') << i << endl;

  return 0;
}
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: