1 Replies - 7099 Views - Last Post: 10 February 2008 - 10:03 AM Rate Topic: -----

#1 erinl1   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 10-February 08

the sieve of eratosthenes

Posted 10 February 2008 - 08:39 AM

(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! :code:

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


Is This A Good Question/Topic? 0
  • +

Replies To: the sieve of eratosthenes

#2 Martyr2   User is online

  • Programming Theoretician
  • member icon

Reputation: 5309
  • View blog
  • Posts: 14,172
  • Joined: 18-April 07

Re: the sieve of eratosthenes

Posted 10 February 2008 - 10:03 AM

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! :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1