finding prime numbers

[tones1986]

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...

[stilllearning]

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

[tones1986]

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;
}

[gregorynoob]

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

#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;
}

[tones1986]

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!

[tones1986]

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?

[VernonDozier]

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.

[tones1986]

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!

[VernonDozier]

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.

[tones1986]

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...

int input;
...
cin >> input;
...
sieve(intSet, input);

SIEVE function:
void sieve(set<int>& intSet, int n)
{
...

that should explain where N is coming from...

and as i mentioned... the infinte loop is not a problem anymore, my problem is the output ... it does not get rid of ALL the non-prime numbers, just 2,4,8 instead of 2,4,6,8,9,10 --- i should be left with only 3,5,7

Hope this makes sense, thanks for posting and plz help again if possible

[VernonDozier]

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);      
}

Line 15 - You are deleting too much in this line. What if *k == *m? Do you want to delete then?

Line 16 - problem. You are deleting the element your iterator is pointing to. When I ran your code, this was a problem when *m equaled 2 and *k = 12. Once you deleted 12, the next time the iterator was incremented, it pointed to 300,000 or some nonsense number and thus bailed out of you inner loop too soon, thus not deleting numbers it needed to. Make sure your iterator is not pointing to an element that is about to be deleted. Make a temporary integer variable called temp and store *k in it. then back up the k iterator by 1 so it is still pointing to something that is going to still be in the set. THEN delete temp, not *k. That way the iterator is going to go through the whole list and you won't risk short-circuiting your inner loop by not iterating past a deleted element.

[VernonDozier]

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...

int input;
...
cin >> input;
...
sieve(intSet, input);

SIEVE function:
void sieve(set<int>& intSet, int n)
{
...

that should explain where N is coming from...

and as i mentioned... the infinte loop is not a problem anymore, my problem is the output ... it does not get rid of ALL the non-prime numbers, just 2,4,8 instead of 2,4,6,8,9,10 --- i should be left with only 3,5,7

Hope this makes sense, thanks for posting and plz help again if possible

Actually I'm referring to the n in 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);

Is this line supposed to be this:

for (int i = 2; i <= input; i++)   // was n before

I don't understand this line in your function:

if (*k >= limit)
         intSet.erase(*k);

If n = 100, then limit = 10, so you'll be deleting 11, 13, 17, etc.?

[tones1986]

Good points and thank you for your input...

You were correct in saying the N in main should have been input, not N...

I had emailed my TA about this assignment and his help was the following:

I changed a couple of things that should now make it work according to my teaching assistant.

#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
   cout << "Input a max: ";
   cin >> input;
   //creates the list set from 2 to input value
   for (int i = 2; i <= input; 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); 
cout << endl;

int limit = (int)sqrt(n);

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

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

The bolded statements are ones that i changed. I am having an error with the underlined section that says;

47 C:\Users\Tony\Documents\school\Fall 08\CSCI 340\Assign3\assign3.cc invalid conversion from `int' to `const std::_Rb_tree_node<int>*'
47 C:\Users\Tony\Documents\school\Fall 08\CSCI 340\Assign3\assign3.cc initializing argument 1 of `std::_Rb_tree_const_iterator<_Tp>::_Rb_tree_const_iterator(const std::_Rb_tree_node<_Tp>*) [with _Tp = int]'

If i could get any input as to why im getting this error please let me know, as always ill update you on my progess (sorry for not replying for a while, i was at work all day, now working all night on it)..

THanks in advance

[VernonDozier]

for (set<int>::const_iterator m = intSet.begin(); *m <= limit; ++m)
{
   for (set<int>::const_iterator k = (*m + 1); *k <= n; ++k)
   {
      if (*k % *m == 0 || *k >= limit)
         intSet.erase(*k); 
      intSet.erase(*m * *k);
   }      
}

You are comparing an iterator to an integer in red above. You could do something like this:

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

You may want to also check intSet.end () . *k <= n may not catch everything when the iterator goes "over the edge". I had some infinite loops that went away when I checked whether k equaled intSet.end () .

I'm still not sure about this code:

if (*k % *m == 0 || *k >= limit)
         intSet.erase(*k); 
      intSet.erase(*m * *k);

It looks like it is erasing prime numbers to me.

[tones1986]

You are correct. It does seem to be erasing some prime numbers. This program is becoming quite the pain. If you didn't have to use sets it would be so much easier.

Do you have any ideas how i could get it working then to delete only the non-primes. Obviously there is a way, esle i wouldn't have this assignment.

I am still looking into and changing things around. But the iterators are a pain...

As always, thanks for the help so far, just a little more needed!

[VernonDozier]

if (*k % *m == 0 || *k >= limit)
         intSet.erase(*k); 
      intSet.erase(*m * *k);

Line 1 above. Get rid of the OR condition. You are done with your limit variable as far as I can tell. You already have it in your outer loop. I don't see any place for it in your inner loop. So make it:

if (*k % *m == 0)

Line 3 - I suppose this line doesn't hurt, but you can delete it. Anything it would catch is going to get deleted on a subsequent follow throw. it might make the program faster, might not. I'm not sure.

Try changing line 1 and getting rid of line 3 and see what results you get. If you end up with any infinite loops, compare k to intSet.end () and if it is equal to it, bail out of the inner loop. If you still have problems after that, look back at my post and try to make sure that you are not deleting the number your iterator is pointing to. As I mentioned earlier, there were times when deleting that caused my iterator to go haywire, but sometimes it didn't. Be extra safe and make sure it's always pointing to something valid. But try the other suggestions first.

for (set<int>::const_iterator m = intSet.begin(); *m <= limit; ++m)
{
   for (set<int>::const_iterator k = m; *k <= n;)
   {
      ++k;
      if (*k % *m == 0)
      {
           // deletion code
      } 
   }      
}

[tones1986]

Doing more work with what you gave me (a big thank you by the way, very helpfull and easy to understand) i have come to get the following output:

2 3 4 5 6 7 8 9 10
2 3 5 7 8 9 10

So the only number that is delted is 6 (which is correct) but it should also delete 8,9,10 aswell correct?

I have to get to bed - but i just wanted to show you what i was getting after your input. I will work further with making sure i am not deleting any iterator pointers etc... because as you said, that could cause havoc.

Thanks very, very much for all of your help! Hope you can spare a little more time!

[VernonDozier]

Doing more work with what you gave me (a big thank you by the way, very helpfull and easy to understand) i have come to get the following output:

2 3 4 5 6 7 8 9 10
2 3 5 7 8 9 10

So the only number that is delted is 6 (which is correct) but it should also delete 8,9,10 aswell correct?

I have to get to bed - but i just wanted to show you what i was getting after your input. I will work further with making sure i am not deleting any iterator pointers etc... because as you said, that could cause havoc.

Thanks very, very much for all of your help! Hope you can spare a little more time!

Yes, it should delete 8, 9, and 10. Your code is short enough that it's probably easiest to post the current version each time. Anyone who hasn't read the rest of the thread (and I) can then copy and paste the newest program and run it and get exactly what you got. You can point out any changes you have made. Also, if you post results, make sure to mention what you entered for input. I imagine you are still inputting 100.

[Agni]

A math grad student at Rutgers [ http://recursed.blogspot.com/2008/07/rutgers-graduate-student-finds-new.html ] has come up with a formula which can generate infinite primes

Let a(1) = 7
Define: a(n) = a(n-1) + gcd(n,a(n-1))
Then the prime generator is : a(n) - a(n-1) [one needs to ignore the 1s and then ignore the repeated primes]

Ain't that beautiful !

[tones1986]

My up to date code is:

#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
   cout << "Input a max: ";
   cin >> input;
   //creates the list set from 2 to input value
   for (int i = 2; i <= input; 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); 
cout << endl;

int limit = (int)sqrt(n);

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

//test print of set from beg. -> end
copy(intSet.begin(), intSet.end(), screen);  
cout << endl;    
} 

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

I made a couple of changes. First off i deleted my || (or) statement from the IF. And removed the *m * *k erase line after that if within the inner loop. I removed these both b/c my TA told me they were not needed, just like you had mentioned, as the outter loops accomplish that already.

The other thing he mentioned to change was the inner loops initial starting point. He mentioned i should use:

for (set<int>::const_iterator [B]k = (m + 1); [/B]*k <= n; ++k)

The bold part, instead of ...k = (*m + 1)

But i get the following error with this line then:

46 C:\Users\Tony\Documents\school\Fall 08\CSCI 340\Assign3\assign3.cc no match for 'operator+' in 'm + 1'

Also, just so you know. i am using 10 as my input, so i should be getting this output
3 5 7

As of now i cant get output because the above error...

Thanks AGAIN

[VernonDozier]

My up to date code is:

#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
   cout << "Input a max: ";
   cin >> input;
   //creates the list set from 2 to input value
   for (int i = 2; i <= input; 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); 
cout << endl;

int limit = (int)sqrt(n);

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

//test print of set from beg. -> end
copy(intSet.begin(), intSet.end(), screen);  
cout << endl;    
} 

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

I made a couple of changes. First off i deleted my || (or) statement from the IF. And removed the *m * *k erase line after that if within the inner loop. I removed these both b/c my TA told me they were not needed, just like you had mentioned, as the outter loops accomplish that already.

The other thing he mentioned to change was the inner loops initial starting point. He mentioned i should use:

for (set<int>::const_iterator [B]k = (m + 1); [/B]*k <= n; ++k)

The bold part, instead of ...k = (*m + 1)

But i get the following error with this line then:

46 C:\Users\Tony\Documents\school\Fall 08\CSCI 340\Assign3\assign3.cc no match for 'operator+' in 'm + 1'

Also, just so you know. i am using 10 as my input, so i should be getting this output
3 5 7

As of now i cant get output because the above error...

Thanks AGAIN

Yes, that is why I suggested taking the ++k out of the for statement and sticking it at the top of the loop.

for (set<int>::const_iterator k = m; *k <= n;)
{
     ++k;
     // code
}

or keeping it the way you originally had it and adding a condition to the if statement:

for (set<int>::const_iterator k = m; *k <= n; ++k)
{
     if (*k % *m == 0 && *k != *m)
     {
          // deletion code
     }
}

There may well be a way to do it all in a for loop declaration, but I don't know how.

[Lerner]

Post deleted. Answer already provided.

[tones1986]

I have now come up with this for my loop.

#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
   cout << "Input a max: ";
   cin >> input;
   //creates the list set from 2 to input value
   for (int i = 2; i <= input; 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); 
cout << endl;

int limit = (int)sqrt(n);

/*for (set<int>::const_iterator m = intSet.begin(); *m <= limit; ++m)
{
   for (set<int>::const_iterator k = m; *k <= n;++k)
   {
      if (*k % *m == 0 && *k != *m)
         intSet.erase(k); 
   }      
}*/
for (set<int>::const_iterator m = intSet.begin(); *m <= limit; ++m)
{
    set<int>::const_iterator k = m;
    for (++k; *k <= n; ++k)
    {
      if (*k % *m == 0)
          intSet.erase(k);
    }
}

//test print of set from beg. -> end
copy(intSet.begin(), intSet.end(), screen);  
cout << endl;    
} 

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

Notice how i changed the 'inner loop' to for a little differently.

This, although it solves my problems with setting iterator to iterator or adding to iterators, still does not solve the problem.

For an input of 10, i get the following output:

2 3 5 7 8 9 10

Instead of the correct:

3 5 7

So my code is still not correct, the only values deleted are 4 and 6...instead of 2 4 6 8 9 10...

Anyone got ideas as to why this isnt working correctly? Am i missing something obvious?

[VernonDozier]

I got an infinite loop when I typed 10. I didn't get the results you got. You got it to run to completion? Reread some of my earlier posts. You have a definite problem where the iterator is going to the last element and then backtracking to a prior element. Run the code below, enter 10, and see if you get an infinite loop of 9's and 10's. Note that the deletion code is commented out and thus has no effect. Then uncomment the for-loop and see if that works better.

for (set<int>::const_iterator m = intSet.begin(); *m <= limit; ++m)
{
    set<int>::const_iterator k = m;
    for (++k; *k <= n /* && k != intSet.end () */; ++k)
    {
        cout << *k << endl;
//        if (*k % *m == 0)
//            intSet.erase(k);
    }
}

[Lerner]

Every value of *m tested will be prime, which means m must go all the way to end of the container. Likewise k is every value remaining in the container of greater value than m every time through the loop, so k must go to the end of the container as well. So n should equal limit, though I haven't looked back far enough to determine if it does or not.

I'd set up a display to determine the values remaining in the container after each loop through the inner loop or set up a display to show each value that is determined not to be prime. If I were using an array it might look like this:

int nums[] = {2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
for(int i = 2; i <= 11; ++i)
{
    if(nums[i - 2] != 0)
    {
       cout << i  << " is prime" << endl;
       cout << "looking for multiples of " << i << endl;
  
       for(int j = i + 1; j <= 11; ++j)
       {
         if(nums[j - 2] != 0 && (nums[j - 2]  % i == 0))
         {
             cout << nums[j - 2] << " is not prime" << endl;
             nums[j - 2] = 0; 
          }
        }
    }
}

cout << "the following numbers are prime"  << endl;
for(int i = 0; i < 10; ++i)
{
  if(nums[i] != 0)
  {
    cout << nums[i] << ' ';
  }
}

Output should be:
2 is prime
looking for multiple of 2
4 is not prime
6 is not prime
8 is not prime
10 is not prime
3 is prime
looking for multiples of 3
9 is not prime
5 is prime
looking for multiples of 5
7 is prime
looking for multiples of 7
11 is prime
the following numbers are prime
2, 3, 5, 7, 11

Admittedly I have not compiled or ran this code so I could be off by an index or 2, but I'm pretty confident of the process and the example.

[tones1986]

Thanks for the post, your idea about inserting cout statements was simple but may help myself and others what might be going on within my code/loop.

I changed my code to look like this:

#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
   cout << "Input a max: ";
   cin >> input;
   //creates the list set from 2 to input value
   for (int i = 2; i <= input; 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); 
cout << endl;

int limit = (int)sqrt(n);

/*for (set<int>::const_iterator m = intSet.begin(); *m <= limit; ++m)
{
   for (set<int>::const_iterator k = m; *k <= n;++k)
   {
      if (*k % *m == 0 && *k != *m)
         intSet.erase(k); 
   }      
}*/
for (set<int>::const_iterator m = intSet.begin(); *m <= limit; ++m)
{
    set<int>::const_iterator k = m;
    for (++k; *k <= n; ++k)
    {
      if (*k % *m == 0)
          {
          intSet.erase(k);   
[B]          cout << *k << " is not prime" << endl;[/B]
          }
    }
    [B]cout << *m << " is prime" << endl;[/B]
}

//test print of set from beg. -> end
copy(intSet.begin(), intSet.end(), screen);  
cout << endl;    
} 

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

So thats all i added and got interesting results...

Input a max: 10
2 3 4 5 6 7 8 9 10 - complete set
4 is not prime
2 is prime
6 is not prime
3 is prime
2 3 5 7 8 9 10 - set after deletions

So obviously for some reason the loop isnt going past 6/7? Not sure why lol. Any ideas?

Thanks again as always. Thanks for the patience especially.

[VernonDozier]

Like I've mentioned before, you need to make sure your iterator is always pointing to something and that that something is dereferencable. Just because you are not getting errors and the program isn't crashing doesn't mean your code is correct. Some programs are going to give you an error here at runtime:

*k <= n

when k has gone past the last element. Some won't. To avoid that, you need to check to make sure k != inSet.end () before trying to use *k.

Also, remember back to when I talked about deleting the element your iterator is pointing to? Sometimes you get lucky, sometimes you don't, but if you delete the element your iterator is pointing to, don't assume the iterator is going to know how to keep iterating. You need to back the iterator up so it's no longer pointing to the number to be deleted, THEN delete. Try this:

for (set<int>::const_iterator m = intSet.begin(); *m <= limit; ++m)
{
    set<int>::const_iterator k = m;
    for (++k; k != intSet.end () && *k <= n; ++k)
    {
      if (*k % *m == 0)
      {
          int temp = *k;
          k--;
          intSet.erase(temp);   
          cout << temp << " is not prime" << endl;
      }
    }
    cout << *m << " is prime" << endl;
}

[Lerner]

I got it to work by dropping limit completely
letting m range from intSet.begin() to intSet.end(), assigning m to k, incrementing k by 1, and then letting k range to intSet.end(), too. To account for the fact that erase() returns an iterator to the next object beyond the object erased, or end() if the last object was erased, I used this syntax:

if (*k % *m == 0)
{
     k = intSet.erase(k); 
}

But, since the code will skip over this *k if the current k is incremented in the for loop, I too needed to go back to the iterator before the erased k by decrementing the current value of k, like this:

if (*k % *m == 0)
{
     k = intSet.erase(k); 
     --k;
}

[VernonDozier]

I got it to work by dropping limit completely
letting m range from intSet.begin() to intSet.end(), assigning m to k, incrementing k by 1, and then letting k range to intSet.end(), too. To account for the fact that erase() returns an iterator to the next object beyond the object erased, or end() if the last object was erased, I used this syntax:

if (*k % *m == 0)
{
     k = intSet.erase(k); 
}

But, since the code will skip over this *k if the current k is incremented in the for loop, I too needed to go back to the iterator before the erased k by decrementing the current value of k, like this:

if (*k % *m == 0)
{
     k = intSet.erase(k); 
     --k;
}

I get an error with this line:

k = intSet.erase(k);

Here are the three options for set::erase from cplusplus.com:
http://www.cplusplus.com/reference/stl/set/erase.html

void erase ( iterator position );
size_type erase ( const key_type& x );
     void erase ( iterator first, iterator last );

The one it is calling is the one in red, I believe, which returns a void, so it looks to me like the compiler doesn't like the assignment operation. This compiled for you?

[Lerner]

set::erase
iterator erase(iterator it);
iterator erase(iterator first, iterator last);
size_type erase(const Key& key);

My current compiler, VC++ 6.0, lists the above versions of the erase() method for set. Assuming your compiler is more up to date and/or more standards compliant than this old compiler then yours is probably the prefered implementation. I do see that the void return type for several of the erase() methods of the set class is the correct syntax per Josuttis in his book The C++ Standard Library.