[erinl1]

(The Sieve of Eratosthenes) A prime integer is any integer that can be divided evenly only by
itself and 1. The Sieve of Eratosthenes is a method of finding prime numbers.

It works as follows:

1) Create an array with all elements initialized to 1 (true). Array elements with prime subscripts
will remain 1. All other array elements will eventually be set to zero.

2) Starting with array subscript 2 (subscript 1 must be prime), every time an array element is
found whose value is 1, loop through the remainder of the array and set to zero every element
whose subscript is a multiple of the subscript for the element with value 1. For array
subscript 2, all elements beyond 2 in the array that are multiples of 2 will be set to zero (subscripts
4, 6, 8, 10, etc.).
For array subscript 3, all elements beyond 3 in the array that are multiples of 3 will be set to zero (subscripts 6, 9, 12, 15, etc.).

When this process is complete, the array elements that are still set to one indicate that the subscript is a
prime number. These subscripts can then be printed. Write a program that uses an array of 1000 elements
to determine and print the prime numbers between 1 and 999. Ignore element 0 of the array.*/

#define N 

int main(void)

{
   int z[N];  /* array of integers, z[0], ... z[N-1] */
   for ( i = 0; i < N; i++ )
	 initialize z[i];
   for ( i = 2; i < N; i++ )
	  mark the multiples of i;  /* this marking can be done with one for and one if statement */
   for ( i = 2; i < N; i++ )
	  print the unmarked entries of z;
}

#include <stdlib.h> 
#include <stdio.h>

void eratosthenes(int top)
{
  int all[1000];
  int idx = 0;
  int prime = 3;
  int x, j;
		
  printf("1 ");
	
  while(prime <= top)
  {
	for(x = 0; x < top; x++)
	{
	  if(all[x] == prime) goto skip; 
	}

	printf("%d ", prime);
	j = prime;
	while(j <= (top / prime))
	{
	  all[idx++] = prime * j;
	  j += 1;
	}

skip:	
	prime+=2;
  }
  puts("");
  return;
}

int main(int argc, char **argv)
{
  if(argc == 2) eratosthenes(atoi(argv[1]));
  else eratosthenes(50);
  return 0;
}

*edit: please use code tags in the future, thanks!

This post has been edited by Martyr2: 10 February 2008 - 10:01 AM

[Martyr2]

I have written a blog entry about this and provided sample code for both Java and C#. The code should give you an idea of how to do it in C++ (since both Java and C# are in some ways similar to C++ in syntax). Check it out at the link below...

Martyr2's Programming Underground - Sieve of eratosthenes

Enjoy!