fork download
  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
stdin
Standard input is empty
stdout
Found 1007 primes using 500 bytes.
Last prime found: 7993