Compile-time sieve of Eratosthenes

Question

There are many instances of prime number sieve implementation both here and other places on the web, but I wanted something a little different. In particular, I wanted to create a static array of the first 1024 prime numbers at compile time as a simple reusable structure. I also wanted to allow for relatively simple creation of larger or smaller arrays.

I combined the code from this question with a little bit of macro magic from this other question to come up with code that meets my goal.

Questions:

I'd like to be able to use something more elegant than the stack of macros (templates perhaps), and would prefer to have the result be something more like an STL container than a raw array. Comments on how to do those things, or comments generally to clean up the code would be welcome.

primeconsttest.cpp

#include "primeconst.h"    
#include <vector>
#include <iterator>
#include <iostream>

int main() {
    std::vector<int> prime{std::begin(primes), std::end(primes)};
    for (unsigned i=0; i < prime.size(); ++i)
        std::cout << i << '\t' << prime[i] << '\n';
}

primeconst.h

extern const int primes[1024];

primeconst.cpp

constexpr bool isPrimeLoop(int i, int k) {
    return (k*k > i)?true:(i%k == 0)?false:isPrimeLoop(i, k + 1);
}

constexpr bool isPrime(int i) {
    return isPrimeLoop(i, 2);
}

constexpr int nextPrime(int k) {
    return isPrime(k)?k:nextPrime(k + 1);
}

constexpr int getPrimeLoop(int i, int k) {
    return (i == 0)?k:
        (i % 2)?getPrimeLoop(i-1, nextPrime(k + 1)):
        getPrimeLoop(i/2, getPrimeLoop(i/2, k));
}

constexpr int getPrime(int i) {
    return getPrimeLoop(i, 2);
}

static_assert(getPrime(511) == 3671, "computed incorrectly");

#define K(x) J(x) J(x + 512)
#define J(x) I(x) I(x + 256)
#define I(x) H(x) H(x + 128)
#define H(x) G(x) G(x +  64)
#define G(x) F(x) F(x +  32)
#define F(x) E(x) E(x +  16)
#define E(x) D(x) D(x +   8)
#define D(x) C(x) C(x +   4)
#define C(x) B(x) B(x +   2)
#define B(x) A(x) A(x +   1)
#define A(x) getPrime(x) ,

extern constexpr int primes[] = { K(0) };

Output

0   2
1   3
2   5
3   7
4   11
5   13
6   17

...

1017    8093
1018    8101
1019    8111
1020    8117
1021    8123
1022    8147
1023    8161

Answer 1

I believe I can help with these things:

• Obliterate macros
• Obliterate raw arrays

Macros can be replaced with std::integer_sequence (C++14), and raw arrays can be replaced with std::array (C++11).

#include <array>
#include <utility>

template <typename T, T... Is>
constexpr auto gen_primes_helper(std::integer_sequence<T, Is...>) {
    return std::array<T, sizeof...(Is)>{{getPrime(Is)...}};
}

// T: integer type
// N: number of elements
// return: std::array<T,N>
template <typename T, T N>
constexpr auto gen_primes() {
    return gen_primes_helper(std::make_integer_sequence<T,N>());
}

constexpr auto primes = gen_primes<int,1024>();

However, we have a problem: Compilers currently implement std::make_integer_sequence in O(N) complexity.

GCC limits N to 900, unless you add the -ftemplate-depth= compiler option. See this bug.

Clang limits N to a pathetic 256, but also provides the same -ftemplate-depth= option.

To solve the problem, std::make_integer_sequence can be implemented in O(log(N)). I have done this as follows:

#include <array>
#include <utility>

namespace logseq {

// alias for std::integer_sequence, for brevity
template <typename T, T... Is>
using intseq_t = std::integer_sequence<T, Is...>;

template <typename A, typename B>
struct concat;

// A: intseq_t
// B: intseq_t
// return: typename intseq_t
//
// Example:
//   concat_t< intseq_t<int,0,1,2>, intseq_t<int,0,1,2,3> >
//     => intseq_t<int,0,1,2,3,4,5,6>
template <typename A, typename B>
using concat_t = typename concat<A,B>::type;

template <typename T, T... As, T... Bs>
struct concat<intseq_t<T, As...>, intseq_t<T, Bs...>> {
    using type = intseq_t<T, As..., (sizeof...(As) + Bs)...>;
};

template <typename T, T N, typename = void>
struct logseq;

// T: integer type
// N: number of elements
// return: typename std::make_integer_sequence<T,N>
// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66059
template <typename T, T N>
using logseq_t = typename logseq<T,N>::type;

template <typename T, T N, typename>
struct logseq {
    using type = concat_t<logseq_t<T,N/2>,logseq_t<T,N-N/2>>;
};

template <typename T, T N>
struct logseq<T,N,typename std::enable_if<N==0>::type> {
    using type = intseq_t<T>;
};

template <typename T, T N>
struct logseq<T,N,typename std::enable_if<N==1>::type> {
    using type = intseq_t<int,0>;
};

} // namespace logseq


template <typename T, T... Is>
constexpr auto gen_primes_helper(std::integer_sequence<T, Is...>) {
    return std::array<T, sizeof...(Is)>{{getPrime(Is)...}};
}

// T: integer type
// N: number of elements
// return: std::array<T,N>
template <typename T, T N>
constexpr auto gen_primes() {
    using logseq::logseq_t;
    return gen_primes_helper(logseq_t<T,N>());
}

constexpr auto primes = gen_primes<int,1024>();

Namespace logseq provides a metafunction logseq_t that returns a typename std::integer_sequence<T, 0, /* ... */, N-1>. It is a drop-in replacement for std::make_integer_sequence, which returns the same type.

logseq_t allows for infinite (read: really freaking big) values of N.