fork download
copy 
  1. #include <iostream>
  2. #include <deque>
  3.  
  4. template<typename T>
  5. bool is_odd(T value)
  6. {
  7.     return value & 1;
  8. }
  9.  
  10. std::deque<std::size_t> atkin(std::size_t max)
  11. {
  12.     std::deque<std::size_t> result{ 2, 3, 5 };
  13.     std::deque<bool> sieve(max, false);
  14.  
  15.     for (std::size_t n{ 7 }; n < sieve.size(); ++n) {
  16.         auto rem{ n % 60 };
  17.         if (!is_odd(rem))
  18.             continue;
  19.  
  20.         if (rem == 1 || rem == 13 || rem == 17 || rem == 29 || rem == 37 || rem == 41 || rem == 49 || rem == 53) {
  21.             // 4x² + y² = n
  22.             for (std::size_t y{ 0 }; y < n; ++y)
  23.                 for (std::size_t x{ 0 }; x < n; ++x)
  24.                     if (4 * (x * x) + y * y == n)
  25.                         sieve[n] = !sieve[n];
  26.         }
  27.         else if (rem == 7 || rem == 19 || rem == 31 || rem == 43) {
  28.             // 3x² + y² = n
  29.             for (std::size_t y{ 0 }; y < n; ++y)
  30.                 for (std::size_t x{ 0 }; x < n; ++x)
  31.                     if (3 * (x * x) + y * y == n)
  32.                         sieve[n] = !sieve[n];
  33.         }
  34.         else if (rem == 11 || rem == 23 || rem == 47 || rem == 59) {
  35.             // 3x² − y² = n | x > y
  36.             for (std::size_t y{ 0 }; y < n; ++y)
  37.                 for (std::size_t x{ y + 1 }; x < n; ++x)
  38.                     if (3 * (x * x) - y * y == n)
  39.                         sieve[n] = !sieve[n];
  40.         }
  41.     }
  42.  
  43.     for (std::size_t n{}; n < sieve.size(); ++n) {
  44.         if (!sieve[n])
  45.             continue;
  46.  
  47.         result.push_back(n);
  48.  
  49.         for (auto not_prime{ n * n }; not_prime <= max; not_prime += n)
  50.             sieve[not_prime] = false;
  51.     }
  52.  
  53.     return result;
  54. }
  55.  
  56.  
  57.  
  58. int main(){
  59. 	std::cout << std::unitbuf;
  60.  
  61.     for(auto x : atkin(10000))
  62.         std::cout << x << ' ';
  63. }
  64.  
Time limit exceeded #stdin #stdout 5s 4316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/KHgaBO
language:
C++ 4.3.2 (gcc-4.3.2)
created:
5 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!