# the sieve of eratosthenes

Page 1 of 1

## 1 Replies - 7099 Views - Last Post: 10 February 2008 - 10:03 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=42888&amp;s=33c3c36d4806955ab90e22b25ddaede2&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 erinl1

Reputation: 0
• 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!

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

• Programming Theoretician

Reputation: 5309
• 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!