DaniWeb Home &gt; Forums &gt; Software Development &gt; C++

Offline

Junior Poster in Training

finding prime numbers

Sep 30th, 2008

Hey All - i am currently working on an assignment for a computer science programming class. I have to find and print all the prime numbers from 2 to N (N being a number read in from file).

I have some code but i do can not get my mind around one of the main concepts. I have to use the sieve of eratosthenes. This, from what i have read elsewhere online and mentioned in my assignment notes goes something like this:

you take an array of numbers, say 1 - 100 and then do,

2 * 2 = 4, 4 *2 = 8, 8 * 2 = 16 ... etc etc... while doing this, you delete the value from the array ( set it to zero - for error checking later while printing). But then you take... say 3 and do 3 * 2 = 6, 6 * 2 = 12, .... etc ...

Is this correct? Or do i have the idea of it completely incorrect... ?

As always i have done some minor work on this so far, but without a correct understanding of the sieve algorithm im not going to get very far. I will post my attempt below, i ask not that you give me code by any means, but just a hand with understanding the concept the of the sieve algo.

Thanks to everyone in advance, here is my feeble attempt w/o knowing what i truly have to do:

void sieve(set<int>& intSet, int n)
{
ostream_iterator<int> screen(cout, " ");     
     
int i = n;
int j = 2;
  // K is the value that will be multiplied
  for (int k = 2; k < n; k = k * j)
     {
        cout << "Will erase value: " << k << endl;
        intSet.erase(k);
        j++;
        k++;
     }
     
for (int h = 2; h < i;h++)
    {
    cout << "value of h = ";
    copy(intSet.begin(), intSet.end(), screen);
    cout << endl;
    }
}

Using an input value of 10, give me the following output:
10
Will erase value: 2
Will erase value: 9
value of h: 3 4 5 6 7 8
value of h: 3 4 5 6 7 8
value of h: 3 4 5 6 7 8
value of h: 3 4 5 6 7 8
value of h: 3 4 5 6 7 8
value of h: 3 4 5 6 7 8
value of h: 3 4 5 6 7 8
value of h: 3 4 5 6 7 8

Hope i can get a hand with understand this concept better...

Last edited by tones1986 : Sep 30th, 2008 at 1:51 am. Reason: missed [code] end tag

•

Join Date: Oct 2007

Posts: 302

Reputation: stilllearning has a spectacular aura about

Rep Power: 3

Solved Threads: 37

stilllearning stilllearning is offline

Offline

Posting Whiz

Re: finding prime numbers

Sep 30th, 2008

A fairly simple explanation of how you can use the sieve of eratosthenes here

•

Join Date: Feb 2005

Posts: 92

Reputation: tones1986 is an unknown quantity at this point

Rep Power: 4

Solved Threads: 0

Offline

Junior Poster in Training

Re: finding prime numbers

Sep 30th, 2008

Thanks for the link - i had already found that very useful in its explanation. I did some more google searches and now seem to understand the concept well.

So, please stick with me here while i try doing this in my own words/psuedo code, please correct me if i am wrong.

for (2 to n - n being maxsize)
insert value from 2 - n into array/set
for j is beginning value to limit (sqrt n(maxsize)
   set.erase( i * j);

Woudl something along these lines work? Because i have created the list by doing line 2, i tested this by out putting the info, and say if the maxsize input was 10, i would get:
2 3 4 5 6 7 8 9 10

So that seems to be correct. Now for processing the set/array. I use the member function erase() which will erase whatever the value i send it is, correct? So doing i * j would do:
2 * 2; (i is 2, outter for loop ... set to 2, then increments) (j is set to begin value, then increments)
2 * 3;
... etc

Is this correct logic? I am working on it still - but i dont want to be going way off track and confusing myself... so please help with a little input if possible.

As always, no code if you can help, pseudo code would be just fine, i dont want answers, just a gently nudge in the right direction!

Thanks in advance

***EDIT

Using the following code i get an infinite loop within the nester for loop. Not sure quite why yet, but any ideas / comments would be great. Thank you.

for (int i = 2; i <= n; i++)                      
{ 
    intSet.insert(i);
    double limit = sqrt(n);
    cout << "in outter loop" << endl;
       for (set<int>::const_iterator j = intSet.begin(); *j <= limit; j++)
         {
         cout << "in innner loop" << endl;
         intSet.erase((*j * n));
         }
         cout << "after inner loop" << endl;
}

Last edited by tones1986 : Sep 30th, 2008 at 1:17 pm. Reason: posted too early - typo

•

Join Date: Jun 2008

Posts: 86

Reputation: gregorynoob is an unknown quantity at this point

Rep Power: 1

Solved Threads: 5

gregorynoob gregorynoob is offline

Offline

Junior Poster in Training

Re: finding prime numbers

Sep 30th, 2008

well this is a simple implementation of the sieve...

 Help with Code Tags 
 c++ Syntax (Toggle Plain Text) 
#include <cstdio>
#define MAX 100000
 
bool prime[ MAX ];
 
void sieve() {
     for( int i = 0; i < MAX; ++i ) prime[i] = 1;
     prime[1] = 0;
     for( int i = 2; i < MAX; ++i )
          for( int j = 2*i; j < MAX; j += i )
               prime[j] = 0;
}
 
int main( void )
{
    sieve();
    for( int i = 1; i <= 100; ++i )
         if( prime[i] ) printf( "%d\n", i );
 
    scanf( "\n" );
    return 0;
}
#include <cstdio>
#define MAX 100000

bool prime[ MAX ];

void sieve() {
     for( int i = 0; i < MAX; ++i ) prime[i] = 1;
     prime[1] = 0;
     for( int i = 2; i < MAX; ++i )
          for( int j = 2*i; j < MAX; j += i )
               prime[j] = 0;
}

int main( void )
{
    sieve();
    for( int i = 1; i <= 100; ++i )
         if( prime[i] ) printf( "%d\n", i );
    
    scanf( "\n" );
    return 0;
}

•

Join Date: Feb 2005

Posts: 92

Reputation: tones1986 is an unknown quantity at this point

Rep Power: 4

Solved Threads: 0

Offline

Junior Poster in Training

Re: finding prime numbers

Sep 30th, 2008

You are right, that IS easy. I understand that logic without any problems, you are just setting bool values of false to non-primes within an array, then going through and printing all values that are non-false (ie true - or in this 1/0).

In my case though, i have to use a set to store my data. I am inputting a range for my values, say 10.

I then do this:

for (int i = 2; i <= n; i++)                      
{ 
    intSet.insert(i);
}

To create a set filled with all numbers from 2-n (in my case lets just say 10 for now)
I use this to print the line for testing purposes"

ostream_iterator<int> screen(cout, " "); 
...
...
//prints out initial set data 2 to n
copy(intSet.begin(), intSet.end(), screen);

And this outputs my correct values: 2 3 4 5 6 7 8 9 10

My next aim is to use an iterator to go through the set and calculate whats a prime and what isnt. In doing this, i created 2 for loops, with one nested inside the other. Such as:

// sets limit to sqrt of max (10)
double limit = sqrt(n);

for (set<int>::const_iterator m = intSet.begin(); *m <= n; ++m)
{
   for (set<int>::const_iterator k = intSet.begin(); *k <= n; ++k)
   {
    
   }  
}

This code above gives me an infinite loop within the nested k iterator loop. So somehow i need to do erasing here maybe:

intSet.erase(*m * *n);

Which would take 2 * 2 = 4, and erase 4 from the list... then it should loop and do 3 * 3 = 6 and remove 6, then 4 * 4 = 8 and remove 8 and so on.

Is this correct? If so, why would i be getting an infinte loop within the nested loop.

Thanks again for your help... please feel free to include sample code if you think it helps. I just don't want answers given to me in complete!

•

Join Date: Feb 2005

Posts: 92

Reputation: tones1986 is an unknown quantity at this point

Rep Power: 4

Solved Threads: 0

Offline

Junior Poster in Training

Re: finding prime numbers

Sep 30th, 2008

I made a mistake with my logic on the last part above.

If i put this line:

intSet.erase(*m * *n);

Inside the nested for loop, it would do this, at least i think it would:
2 * 3 = 6 (rm 6)
2 * 4 = 8 (rm 8)
2 * 5 = 10 (rm 10)
etc

BUT i just noticed that i do this:

double limit = sqrt(n);

The value of n is 10. So the SQRT(10) is something like 3.16. So the loop would only loop 3 times... so i should get this:

2 * 3 = 6
2 * 4 = 8
2 * 5 = 10

But that doesnt seem to work!

int limit = (int)sqrt(n);

for (set<int>::const_iterator m = intSet.begin(); *m <= limit; ++m)
{
   for (set<int>::const_iterator k = intSet.begin(); *k <= limit; k++)
   {
      intSet.erase(*m * *k);
   }  
}

Now gives me output:
Orig set = 2 3 4 5 6 7 8 9 10
New set after loop = 2 3 5 7 8 10

So im unsure whats being multipled and why!

Any help? Thanks

***EDIT

Now edited with cout statements to get whats being multiplied and got:
2 * 2 = 4
2 * 3 = 6
3 * 2 = 6
3 * 3 = 9

So 4, 6, 9 are correctly removed while 2,8,10 incorrectly remain....
As mentione dbefore only goes to three because limit = (int)sqrt(10) = 3... so never counts higher, if i manually put 10 as limit for loop such as :

for (set<int>::const_iterator m = intSet.begin(); *m <= 10; ++m)
{
   for (set<int>::const_iterator k = intSet.begin(); *k <= 10; k++)
   {
      cout << "( " << *m << " * " << *k << " ) = " << *m * *k << endl;
 /* if (*m % 2 == 0)
         intSet.erase(*m); */
      intSet.erase(*m * *k);
   }      
}

I get an infinite loop in my nested looop again for some reason. Any ideas?

Last edited by tones1986 : Sep 30th, 2008 at 3:40 pm.

•

Join Date: Jan 2008

Posts: 1,995

Reputation: VernonDozier is just really nice

Rep Power: 8

Solved Threads: 243

VernonDozier VernonDozier is offline

Offline

Posting Virtuoso

Re: finding prime numbers

Sep 30th, 2008

I haven't tried your code yet, but is there a reason why you are using a set rather than a regular boolean array?

•

In my case though, i have to use a set to store my data.

Is this an assignment where the object is to demonstrate that you can use a set? if not, and if you are simply trying to find all of the primes from 1 to 100, I don't know how using a set has an advantage over using a boolean array. Also, can you please post your up-to-date full code? You've been posting the snippets that you've changed, but it might be easier if you posted the full program or function so we can simply copy and paste it and run it, plus we'll be sure we are running the most up to date version. Thanks.

•

Join Date: Feb 2005

Posts: 92

Reputation: tones1986 is an unknown quantity at this point

Rep Power: 4

Solved Threads: 0

Offline

Junior Poster in Training

Re: finding prime numbers

Sep 30th, 2008

THis is my full code:

#include <iostream>
#include <set>
#include <iterator>
#include <cmath>

using namespace std;

void sieve(set<int> &, int);
void print_primes(const set<int>&);

int main()
{
   set<int> intSet;
   int input;
   
   //gets input from file or keyboard
   cin >> input;
   //creates the list set from 2 to input value
   for (int i = 2; i <= n; i++)                      
   { 
    intSet.insert(i);
   }
       
   sieve(intSet, input);
   system("PAUSE");
    return 0;
}

void sieve(set<int>& intSet, int n)
{
ostream_iterator<int> screen(cout, " ");     

//prints out initial set data 2 to n
copy(intSet.begin(), intSet.end(), screen); 

int limit = (int)sqrt(n);

for (set<int>::const_iterator m = intSet.begin(); *m <= limit; ++m)
{
   for (set<int>::const_iterator k = intSet.begin(); *k + 1 <= n; k++)
   {
      //cout << "( " << *m << " * " << *k << " ) = " << *m * *k << endl;
      if (*k % *m == 0)
         intSet.erase(*k); 
      intSet.erase(*m * 2);
      if (*k >= limit)
         intSet.erase(*k);
   }      
}
//test print of set from beg. -> end
copy(intSet.begin(), intSet.end(), screen);      
} 

void print_primes(const set<int> & s)
{
     
}

Sorry i didn't post entire thing previously!

Hope this helps.

The idea of the assignment is to understand basic set structure and to use iterators... both of which are new to the class.

Thanks!

Last edited by tones1986 : Sep 30th, 2008 at 4:23 pm.

•

Join Date: Jan 2008

Posts: 1,995

Reputation: VernonDozier is just really nice

Rep Power: 8

Solved Threads: 243

VernonDozier VernonDozier is offline

Offline

Posting Virtuoso

Re: finding prime numbers

Sep 30th, 2008

This line:

   for (int i = 2; i <= n; i++)

does not compile since you never define an n variable. What is n supposed to be and what do you enter for input to get the infinite loop? I made n = 100 and input = 10 and I didn't get an infinite loop.

•

Join Date: Feb 2005

Posts: 92

Reputation: tones1986 is an unknown quantity at this point

Rep Power: 4

Solved Threads: 0

Offline

Junior Poster in Training

Re: finding prime numbers

#10

Sep 30th, 2008

Your right you wont get an infinite loop any more because i changed the FOR loops to be correct... the N value is passed in from main. N is the value that you type in when asked for a number initially - heres all that stuff...