#include <set>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <iterator>
using namespace std;
void GetPrimesByQuadraticForms(vector<bool> &sieveAtkina)
{
int sqrtUpperBound = int(sqrt(sieveAtkina.size() - 1));
for (int x = 1; x <= sqrtUpperBound; x++)
{
for (int y = 1; y <= sqrtUpperBound; y++)
{
int result;
result = ((4 * x * x) + (y * y));
if (result <= sieveAtkina.size() - 1 && (result % 12 == 1 || result % 12 == 5))
{
sieveAtkina[result] = !sieveAtkina[result];
}
result = (3 * x * x) + (y * y);
if (result <= sieveAtkina.size() - 1 && (result % 12 == 7))
{
sieveAtkina[result] = !sieveAtkina[result];
}
if (x > y)
{
result = ((3 * x * x) - (y * y));
if (result <= sieveAtkina.size() - 1 && result % 12 == 11)
{
sieveAtkina[result] = !sieveAtkina[result];
}
}
}
}
}
void DeleteSquaresNumbers(vector<bool> &sieveAtkina)
{
for (int j = 5; j < sqrt(sieveAtkina.size() - 1); j++)
{
if (sieveAtkina[j])
{
int n = j * j;
for (int i = n; i <= sieveAtkina.size() - 1; i += n)
{
sieveAtkina[i] = false;
}
}
}
}
vector<bool> SearchPrimeNumbers(int upperBound)
{
vector<bool> sieveAtkina(upperBound + 1, false);
for (int i = 2; i <= upperBound && i <= 3; i++)
{
sieveAtkina[i] = true;
}
GetPrimesByQuadraticForms(sieveAtkina);
DeleteSquaresNumbers(sieveAtkina);
return sieveAtkina;
}
set<int> GeneratePrimeNumbersSet(int upperBound)
{
set<int> PrimeNumbers;
vector<bool> sieve = SearchPrimeNumbers(upperBound);
for (int i = 1; i <= upperBound; i++)
{
if(sieve[i])
{
PrimeNumbers.insert(i);
}
}
return PrimeNumbers;
}
int main()
{
auto x = GeneratePrimeNumbersSet(25);
copy(x.begin(), x.end(), ostream_iterator<int>(cout, " "));
return 0;
}