A simple compile time functionality for calculating the prime factorization of a number.

compileTimePrimeFactorization.cc

// Compile time prime factorization.
// (C) Thomas Lang, Aug 6th, 2017

#include <iostream>

// First, we create a basic list structure in a functional style:
struct NIL {
    using Head = NIL;
    using Tail = NIL;
};

// data List a = NIL | Cons a (List a)
template<typename H, typename T = NIL>
struct List {
    using Head = H;
    using Tail = T;
};

// Now some utility functions on such lists.

// isNull :: [a] -> Bool
// isNull NIL = True
// isNull _   = False
template<typename List>
struct isNull {
    enum { result = false };
};

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

// appendList :: [a] -> [a] -> [a]
// appendList []     ys = ys
// appendList (x:xs) ys = x : appendList xs ys
template<class List1, class List2>
struct appendList {
    using result = List<typename List1::Head, typename appendList<typename List1::Tail, List2>::result>;
};

template<class List2>
struct appendList<NIL, List2> {
    using result = List2;
};


// Now a utility compile-time 'if'.
template<bool C, typename T, typename E>
struct if_ {
    using result = T;
};

template<typename T, typename E>
struct if_<false, T, E> {
    using result = E;
};

template<int X>
struct Value {
    enum { value = X };
};


// And we need a printer for displaying such lists.
template<typename List>
struct ListPrinter {
   struct Comma   { static const char value = ','; };
   struct NoComma { static const char value = ' '; };

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

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


// Now do mathematic stuff.
// (1) Check if a number is prime.
template<int p, int i>
struct PrimeCheck {
    static const bool ok = (p%i) != 0 && PrimeCheck<p, i-1>::ok;
};
template<int p>
struct PrimeCheck<p, 1> {
    static const bool ok = true;
};

template<int p>
struct IsPrime {
    static const bool result = PrimeCheck<p, p-1>::ok;
};


// (2) Get the next prime number higher than 'P' but smaller-or-equal to 'Limit'.
template<int P, int Limit, bool smallerThanLimit = (P+1 <= Limit) >
struct getNextPrime {
    enum { result =
            if_< IsPrime<P+1>::result,
                 Value<P+1>,
                 Value<getNextPrime<P+1, Limit>::result>
               >::result::value
    };
};

template<int P, int Limit>
struct getNextPrime<P, Limit, false> {
    enum { result = 1 };
};


// (3) Get a list of 'Prime's that can be factorized.
//     Example: GetPrimeAccNumbers<2, 360, NIL> => [2,2,2].
template<int Prime, int X, class Acc, bool div = X % Prime == 0 >
struct GetPrimeAccNumbers {
    using prfaclst = typename GetPrimeAccNumbers<Prime, X/Prime, List<Value<Prime>, Acc> >::prfaclst;
};
template<int Prime, int X, class Acc>
struct GetPrimeAccNumbers<Prime, X, Acc, false> {
    using prfaclst = Acc;
};


// (4) Compute the maximum factor of factorized prime numbers, for the above
//     example this would be for [2,2,2] the factor 2*2*2 = 8.
template<class List>
struct getFactor {
    enum { value = List::Head::value * getFactor<typename List::Tail>::value };
};
template<>
struct getFactor<NIL> {
    enum { value = 1 };
};

// (5) Do recursive factorization of prime number lists.
template<int Prime, int X>
struct PrimeFactorsHelper {
    using prime_list = typename GetPrimeAccNumbers<Prime, X, NIL>::prfaclst;

    enum { newX = X / getFactor<prime_list>::value,
           nextPrime = getNextPrime<Prime, newX>::result
    };
    
    using recursion  = typename PrimeFactorsHelper<nextPrime, newX>::result;
    using result = typename appendList<prime_list, recursion>::result;
};

template<int Prime>
struct PrimeFactorsHelper<Prime, Prime> {
    using result = List<Value<Prime>, NIL>;
};



// (6) Main entry point, starts with the lowest prime number (i.e. 2).
template<int X>
struct PrimeFactors {
    using result = typename PrimeFactorsHelper<2, X>::result;
};


int main(void) {

    using factors = PrimeFactors<360>::result;
    std::cout << "Prime factors of 360:" << std::endl;
    std::cout << "Expected: 2, 2, 2, 3, 3, 5" << std::endl;
    std::cout << "Got:      ";
    ListPrinter<factors>::print();
    std::cout << std::endl;

    using factors2 = PrimeFactors<380>::result;
    std::cout << "Prime factors of 380:" << std::endl;
    std::cout << "Expected: 2, 2, 5, 19" << std::endl;
    std::cout << "Got:      ";
    ListPrinter<factors2>::print();
    std::cout << std::endl;
    return 0;
}