Compile time prime checking

c++, c++11, compile-time, template-meta-programming, templates

Solution

You can change the space requirement from linear to logarithmic by splitting the range by halves using a divide-and-conquer algorithm. This method uses divide-and-conquer, and only tests odd factors (Live at Coliru):

namespace detail {
using std::size_t;

constexpr size_t mid(size_t low, size_t high) {
  return (low + high) / 2;
}

// precondition: low*low <= n, high*high > n.
constexpr size_t ceilsqrt(size_t n, size_t low, size_t high) {
  return low + 1 >= high
    ? high
    : (mid(low, high) * mid(low, high) == n)
      ? mid(low, high)
      : (mid(low, high) * mid(low, high) <  n)
        ? ceilsqrt(n, mid(low, high), high)
        : ceilsqrt(n, low, mid(low, high));
}

// returns ceiling(sqrt(n))
constexpr size_t ceilsqrt(size_t n) {
  return n < 3
    ? n
    : ceilsqrt(n, 1, size_t(1) << (std::numeric_limits<size_t>::digits / 2));
}


// returns true if n is divisible by an odd integer in
// [2 * low + 1, 2 * high + 1).
constexpr bool find_factor(size_t n, size_t low, size_t high)
{
  return low + 1 >= high
    ? (n % (2 * low + 1)) == 0
    : (find_factor(n, low, mid(low, high))
       || find_factor(n, mid(low, high), high));
}
}

constexpr bool is_prime(std::size_t n)
{
  using detail::find_factor;
  using detail::ceilsqrt;

  return n > 1
    && (n == 2
        || (n % 2 == 1
            && (n == 3
                || !find_factor(n, 1, (ceilsqrt(n) + 1) / 2))));
}

EDIT: Use compile-time sqrt to bound search space to ceiling(sqrt(n)), instead of n / 2. Now can compute `is_prime(100000007)` as desired (and `is_prime(1000000000039ULL)` for that matter) on Coliru without exploding.

Apologies for the horrible formatting, I still haven't found a comfortable style for C++11's tortured `constexpr` sub-language.

EDIT: Cleanup code: replace macro with another function, move implementation detail into a detail namespace, steal indentation style from Pablo's answer.

Problem

Original source