Primality Test

pseudocode

function is_prime(n : integer)
    if n ≤ 1
        return false
    else if n ≤ 3
        return true
    else if n mod 2 = 0 or n mod 3 = 0
        return false
    let i ← 5
    while i×i ≤ n
        if n mod i = 0 or n mod (i + 2) = 0
            return false
        i ← i + 6
    return true

take_1.cpp

#include<boost/hana.hpp>
#include "test.hpp"

namespace hana = boost::hana;

constexpr auto if_ = hana::if_;
template<int c>
constexpr auto int_c = hana::int_c<c>;
template<bool c>
constexpr auto bool_c = hana::bool_c<c>;

auto primality_test = [](auto n)
{
  return
    if_(n <= int_c<1>, hana::nothing,
      if_(n <= int_c<3>, hana::just(n),
        if_(n % int_c<2> == int_c<0> || n % int_c<3> == int_c<0>, hana::nothing,
          if_(hana::is_just(hana::while_(
            [&](auto just_i) {
              return hana::maybe(bool_c<false>,
                [&](auto i) {
                  return bool_c<i * i <= n>;
                }, just_i);
            },
            hana::just(int_c<5>),
            [&](auto just_i) {
              return hana::maybe(hana::nothing,
                [&](auto i) {
                  return if_(n % i == int_c<0> || n % (i + int_c<2>) == int_c<0>, hana::nothing,
                    hana::just(i + int_c<6>));
                }, just_i);
            })), hana::just(n), hana::nothing)))); //practically lisp!
};

int main()
{
  /*
  static_assert(decltype(primality_test(int_c<1009>)){} == hana::just(int_c<1009>), "");
  static_assert(decltype(primality_test(int_c<1010>)){} == hana::nothing, "");
  */
  test_(primality_test);
}

take_2.cpp

#include<boost/hana.hpp>
#include "test.hpp"

namespace hana = boost::hana;

constexpr auto if_ = hana::if_;
template<int c>
constexpr auto int_c = hana::int_c<c>;
template<bool c>
constexpr auto bool_c = hana::bool_c<c>;

auto primality_test = [](auto n)
{
  auto tests = hana::make_tuple(
    hana::make_pair(n <= int_c<1>,
      bool_c<false>),
    hana::make_pair(n <= int_c<3>,
      bool_c<true>),
    hana::make_pair(n % int_c<2> == int_c<0> || n % int_c<3> == int_c<0>,
      bool_c<false>),
    hana::make_pair(hana::is_just(hana::while_(
      [&](auto just_i) {
        return hana::maybe(bool_c<false>,
          [&](auto i) {
            return bool_c<i * i <= n>;
          }, just_i);
      },
      hana::just(int_c<5>),
      [&](auto just_i) {
        return hana::maybe(hana::nothing,
          [&](auto i) {
            return if_(n % i == int_c<0> || n % (i + int_c<2>) == int_c<0>, hana::nothing,
              hana::just(i + int_c<6>));
          }, just_i);
      })), bool_c<true>),
    hana::make_pair(bool_c<true>, bool_c<false>));
  auto results = hana::unpack(tests,
    [](auto... x) {
      return hana::make_tuple(if_(hana::first(x), hana::just(hana::second(x)), hana::nothing)...); 
    });
  return if_(**hana::find_if(results, hana::is_just), hana::just(n), hana::nothing);
};

int main()
{
  //static_assert(decltype(primality_test(int_c<1009>)){} == hana::just(int_c<1009>), "");
  //static_assert(decltype(primality_test(int_c<1010>)){} == hana::nothing, "");
  //static_assert(decltype(primality_test(int_c<25>)){} == hana::nothing, "");
  test_(primality_test);
}

test.hpp

#ifndef PRIME_TEST_TEST_HPP
#define PRIME_TEST_TEST_HPP

#include<boost/hana.hpp>

namespace hana = boost::hana;

auto primes = hana::tuple_c<int, 
    2,  3,  5,  7, 11, 13, 17, 19, 23, 29,
   31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
   73, 79, 83, 89, 97,101,103,107,109,113,
  127,131,137,139,149,151,157,163,167,173,
  179,181,191,193,197,199,211,223,227,229,
  233,239,241,251,257,263,269,271,277,281,
  283,293,307,311,313,317,331,337,347,349,
  353,359,367,373,379,383,389,397,401,409,
  419,421,431,433,439,443,449,457,461,463,
  467,479,487,491,499>;

template<typename F>
void test_(F f)
{
  hana::for_each(hana::make_range(hana::int_c<0>, hana::int_c<94>), //length - 1
    [&](auto i) {
      static_assert(decltype(f(primes[i])){} == hana::just(primes[i]), "");
      hana::for_each(hana::make_range(primes[i] + hana::int_c<1>, primes[i + hana::int_c<1>]),
        [&](auto j) {
          static_assert(decltype(f(j)){} == hana::nothing, "");
        });
    });
}

#endif