templated_primes.cpp

#include <iostream>
#include <typeinfo>

bool is_prime(unsigned n, unsigned i){
	if (i * i >= n)
		return true;
	if (n % i == 0)
		return false;
	return is_prime(n, i + 2);
}

bool is_prime(unsigned n){
	if (n % 2 == 0)
		return false;
	return is_prime(n, 3);
}

template <bool B, typename T, typename F>
struct compile_time_decision{};

template <typename T, typename F>
struct compile_time_decision<true, T, F>{
	typedef T type;
};

template <typename T, typename F>
struct compile_time_decision<false, T, F>{
	typedef F type;
};

template <bool B>
struct compile_type_bool{
	static const bool value = B;
};

template <unsigned N, unsigned I>
struct primality2{
	static const bool value = compile_time_decision<
			(I * I > N),
			compile_type_bool<true>,
			compile_time_decision<
				(N % I == 0),
				compile_type_bool<false>,
				primality2<N, I + 2>
			>::type
		>::type::value;
};

template <unsigned N>
struct primality{
	static const bool value = compile_time_decision<
			(N % 2 == 0),
			compile_type_bool<false>,
			primality2<N, 3>
		>::type::value;
};

template <>
struct primality<1>{
	static const bool value = false;
};

template <>
struct primality<2>{
	static const bool value = true;
};

struct null{};

template <unsigned N>
struct int_node{
	static const unsigned value = N;
};

template <typename Inner, typename Outer>
struct cons{};

template <typename Inner, typename Outer>
cons<Inner, Outer> operator+(const Inner &, const Outer &){
	return cons<Inner, Outer>();
}

template <unsigned N>
struct assemble_list_of_numbers_up_to{
	typedef cons<typename assemble_list_of_numbers_up_to<N - 1>::type, int_node<N> > type;
};

template <>
struct assemble_list_of_numbers_up_to<0>{
	typedef cons<null, int_node<0> > type;
};

template <unsigned N>
struct assemble_list_of_primes_up_to{
	typedef typename compile_time_decision<
			primality<N>::value,
			cons<typename assemble_list_of_primes_up_to<N - 1>::type, int_node<N> >,
			typename assemble_list_of_primes_up_to<N - 1>::type
		>::type type;
};

template <>
struct assemble_list_of_primes_up_to<0>{
	typedef null type;
};

template <typename F>
void traverse(const null &, F &){
}

template <typename Inner, typename Outer, typename F>
void traverse(const cons<Inner, Outer> &, F &f){
	traverse(Inner(), f);
	f(Outer::value);
}

int main(int argc, char **argv){
	traverse(
		assemble_list_of_primes_up_to<100>::type(),
		[](unsigned n){
			std::cout << n << std::endl;
		}
	);
	std::cout << typeid(primality<100>).name() << std::endl;
}