#include <iostream>
#include <deque>
template<typename T>
bool is_odd(T value)
{
return value & 1;
}
std::deque<std::size_t> atkin(std::size_t max)
{
std::deque<std::size_t> result{ 2, 3, 5 };
std::deque<bool> sieve(max, false);
for (std::size_t n{ 7 }; n < sieve.size(); ++n) {
auto rem{ n % 60 };
if (!is_odd(rem))
continue;
if (rem == 1 || rem == 13 || rem == 17 || rem == 29 || rem == 37 || rem == 41 || rem == 49 || rem == 53) {
// 4x² + y² = n
for (std::size_t y{ 0 }; y < n; ++y)
for (std::size_t x{ 0 }; x < n; ++x)
if (4 * (x * x) + y * y == n)
sieve[n] = !sieve[n];
}
else if (rem == 7 || rem == 19 || rem == 31 || rem == 43) {
// 3x² + y² = n
for (std::size_t y{ 0 }; y < n; ++y)
for (std::size_t x{ 0 }; x < n; ++x)
if (3 * (x * x) + y * y == n)
sieve[n] = !sieve[n];
}
else if (rem == 11 || rem == 23 || rem == 47 || rem == 59) {
// 3x² − y² = n | x > y
for (std::size_t y{ 0 }; y < n; ++y)
for (std::size_t x{ y + 1 }; x < n; ++x)
if (3 * (x * x) - y * y == n)
sieve[n] = !sieve[n];
}
}
for (std::size_t n{}; n < sieve.size(); ++n) {
if (!sieve[n])
continue;
result.push_back(n);
for (auto not_prime{ n * n }; not_prime <= max; not_prime += n)
sieve[not_prime] = false;
}
return result;
}
int main(){
std::cout << std::unitbuf;
for(auto x : atkin(10000))
std::cout << x << ' ';
}