sieve of eratosthenes

this is an assignment so

Page 1 of 1

10 Replies - 8080 Views - Last Post: 26 February 2010 - 08:43 AM Rate Topic: -----

#1 cburkovi   User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • 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   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7183
  • View blog
  • Posts: 14,970
  • Joined: 16-October 07

Re: sieve of eratosthenes

Posted 19 February 2010 - 08:47 AM

View Postcburkovi, on 19 February 2010 - 09:17 AM, said:

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


Read the wikipedia entry: http://en.wikipedia....of_Eratosthenes

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

#3 Guest_Guest*


Reputation:

Re: sieve of eratosthenes

Posted 19 February 2010 - 10:08 AM

isn't that what I did
Was This Post Helpful? 0

#4 xTorvos   User is offline

  • D.I.C Regular
  • member icon

Reputation: 61
  • View blog
  • 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
Was This Post Helpful? 0
  • +
  • -

#5 Guest_Guest*


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
Was This Post Helpful? 0

#6 NickDMax   User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2255
  • View blog
  • 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.
Was This Post Helpful? 1
  • +
  • -

#7 cburkovi   User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • 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
Was This Post Helpful? 0
  • +
  • -

#8 NickDMax   User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2255
  • View blog
  • 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

tada..

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

#9 Guest_Petr_Kropotkin*


Reputation:

Re: sieve of eratosthenes

Posted 26 February 2010 - 08:07 AM

View Postcburkovi, 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;
}

Was This Post Helpful? 0

#10 Guest_Petr_Kropotkin*


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

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

Was This Post Helpful? 0

#11 NickDMax   User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2255
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1