# Finding Prime Numbers Using The Sieve Of Eratosthenes

Page 1 of 1

## 3 Replies - 1591 Views - Last Post: 24 January 2012 - 02:39 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=364364&amp;s=362b30d85af0ce5347e4ac92c3d7f103&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 Louisda16th

• dream.in.assembly.code

Reputation: 15
• Posts: 1,967
• Joined: 03-August 06

# Finding Prime Numbers Using The Sieve Of Eratosthenes

Posted 12 August 2006 - 01:19 AM

Description: compile, build n runThis program uses a simple method developed by Eratosthenes(Greek mathematician). Basically u select a number an strike of all its multiplies. then u go to the next number n so on till u reach the end. What ure left with r prime numbers.
```/* Finding Prime Numbers Using The Sieve Of Eratosthenes*/
#include<stdio.h>
#include<stdlib.h>
int main()
{
int *num;
int i, j, s_size, prime;

printf("Enter sieve size:n");
scanf("%0d", &s_size);
num = malloc(s_size*sizeof(int));

for(i = 0; i < s_size; i++)
num[i]=i+1;

for(i = 1; i < s_size; i++)
{
//Select the next non-zero number as the next prime.
if(num[i] != 0)
prime = num[i];
else
continue;

//Set all numbers occuring in steps of the selected prime to 0.
j = prime+prime;

while(j <= s_size)
{
num[j-1] = 0;
j += prime;
}

}

for(i=0;i<s_size;i++)
{
if(num[i]!=0)                    /*Print all non zero numbers (prime numbers)*/
printf("%dn",num[i]);
}
return 0;
}

```

Is This A Good Question/Topic? 0

## Replies To: Finding Prime Numbers Using The Sieve Of Eratosthenes

### #2 NSLogan

Reputation: 0
• Posts: 7
• Joined: 24-March 09

## Re: Finding Prime Numbers Using The Sieve Of Eratosthenes

Posted 24 March 2009 - 01:01 PM

poor scalability

### #3 kame.akbare

Reputation: 0
• Posts: 0
• Joined: 20-August 10

## Re: Finding Prime Numbers Using The Sieve Of Eratosthenes

Posted 20 August 2010 - 03:33 PM

I want program : find prime large numbers latest numbers 150 digit mail: [email protected]

### #4 Karel-Lodewijk

Reputation: 454
• Posts: 864
• Joined: 17-March 11

## Re: Finding Prime Numbers Using The Sieve Of Eratosthenes

Posted 24 January 2012 - 02:39 PM

This snippet does not actually implement sieve of Eratosthenes. When you find a prime you should take steps of prime through the list and remove exactly those elements. What you do is take steps of one through a list and do trial division.