# sieve of eratosthenes

Page 1 of 1

## 10 Replies - 8727 Views - Last Post: 26 February 2010 - 08:43 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=157003&amp;s=06297be8e05857e1dbcd625631cf06e2&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 cburkovi

Reputation: 1
• Posts: 56
• Joined: 03-February 10

# sieve of eratosthenes

Posted 19 February 2010 - 08:17 AM

My professor gave us an assignment to look up the Sieve of Eratosthenes
I found many different sites that describe the topic but what I basically understand is that it is a list of prime numbers. Write? so I wrote this and after I did I found that it looks like I plagiarized it form someone. What should I do?
```#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int main(){
int i;
printf("Find primes up to: ");
scanf("%i",&i);

double t = 0.0;

//create prime list
int prime[i];
int c1, c2, c3;

//fill list with 0 - prime
for(c1 = 2; c1 <= i; c1++){
prime[c1] = 0;
}

//set 0 and 1 as not prime
prime[0]=1;
prime[1]=1;

//find primes then eliminate their multiples (0 = prime, 1 = composite)
for(c2 = 2;c2 <= (int)sqrt(i)+1;c2++){
if(prime[c2] == 0){
c1=c2;
for(c3 = 2*c1;c3 <= i+1; c3 = c3+c1){
prime[c3] = 1;
}
}
}

//print primes
for(c1 = 0; c1 < i+1; c1++){
if(prime[c1] == 0) printf("%i\n",c1);
}

system("pause");
return 0;
}
```

Is This A Good Question/Topic? 0

## Replies To: sieve of eratosthenes

### #2 baavgai

• Dreaming Coder

Reputation: 7291
• Posts: 15,178
• Joined: 16-October 07

## Re: sieve of eratosthenes

Posted 19 February 2010 - 08:47 AM

cburkovi, on 19 February 2010 - 09:17 AM, said:

looks like I plagiarized it form someone. What should I do?

You know you have to make an array. Now, without looking at anyone else, write your own. The sqrt thing is a cuteness. A lot of the code you'll find plays tricks to shorten things; ignore them. Writing your own will teach you so much more.

Look at examples, then look away. There is no one right way to program anything. Find your own path. You can do it.

Reputation:

## Re: sieve of eratosthenes

Posted 19 February 2010 - 10:08 AM

isn't that what I did

### #4 xTorvos

• D.I.C Regular

Reputation: 61
• Posts: 271
• Joined: 23-October 09

## Re: sieve of eratosthenes

Posted 19 February 2010 - 10:22 AM

Huh, that's funny. It does look like you plagerized it. In fact, it looks like you stole it almost line-for-line from here:
http://www.dreaminco...snippet3315.htm

Maybe next time you should do some of the thinking on your own.

Just my .02

Reputation:

## Re: sieve of eratosthenes

Posted 19 February 2010 - 10:30 AM

from what I see it looks like 2 people could have the same Ideas by total accident but I agree change your code to not look like you stole it dude you suck make your own

### #6 NickDMax

Reputation: 2255
• Posts: 9,245
• Joined: 18-February 07

## Re: sieve of eratosthenes

Posted 19 February 2010 - 10:35 AM

The Sieve of Eratosthenes is really not hard at all. I recommend doing on paper once:

take a pice of graph paper and fill a 10x10 grid with all of the numbers between 1 and 100. Cross out 1:

step 2: find and circle the first number not crossed out (should be 2 the first time).
step 3: cross out all multiples of the circled number (for example for 2 cross out all even numbers).
step 4: if not done goto step 2.

So that is really easy to do on paper now you need to think about how to do it in code... its still easy but you have to think about how to get the computer to do it.

#1 you need a list of numbers... an array will work.
#2 you need a way of telling if they are circled or crossed out or un-touched. -- generally I don't do anything special for "circled" I just use some kind of pointer or index to keep track of the last "circled" number. So I generally fill the array with the numbers 0 - N and when I "cross out" a number I set it to 0. So when I am looking for the next number I just look for the next non-zero entry. (but lots of different ways to do this -- some people use 1 and 0 -- whatever works for you).

once you work out how you will implement #1 and #2 -- its generally pretty easy for that point.

### #7 cburkovi

Reputation: 1
• Posts: 56
• Joined: 03-February 10

## Re: sieve of eratosthenes

Posted 19 February 2010 - 10:51 AM

I would like to say thanks to everyone yes I did write what you see by myself and now I know what needs to be done but how do I circle the primes in the array

### #8 NickDMax

Reputation: 2255
• Posts: 9,245
• Joined: 18-February 07

## Re: sieve of eratosthenes

Posted 19 February 2010 - 08:11 PM

Well you might "circle" a number by not crossing it out (setting it to zero) when you begin to loop though the multiples.

so if you have the array
1 2 3 4 5 6 7 8 9 10

start by setting 1 to 0

0 2 3 4 5 6 7 8 9 10

"circle the first number and cross out all multiples"

0 2 3 0 5 0 7 0 9 0

then find the next number not crossed out 3

0 2 3 0 5 0 7 0 0 0

once you reach 7 you find that there are no more non-zero numbers. So the primes are all of the non-zero numbers

2 3 5 7

BUT, this is BY FAR not the only way you can do this. For example you might "circle" a number by putting it into an array of primes, this saves you from having to scan the array for them later.

find a way that makes sense to YOU.

Reputation:

## Re: sieve of eratosthenes

Posted 26 February 2010 - 08:07 AM

cburkovi, on 19 February 2010 - 07:17 AM, said:

My professor gave us an assignment to look up the Sieve of Eratosthenes
I found many different sites that describe the topic but what I basically understand is that it is a list of prime numbers. Write? so I wrote this and after I did I found that it looks like I plagiarized it form someone. What should I do?
```#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int main(){
int i;
printf("Find primes up to: ");
scanf("%i",&i);

double t = 0.0;

//create prime list
int prime[i];
int c1, c2, c3;

//fill list with 0 - prime
for(c1 = 2; c1 <= i; c1++){
prime[c1] = 0;
}

//set 0 and 1 as not prime
prime[0]=1;
prime[1]=1;

//find primes then eliminate their multiples (0 = prime, 1 = composite)
for(c2 = 2;c2 <= (int)sqrt(i)+1;c2++){
if(prime[c2] == 0){
c1=c2;
for(c3 = 2*c1;c3 <= i+1; c3 = c3+c1){
prime[c3] = 1;
}
}
}

//print primes
for(c1 = 0; c1 < i+1; c1++){
if(prime[c1] == 0) printf("%i\n",c1);
}

system("pause");
return 0;
}
```

Reputation:

## Re: sieve of eratosthenes

Posted 26 February 2010 - 08:30 AM

Here is my solution to the problem:
```#include <iostream>
#include <stdlib.h>
#include <cmath>
#include<iomanip>
using namespace std;

int main(  )
{
const int MAXSIZE=1000;
bool primes[MAXSIZE];
int size=sqrt(MAXSIZE)+1;
int i,j,counter;
enum tval{ FALSE=0,TRUE=1};
// initialise prime array
for(i=0;i<MAXSIZE;i++)
if( i % 2 !=0   && i % 3 !=0 && i % 5 !=0 & i % 7 !=0 )
primes[i]=TRUE;
else
primes[i]=FALSE;

// if primes are multiple initialise them to false;
for(i=2;i<=size;i++)
if( i % 2==0   && i % 3 ==0 && i % 5==0 & i % 7 ==0 )
primes[i]=FALSE;

//print em out
for(i=1,counter=0;i<=MAXSIZE;i++)
if(primes[i])
{ cout<<setw(5)<<i;
if (++counter %12==0)
cout<<endl;
}

system("Pause");
}

```

You can see the readout for 1000 primes

I tried many variants of the above
algorithm and it didn't work

### #11 NickDMax

Reputation: 2255
• Posts: 9,245
• Joined: 18-February 07

## Re: sieve of eratosthenes

Posted 26 February 2010 - 08:43 AM

Sorry... your program does not work: 979 -- not prime and I am sure there are plenty of others others... like multiple of 13 like say 169 is on your list 289 = 17*17 is on your list.

Back to the drawing table. Read over the sieve carefully, it is one of the fastest and easiest methods for finding primes.