Sieve of Eratosthenes: Difference between revisions

← Older edit Newer edit →

Content deleted Content added

Inline

@@ Line 2,778: / Line 2,778: @@
 <syntaxhighlight lang="cpp">#include <iostream>
+#include <iterator>
 #include <algorithm>
 #include <vector>
+// Fills the range [start, end) with 1 if the integer corresponding to the index is composite and 0 otherwise.
-// requires Iterator satisfies RandomAccessIterator
+// requires: I is RandomAccessIterator
-template <typename Iterator>
+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);
-    // mark composites with 1
-    for (Iterator prime_it = start + 1; prime_it != end; ++prime_it)
+    for (auto it = start + 1; it != end; ++it)
     {
-        if (*prime_it == 1) continue;
+        if (*it == 0)
-        // determine the prime number represented by this iterator location
-        size_t stride = (prime_it - start) + 1;
-        // mark all multiples of this prime number up to max
-        Iterator mark_it = prime_it;
-        while ((end - mark_it) > stride)
         {
-            std::advance(mark_it, stride);
+            auto prime = std::distance(start, it) + 1;
-            *mark_it = 1;
+            // mark all multiples of this prime number as composite.
+            while (std::distance(it, end) > prime)
+            {
+                std::advance(it, prime);
+                *it = 1;
+            }
         }
     }
+}
-    // 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).
-    for (Iterator it = start + 1; it != end; ++it)
+// 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);
+    for (auto it = start + 1; it != end; ++it)
     {
         if (*it == 0)
         {
-            *out_it = (it - start) + 1;
+            *out = std::distance(start, it) + 1;
-            ++out_it;
+            ++out;
         }
     }
-    return out_it - start;
+    return out;
 }
-int main(int argc, const char* argv[])
+int main()
 {
-    std::vector<int> primes(100);
+    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
-    for (size_t i = 0; i < count; ++i)
+    // Alternative to store in a vector:
-        std::cout << primes[i] << " ";
+    // std::vector<int> primes;
+    // sieve_primes(is_composite.begin(), is_composite.end(), std::back_inserter(primes));
-    std::cout << std::endl;
+}
-    return 1;
-}</syntaxhighlight>
+</syntaxhighlight>
 === Boost ===