The Sieve of Eratosthenes

A prime number is a number which only divisible by 1 and itself. Another way to think about primes is that if you have a prime number of square tiles, then they cannot be arranged to form a rectangle which is more than one tile wide. Below is an example of how 7 square tiles (a prime number) can be arranged:


The "Sieve of Eratosthenes" is a method that was used in the 3rd century BC by a Greek librarian called Eratosthenes to determine which numbers are prime. Basically you write down the first N integers and cross out all multiples of 2 (i.e. 4, 6, 8, 10, etc), and then all multiples of the next number which has not yet been crossed out (i.e. 3) and so on. Any numbers which are left at the end of this procedure are primes.

The C++ program below implements this method: 

//
// EratosthenesSieve.cpp
//
// Anthony Dunk, 31/3/07
//
// This program uses the "Sieve of Eratosthenes" method to build a list of the prime
// numbers between 1 and N.
//

#include "stdafx.h"

int main(int argc, char* argv[])
{
	//
	// Find all primes between 1 and N
	//
	const int N = 1000;

	// Define the sieve
	bool prime[N+1];

	// Flag all numbers as prime initially
	int i,j,p;
	for (i=1; i<=N; i++) prime[i]=true;

	// Start with first prime, 2
	p = 2;
	while (true)
	{
		// Eliminate all factors of this prime
		j=2*p;
		while (j<=N)
		{
			prime[j]=false; // Flag this number as non-prime
			j=j+p;
		}

		// Find the next prime
		bool next_prime_found = false;
		for (i=p+1; i<=N; i++)
		{
			if (prime[i])
			{
				p = i;
				next_prime_found = true;
				break;
			}
		}

		// Exit loop if all prime factors have been eliminated
		if (!next_prime_found) break;
	}

	// Display the primes and count them
	printf("Prime numbers between 1 and %d:\n\n",N);
	int count = 0;
	for (i=2; i<=N; i++)
	{
		if (prime[i])
		{
			printf("%4d ",i);
			count++;
		}
	}
	printf("\n\n");
	printf("%d primes\n\n",count);

	return 0;
}


And here are the results when the program is run with N = 1000: 

Prime numbers between 1 and 1000:

    2    3    5    7   11   13   17   19   23   29   31   37   41   43
   47   53   59   61   67   71   73   79   83   89   97  101  103  107
  109  113  127  131  137  139  149  151  157  163  167  173  179  181
  191  193  197  199  211  223  227  229  233  239  241  251  257  263
  269  271  277  281  283  293  307  311  313  317  331  337  347  349
  353  359  367  373  379  383  389  397  401  409  419  421  431  433
  439  443  449  457  461  463  467  479  487  491  499  503  509  521
  523  541  547  557  563  569  571  577  587  593  599  601  607  613
  617  619  631  641  643  647  653  659  661  673  677  683  691  701
  709  719  727  733  739  743  751  757  761  769  773  787  797  809
  811  821  823  827  829  839  853  857  859  863  877  881  883  887
  907  911  919  929  937  941  947  953  967  971  977  983  991  997 

168 primes


If you interested in the primes I can recommend Marcus du Sautoy's The Music of the Primes as an interesting book to read.

Back to my software page