Sieve of Eratosthenes: Difference between revisions
Content deleted Content added
Improve C++ style for stdlib version. |
|||
Line 2,778: | Line 2,778: | ||
<syntaxhighlight lang="cpp">#include <iostream> |
<syntaxhighlight lang="cpp">#include <iostream> |
||
#include <iterator> |
|||
#include <algorithm> |
#include <algorithm> |
||
#include <vector> |
#include <vector> |
||
// Fills the range [start, end) with 1 if the integer corresponding to the index is composite and 0 otherwise. |
|||
// requires |
// requires: I is RandomAccessIterator |
||
template |
template<typename I> |
||
size_t prime_sieve(Iterator start, Iterator end) |
|||
void mark_composites(I start, I end) |
|||
{ |
{ |
||
if (start == end) return 0; |
|||
// clear the container with 0 |
|||
std::fill(start, end, 0); |
std::fill(start, end, 0); |
||
// mark composites with 1 |
|||
for ( |
for (auto it = start + 1; it != end; ++it) |
||
{ |
{ |
||
if (* |
if (*it == 0) |
||
// determine the prime number represented by this iterator location |
|||
size_t stride = (prime_it - start) + 1; |
|||
⚫ | |||
Iterator mark_it = prime_it; |
|||
while ((end - mark_it) > stride) |
|||
{ |
{ |
||
std:: |
auto prime = std::distance(start, it) + 1; |
||
⚫ | |||
⚫ | |||
while (std::distance(it, end) > prime) |
|||
{ |
|||
std::advance(it, prime); |
|||
⚫ | |||
} |
|||
} |
} |
||
} |
} |
||
} |
|||
// copy marked primes into container |
|||
Iterator out_it = start; |
|||
// Fills "out" with the prime numbers in the range 2...N where N = distance(start, end). |
|||
⚫ | |||
// requires: I is a RandomAccessIterator |
|||
// O is an OutputIterator |
|||
template <typename I, typename O> |
|||
O sieve_primes(I start, I end, O out) |
|||
{ |
|||
mark_composites(start, end); |
|||
⚫ | |||
{ |
{ |
||
if (*it == 0) |
if (*it == 0) |
||
{ |
{ |
||
* |
*out = std::distance(start, it) + 1; |
||
++ |
++out; |
||
} |
} |
||
} |
} |
||
return |
return out; |
||
} |
} |
||
int main( |
int main() |
||
{ |
{ |
||
std::vector< |
std::vector<uint8_t> is_composite(1000); |
||
sieve_primes(is_composite.begin(), is_composite.end(), std::ostream_iterator<int>(std::cout, " ")); |
|||
size_t count = prime_sieve(primes.begin(), primes.end()); |
|||
// display the primes |
|||
// Alternative to store in a vector: |
|||
// std::vector<int> primes; |
|||
// sieve_primes(is_composite.begin(), is_composite.end(), std::back_inserter(primes)); |
|||
std::cout << std::endl; |
|||
} |
|||
return 1; |
|||
</syntaxhighlight> |
|||
=== Boost === |
=== Boost === |