# Prime number generator

I have a created small program that prints a sequence of prime numbers. Based on the origin code in here.

How can I improve this code?

#include <iostream>

template <std::size_t p, std::size_t i>
struct Run
{
static const bool mValue = ((p % i) && Run<p, i - 1>::mValue);
};

template <std::size_t p>
struct Run<p, 1>
{
static const bool mValue = true;
};

template <std::size_t i>
struct Prime
{
Prime<i - 1> mPrime;
static const bool mResult = Run<i, i - 1>::mValue;

void print()
{
mPrime.print();

if (mResult)
{
std::cout << "prime number: " << i << '\n';
}
}
};

template<>
struct Prime<1>
{
static const bool mResult = false;

void print()
{
}
};

int main()
{
Prime<30> PrimeNumbers;
PrimeNumbers.print();
}

• A template-based prime number generator? I am not a C++ expert at all, but doesn't that instantiate the template function for each number from 1 to 30? Try to compile this with 300 instead of 30! Dec 3, 2014 at 20:30
• Doesn't this mean you can't use runtime variables as input? Dec 3, 2014 at 21:48
• So if I understand it correctly, the primality check is done at compile time. Dec 3, 2014 at 22:47
• It is a compile time generator, indeed, which means you can only use it with compile time constants. Alternatively, you could do the same thing in C++11 using constexpr, in a much simpler way. Dec 4, 2014 at 3:28

## 1 Answer

How can I improve this code?

The code itself isn't particularly useful. You can print the primes up to N, but what if I wanted to sum all the primes up to N? In this model, you'd have to add a sum() member function to Prime<i> and again to Prime<1>. That doesn't make for a very reusable system. So let's go for something reusable, and in C++11 to boot.

Checking primality

Run isn't a particularly good name for a metafunction that determines if something is prime or not. Furthermore it doesn't even have to be a metafunction, it can be a constexpr function:

constexpr bool is_prime(std::size_t N)
{
if (N < 2) return false;

for (std::size_t i=2; i*i <= N; ++i) {
if (N%i == 0) return false;
}
return true;
}


Check primality for lots of numbers

Your original example wanted all primes under 30. The standard metaprogramming mechanism for getting all numbers under 30 is:

using Nums = std::make_index_sequence<31>; // std::index_sequence<0, 1, 2, ..., 30>;


Although that gives us numbers and metaprogramming is all about types. Anything that isn't a type is usually a real nuisance to deal with, so let's write something to instead give us a list of types:

template <typename T>
struct type_is { using type = T; };

template <typename...>
struct typelist { };

namespace details {
template <std::size_t N, typename = std::make_index_sequence<N>>
struct make_type_index_sequence;

template <std::size_t N, std::size_t... Is>
struct make_type_index_sequence<N, std::index_sequence<Is...>> {
using type = typelist<std::integral_constant<std::size_t, Is>...>;
};
}

template <std::size_t N>
using make_type_index_sequence = typename details::make_type_index_sequence<N>::type;

// typelist<size_t_<0>, size_t_<1>, ..., size_t_<30>>, where size_t_<N> is integral_constant<size_t, N>
using Nums = make_type_index_sequence<31>;


Ok, we have a typelist. Now we just need to filter it down based on a condition. To filter, we need to be able to concatenate:

template <typename... Args>
struct concat;

template <typename... Args>
using concat_t = typename concat<Args...>::type;

template <typename... A1, typename... A2, typename... Args>
struct concat<typelist<A1...>, typelist<A2...>, Args...> {
using type = concat_t<typelist<A1..., A2...>, Args...>;
};

template <typename TL>
struct concat<TL> {
using type = TL;
};


After which filter comes naturally:

template <typename A, typename F>
using filter_one = std::conditional_t<F::template apply<A>::value,
typelist<A>,
typelist<>>;

template <typename TL, typename F>
struct filter;

template <typename... Args, typename F>
struct filter<typelist<Args...>, F> {
using type = concat_t<filter_one<Args, F>...>;
};

template <typename TL, typename F>
using filter_t = typename filter<TL, F>::type;


Metafunction classes

Something needs to be mentioned about this construction:

F::template apply<A>::value


Here F is a "metafunction class". That is, it's a type of the form:

struct MetafunctionClass {
template <typename... Args>
using apply = ???
};


Metaprogramming is all about convention. If everybody doesn't agree on convention, everybody's metaprograms may as well be written in different languages. The most core convention is that the "return" of a metafunction lives in a type named type. But a fairly common one is that when you need a "metafunctor", you pass something like this. The advantage of something like this is that it's always easy to create a type, but usually not so easy to create a template template (which would be the alternative).

Specifically here, we need:

struct IsPrime {
template <typename T>
using apply = std::integral_constant<bool, is_prime(T::value)>;
};


with which getting all the primes under 30 is:

template <size_t N>
using PrimesUnder = filter_t<make_type_index_sequence<N>, IsPrime>;


What can I do with this?

Well, anything really. Now that I made it easy to generate the primes, anything we may want to do with them is easy too. Printing them?

template <typename... Ts, typename F>
void for_each(typelist<Ts...>, F f) {
using expander = int[];
expander{0,
(void(f(type_is<Ts>{})), 0)...
};
}

for_each(PrimesUnder<30>{}, [](auto t) {
std::cout << "prime number: " << decltype(t)::type::value << std::endl;
});


Summing them?

template <typename TL, typename F, typename Z>
using foldl_t = ??? // exercise for the reader

struct Add {
template <typename T, typename U>
using apply = std::integral_constant<decltype(T::value + U::value),
T::value + U::value
>;
};

template <size_t N>
using SumOfPrimesUnder = foldl_t<PrimesUnder<N>, Add, std::integral_constant<int, 0>>;


Anything else you may need to do with your primes? You have the typelist - it's all in your hands.