### Prime number seive help?

I saw that there has been a TON of messages regarding this on here recently and I hope that this isn't going to hit the cap on the "Sieve of E." (I can't spell that guys name... :/ )
Last edited on
Heres an example using a vector of bools
 ``12345678910111213141516171819202122232425262728293031323334353637`` ``````#include #include #include #include int main() { const std::size_t size = 100000; //initialize all numbers as "prime" std::vector primes(size, true); int sq = std::sqrt(size); for(int i = 2; i < sq; ++i) { if(primes[i])//if i is prime set all multiples to false (not prime) { for(int j = 2; j*i < size; ++j ) { if(primes[i * j]) primes[j * i] = false; } } } //output in pretty columns int c = 1;//counter used for formatting for(int i = 1; i < size; ++i) { if(primes[i]) { std::cout << std::setw(7) << i << " "; if(c % 14 == 0) std::cout << std::endl; ++c; } } }``````
 Does this look ok?

Given: `vector<int>& primes`

`set<int>::iterator m = primes.begin();` definitely does not look ok.
Last edited on
Here is the updated code. Any suggestions?

 ``123456789101112131415161718192021222324`` `````` void findVectorPrimes(int num, vector& v, set& primes) { int squareRoot = sqrt(num); vector::iterator m = v.begin(); while (*m <= squareRoot) { for (size_t k = *m; k <= num; k++) { vector::iterator j = v.at((*m) * k); v.erase(j); } ++m; } primes.clear(); copy(v.being(), v.end(), primes.begin()); } ``````

Last edited on
The set does not let you modify the elements because you could break the order.

Do a desk test (also, make your code compilable)
It's hard to relate the code you supply with the subject of the thread since you definitely do not seem to be implementing a sieve. Is it your intent for v to represent the sieve? If it is, what do you think you're accomplishing by erasing elements?

I would worry more about getting the sieve right than I would about how to fill a set with the sieve results.

[edit: And why don't you move this out of the unix/linux forum to one where it's on topic?]
Last edited on
Sorry for the delay. I got it figured out. Thanks. ;3
Topic archived. No new replies allowed.