{{ message }}

Instantly share code, notes, and snippets.

# ricejasonf/pseudocode

Last active Dec 2, 2015
Primality Test
 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
 #include #include "test.hpp" namespace hana = boost::hana; constexpr auto if_ = hana::if_; template constexpr auto int_c = hana::int_c; template constexpr auto bool_c = hana::bool_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, [&](auto i) { return bool_c; }, 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); }
 #include #include "test.hpp" namespace hana = boost::hana; constexpr auto if_ = hana::if_; template constexpr auto int_c = hana::int_c; template constexpr auto bool_c = hana::bool_c; auto primality_test = [](auto n) { auto tests = hana::make_tuple( hana::make_pair(n <= int_c<1>, bool_c), hana::make_pair(n <= int_c<3>, bool_c), hana::make_pair(n % int_c<2> == int_c<0> || n % int_c<3> == int_c<0>, bool_c), hana::make_pair(hana::is_just(hana::while_( [&](auto just_i) { return hana::maybe(bool_c, [&](auto i) { return bool_c; }, 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), hana::make_pair(bool_c, bool_c)); 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); }
 #ifndef PRIME_TEST_TEST_HPP #define PRIME_TEST_TEST_HPP #include namespace hana = boost::hana; auto primes = hana::tuple_c; template 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