generate compile-time prime table

prime_sequence.cpp

#include <array>
#include <iostream>
#include <type_traits>

#define ENABLER(cond) \
  typename std::enable_if<(cond), std::nullptr_t>::type = nullptr

template <typename T, T... N>
struct IntegerSequence;

template <typename T, class S>
struct IntegerSequenceTraits : std::false_type
{};
template <typename T, T... N>
struct IntegerSequenceTraits<T, IntegerSequence<T, N...> > : std::true_type {
  using type = IntegerSequence<T, N...>;
  using value_type = typename type::value_type;
  using size_type = typename type::size_type;
  static constexpr size_type size() { return type::size(); }
};

template <std::size_t... N>
using IndexSequence = IntegerSequence<std::size_t, N...>;

template <bool... B>
using BoolSequence = IntegerSequence<bool, B...>;

template <std::size_t From, std::size_t To, ENABLER(From <= To)>
struct MakeIndexSequenceHelper {
  template <std::size_t Start, std::size_t Count>
  struct Impl;
  template <std::size_t Start, std::size_t Count>
  struct Impl {
    using Head = typename Impl<Start, (Count / 2)>::type;
    using Tail = typename Impl<(Start + Count / 2), (Count - Count / 2)>::type;
    using type = typename Head::template Join<Tail>::type;
  };
  template <std::size_t Start>
  struct Impl<Start, 1> {
    using type = IndexSequence<Start>;
  };
  template <std::size_t Start>
  struct Impl<Start, 0> {
    using type = IndexSequence<>;
  };
  using type = typename Impl<From, (To - From)>::type;
};
template <std::size_t From, std::size_t To>
using MakeIndexSequence = typename MakeIndexSequenceHelper<From, To>::type;

template <typename T, T N>
struct MakeIntegerSequenceHelper {
  template <class S>
  struct Impl;
  template <std::size_t... I>
  struct Impl<IndexSequence<I...> >
      : IntegerSequence<T, (static_cast<T>(I))...>
  {};
  using type = typename Impl<MakeIndexSequence<0, N> >::type;
};
template <typename T, T N>
using MakeIntegerSequence = typename MakeIntegerSequenceHelper<T, N>::type;

template <class S>
struct AndAll;
template <bool C, bool... B>
struct AndAll<BoolSequence<C, B...> > {
  static constexpr bool value = C && AndAll<BoolSequence<B...> >::value;
};
template <>
struct AndAll<BoolSequence<> > {
  static constexpr bool value = true;
};

template <class S>
struct OrAll;
template <bool C, bool... B>
struct OrAll<BoolSequence<C, B...> > {
  static constexpr bool value = C || OrAll<BoolSequence<B...> >::value;
};
template <>
struct OrAll<BoolSequence<> > {
  static constexpr bool value = false;
};

template <typename T, T... N>
struct IntegerSequence {
  using value_type = T;
  using size_type = std::size_t;
  using type = IntegerSequence;
  static constexpr size_type size() { return sizeof...(N); }
  static constexpr std::array<T, size()> make_array() {
    return std::array<T, size()>{{N...}};
  }
  static constexpr T at(size_type n) { return ((T[size()]){N...})[n]; }
  template <template <T...> class S>
  using Unpack = S<N...>;
  template <typename U, U(f)(T)>
  using Map = IntegerSequence<U, f(N)...>;
  template <typename U, template <T> class F>
  using ValueMap = IntegerSequence<U, F<N>::value...>;
  template <T... M>
  using Append = IntegerSequence<T, N..., M...>;
  template <T... M>
  using Prepend = IntegerSequence<T, M..., N...>;
  template <class S, bool B, ENABLER(B)>
  struct JoinHelper {
    using type = typename S::template Prepend<N...>::type;
  };
  template <class S>
  using Join = typename JoinHelper<S, IntegerSequenceTraits<T, S>::value>::type;
  template <size_type... I>
  using Extract = IntegerSequence<T, at(I)...>;
  template <size_type From, size_type To, ENABLER(From <= To)>
  struct SliceHelper {
    using Sequence = MakeIndexSequence<From, To>;
    using type = typename Sequence::template Unpack<Extract>::type;
  };
  template <size_type From, size_type To>
  using Slice = typename SliceHelper<From, To>::type;
  template <size_type Count>
  struct Divide {
    static constexpr auto count = Count < size() ? Count : size();
    using Head = typename Slice<0, count>::type;
    using Tail = typename Slice<(size() - count), size()>::type;
  };
  template <size_type Count>
  using Head = typename Divide<Count>::Head;
  template <size_type Count>
  using Tail = typename Divide<Count>::Tail;
  template <template <T> class F>
  struct FilterHelper {
    using E = IntegerSequence<T>;
    template <class S>
    struct Impl;
    template <T... M>
    struct Impl<IntegerSequence<T, M...> > {
      using Sequence = IntegerSequence<T, M...>;
      static constexpr auto size = Sequence::size();
      static constexpr auto half = size / 2;
      using Head = typename Sequence::template Head<half>::type;
      using Tail = typename Sequence::template Tail<(size - half)>::type;
      using Left = typename Impl<Head>::type;
      using Right = typename Impl<Tail>::type;
      using type = typename Left::template Join<Right>::type;
    };
    template <T M>
    struct Impl<IntegerSequence<T, M> > {
      using S = IntegerSequence<T, M>;
      using type = typename std::conditional<F<M>::value, S, E>::type;
    };
    using type = typename std::conditional<
      (size() == 0), E, typename Impl<IntegerSequence>::type>::type;
  };
  template <template <T> class F>
  using Filter = typename FilterHelper<F>::type;
};


constexpr bool is_even(int n) {
  return n % 2 == 0;
}

constexpr int square(int n) {
  return n * n;
}

// return a^b mod n
constexpr int mod_pow(int a, int b, int n) {
  return (b == 0 ? 1 :
          is_even(b) ? square(mod_pow(a, b / 2, n)) :
          (a * mod_pow(a, b - 1, n))) % n;
}
constexpr int int_pow(int a, int b) {
  return (b == 0 ? 1 :
          is_even(b) ? square(int_pow(a, b / 2)) :
          (a * int_pow(a, b - 1)));
}

// return (d, s)
// N == d * 2^s and d is odd
template <int N>
struct Factorize {
  using Half = Factorize<(N / 2)>;
  static constexpr int d = is_even(N) ? Half::d : N;
  static constexpr int s = is_even(N) ? (Half::s + 1) : 0;
};
template <>
struct Factorize<1> {
  static constexpr int d = 1;
  static constexpr int s = 0;
};

// if true, n may be prime
// if false, n must be composite
// n == d * 2^s
// a is sample
template <int A, int N>
struct MillerTest {
  template <int D, int S, bool B>
  struct Impl {
    struct Test1 {
      static constexpr bool value = mod_pow(A, D, N) == 1;
    };
    template <int R>
    struct Test2 {
      static constexpr bool value = mod_pow(A, D * int_pow(2, R), N) == N - 1;
    };
    using Sequence = MakeIntegerSequence<int, S>;
    using Conditions = typename Sequence::template ValueMap<bool, Test2>::type;
    static constexpr bool value = Test1::value || OrAll<Conditions>::value;
  };
  template <int D, int S>
  struct Impl<D, S, false> {
    static constexpr bool value = true;
  };
  static constexpr auto D = Factorize<(N - 1)>::d;
  static constexpr auto S = Factorize<(N - 1)>::s;
  static constexpr bool value = Impl<D, S, (A < N)>::value;
};

template <int N>
struct IsPrime {
  struct ImplFalse {
    static constexpr bool A2 = MillerTest<2, N>::value;
    static constexpr bool A7 = MillerTest<7, N>::value;
    static constexpr bool A61 = MillerTest<61, N>::value;
    using Conditions = BoolSequence<A2, A7, A61>;
    static constexpr bool value = AndAll<Conditions>::value;
  };
  struct ImplTrue {
    static constexpr bool value = N < 2 ? false : (N == 2);
  };
  using Impl = typename std::conditional<
    (N < 2 || is_even(N)), ImplTrue, ImplFalse>::type;
  static constexpr bool value = Impl::value;
};

template <typename T, class S>
struct SequenceForEach {
  template <class, std::size_t>
  struct Impl;
  template <T M, T... N, std::size_t I>
  struct Impl<IntegerSequence<T, M, N...>, I> {
    template <typename F>
    static void apply(F f) {
      f(I, M);
      Impl<IntegerSequence<T, N...>, (I + 1)>::apply(f);
    }
  };
  template <std::size_t I>
  struct Impl<IntegerSequence<T>, I> {
    template <typename F>
    static void apply(F) {}
  };
  template <typename F>
  static void apply(F f) {
    Impl<S, 0>::apply(f);
  }
};

template <typename... S>
struct VariadicPrint {
  template <typename... T>
  struct Impl;
  template <typename V, typename U, typename... T>
  struct Impl<V, U, T...> {
    static void print(const V& v, const U& u, const T&... t) {
      std::cout << v << ' ';
      Impl<U, T...>::print(u, t...);
    }
  };
  template <typename T>
  struct Impl<T> {
    static void print(const T& t) {
      std::cout << t << std::endl;
    }
  };
  static void print(const S&... s) {
    Impl<S...>::print(s...);
  }
};

template <typename... T>
void print(const T&... t) {
  VariadicPrint<T...>::print(t...);
}
template <typename T, T... N>
void print(IntegerSequence<T, N...>) {
  const auto print = VariadicPrint<std::size_t, T>::print;
  SequenceForEach<T, IntegerSequence<T, N...> >::apply(print);
}

int main() {
  using Ints = MakeIntegerSequence<int, 10000>;
  using Primes = Ints::template Filter<IsPrime>;
  constexpr auto primes = Primes::make_array();
  for (auto&& p : primes) {
    print(p);
  }
}