Skip to content

Instantly share code, notes, and snippets.

@ricejasonf

ricejasonf/pseudocode

Last active Dec 2, 2015
Embed
What would you like to do?
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<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);
}
#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);
}
#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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.