fork download
copy 
  1. #include <bitset>
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. template <std::size_t N>
  6. struct prime_sieve
  7. {
  8.     prime_sieve() : _sieve()
  9.     {
  10.         _sieve.flip();
  11.  
  12.         for (std::size_t i = 0; i < N; ++i)
  13.         {
  14.             if (_sieve.test(i))
  15.             {
  16.                 auto value = 3 + i * 2;
  17.                 for (std::size_t j = i + value; j < N; j += value)
  18.                     _sieve.reset(j);
  19.             }
  20.         }
  21.     }
  22.  
  23.     std::vector<unsigned long long> get_primes() const
  24.     {
  25.         std::vector<unsigned long long> primes(1, 2);
  26.         for (std::size_t i = 0; i < N; ++i)
  27.             if (_sieve.test(i))
  28.                 primes.push_back(3 + i * 2);
  29.  
  30.         return primes;
  31.     }
  32.  
  33. private:
  34.     std::bitset<N> _sieve;
  35. };
  36.  
  37.  
  38. int main()
  39. {
  40.     const std::size_t bits = 4000;
  41.  
  42.     prime_sieve<bits> sieve;
  43.  
  44.     auto primes = sieve.get_primes();
  45.  
  46.     std::cout << "Found " << primes.size() << " primes using " << bits / 8 << " bytes.\n";
  47.     std::cout << "Last prime found: " << primes.back() << '\n';
  48. }
Success #stdin #stdout 0s 3456KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Found 1007 primes using 500 bytes.
Last prime found: 7993
https://ideone.com/RbUJBk
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!