Prime number generator

Question

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();
}

• Martin R: 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!
• raptortech97: Doesn't this mean you can't use runtime variables as input?
• Martin R: So if I understand it correctly, the primality check is done at compile time.
• glampert: 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.

Answer 1

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.