35 lines
568 B
C++
35 lines
568 B
C++
#include <array>
|
|
#include <array>
|
|
#include <cmath>
|
|
|
|
using namespace std;
|
|
|
|
template <typename U, typename F>
|
|
constexpr size_t c_div(U a, F b)
|
|
{
|
|
return static_cast<U>(a / b + 0.5);
|
|
};
|
|
|
|
template <size_t N>
|
|
class Primes
|
|
{
|
|
public:
|
|
constexpr Primes()
|
|
{
|
|
for (size_t i = 0; i < N; i++)
|
|
b[i] = 1;
|
|
|
|
for (size_t i = 2; i <= N; i++)
|
|
if (b[i-1])
|
|
for (size_t j = 2 * i; j <= N; j += i)
|
|
b[j-1] = 0;
|
|
|
|
for (size_t i = 1; i < N; i++)
|
|
if (b[i])
|
|
arr[n++] = i+1;
|
|
};
|
|
|
|
size_t n;
|
|
array<bool, N> b;
|
|
array<size_t, N> arr;
|
|
}; |