•
•
•
•
What is DaniWeb IT Discussion Community?
You're currently browsing the C++ section within the Software Development category of DaniWeb, a massive community of 456,475 software developers, web developers, Internet marketers, and tech gurus who are all enthusiastic about making contacts, networking, and learning from each other. In fact, there are 2,756 IT professionals currently interacting right now! Registration is free, only takes a minute and lets you enjoy all of the interactive features of the site.
Please support our C++ advertiser: Programming Forums
Views: 1181 | Replies: 35
 |
•
•
Join Date: Jan 2008
Posts: 1,995
Reputation: 
Rep Power: 8
Solved Threads: 243
•
•
•
•
Originally Posted by 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 k = (m + 1); *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.
•
•
Join Date: Jul 2005
Posts: 1,288
Reputation:
Rep Power: 9
Solved Threads: 175
Post deleted. Answer already provided.
Last edited by Lerner : Oct 1st, 2008 at 2:49 pm.
•
•
Join Date: Feb 2005
Posts: 92
Reputation:
Rep Power: 4
Solved Threads: 0
Junior Poster in Training
I have now come up with this for my loop.
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?
#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?
•
•
Join Date: Jan 2008
Posts: 1,995
Reputation:
Rep Power: 8
Solved Threads: 243
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);
}
} •
•
Join Date: Jul 2005
Posts: 1,288
Reputation:
Rep Power: 9
Solved Threads: 175
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:
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.
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.
•
•
Join Date: Feb 2005
Posts: 92
Reputation:
Rep Power: 4
Solved Threads: 0
Junior Poster in Training
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:
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.
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);
cout << *k << " is not prime" << endl;
}
}
cout << *m << " is prime" << endl;
}
//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.
•
•
Join Date: Jan 2008
Posts: 1,995
Reputation:
Rep Power: 8
Solved Threads: 243
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:
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:
*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;
} •
•
Join Date: Jul 2005
Posts: 1,288
Reputation:
Rep Power: 9
Solved Threads: 175
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:
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:
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);
}if (*k % *m == 0)
{
k = intSet.erase(k);
--k;
} •
•
Join Date: Jan 2008
Posts: 1,995
Reputation:
Rep Power: 8
Solved Threads: 243
•
•
•
•
Originally Posted by 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: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); }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?
•
•
Join Date: Jul 2005
Posts: 1,288
Reputation:
Rep Power: 9
Solved Threads: 175
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.
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.
|
•
•
•
•
•
•
•
•
DaniWeb C++ Marketplace
•
•
•
•
Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
Linear Mode
Similar Threads
- finding prime numbers that add up to even number? (C)
- finding prime numbers problem (C++)
- C++ prime number program help (C++)
- Finding Prime numbers without using Boolean (C++)
- C++ Finding Prime Numbers (C++)
Other Threads in the C++ Forum
- Previous Thread: need help starting up .
- Next Thread: Need major help-Segmentation fault
