A simple, and damn stupid compile-time Sieve of Erathostenes.

CTSieve.cc

// A primitive compile-time Sieve of Erathostenes, (c) Thomas Lang, 2017
#include <iostream>

// First, the usual value-to-type wrapper for usage in type lists.
template<unsigned int V>
struct Value {
    enum { value = V };
};

// And the ususal conditional.
template<bool Condition, typename Then, typename Else>
struct if_ {
    using result = Then;
};

template<typename Then, typename Else>
struct if_<false, Then, Else> {
    using result = Else;
};

// Now the fundamentals for building type lists.
struct NIL {
    using Head = NIL;
    using Tail = NIL;
};

template<typename H, typename T = NIL>
struct List {
    using Head = H;
    using Tail = T;
};

// Check if the list is empty.
template<typename TypeList>
struct isNull {
    enum { result = false };
};

template<>
struct isNull<NIL> {
    enum { result = true };
};

// Erase all elements from TypeList, whose values are divisible by CurrentValue.
template<unsigned int CurrentValue, typename TypeList>
struct EraseModuloValue {
    static const bool isDivisible = (TypeList::Head::value % CurrentValue) == 0;
    using recCall = typename EraseModuloValue<CurrentValue, typename TypeList::Tail>::result;
    using result  = typename if_<isDivisible, recCall, List<typename TypeList::Head, recCall>>::result;
};

template<unsigned int CurrentValue>
struct EraseModuloValue<CurrentValue, NIL> {
    using result = NIL;
};

// Utility for printing a list.
template<typename TypeList>
struct ListPrinter {
    struct Comma   { static const char value = ','; };
    struct NoComma { static const char value = ' '; };

    static void print(void) {
        std::cout << TypeList::Head::value;
        std::cout << if_<isNull<typename TypeList::Tail>::result, NoComma, Comma>::result::value << ' ';
        ListPrinter<typename TypeList::Tail>::print();
    }
};

template<>
struct ListPrinter<NIL> {
    static void print(void) {
        std::cout << std::endl;
    }
};

// Generates a list of all integers from Lower to Limit (both inclusive).
template<unsigned int Lower, unsigned int Limit>
struct AccumulateNumbers {
    using result = List<Value<Lower>, typename AccumulateNumbers<Lower + 1, Limit>::result>;
};

template<unsigned int Limit>
struct AccumulateNumbers<Limit, Limit> {
    using result = List<Value<Limit>, NIL>;
};

// Sieves out the multiples of the head of the list from the tail.
// The recursive call operates on the filtered list, therefore it then removes all multiples of
// the next head element and so on. For the list [2..100], it first removes all multiples of 2
// in the tail list [3..100], then all multiples of 3 in the new tail and so on.
// The final result will only contain the prime numbers.
template<typename TypeList>
struct SieveOut {
    using CurrentValue = typename TypeList::Head;
    using filteredList = typename EraseModuloValue<CurrentValue::value, typename TypeList::Tail>::result;
    using result       = List<CurrentValue, typename SieveOut<filteredList>::result>;
};

template<>
struct SieveOut<NIL> {
    using result = NIL;
};

// Main invocation, generates all prime numbers in the range [Lower..Limit] by
// performing the Sieve of Erathostenes.
template<unsigned int Lower, unsigned int Limit>
struct Sieve {
    using AllNumbersInRange = typename AccumulateNumbers<Lower, Limit>::result;
    using result = typename SieveOut<AllNumbersInRange>::result;
};

int main(int argc, char** argv) {

    static constexpr unsigned int Limit = 100;

    using primesViaSieve = Sieve<2, Limit>::result;

    std::cout << "Prime factors until " << Limit << " using the Sieve of Erathostenes:\n";
    ListPrinter<primesViaSieve>::print();
    
    return 0;
}