List of prime factors at compile-time: specialization error

Question

Consider the following code (link to IDEONE):

#include <iostream>
#include <type_traits>

// List of factors
template<std::intmax_t ... Misc> 
struct factors { };

// Declaration
template<std::intmax_t ... Misc> 
struct factorization;

// Initial specialization
template<std::intmax_t Value> 
struct factorization<Value>
{
    typedef typename std::conditional<Value % 2 == 0,
            typename factorization<Value / 2, 2, 2>::type,
            typename factorization<Value / 2, 2 + 1>::type>::type type;
};

// Initial specialization when the value is not divisible by 2
template<std::intmax_t Value, std::intmax_t Divisor> 
struct factorization<Value, Divisor>
{
    typedef typename std::conditional<Value % Divisor == 0,
            typename factorization<Value / Divisor, Divisor, Divisor>::type,
            typename factorization<Value / Divisor, Divisor + 1>::type>::type type;
};

// Specialization after the first recusion step
template<std::intmax_t Value, std::intmax_t Divisor, std::intmax_t Prime> 
struct factorization<Value, Divisor, Prime>
{
    typedef typename std::conditional<Value % Divisor == 0,
            typename factorization<Value / Divisor, Divisor, Divisor>::type,
            typename factorization<Value / Divisor, Divisor + 1>::type>::type type;
};

// Recursion specialization
template<std::intmax_t Value, std::intmax_t Divisor, std::intmax_t Prime, std::intmax_t ... Primes> 
struct factorization<Value, Divisor, Prime, Primes...>
{
    typedef typename std::conditional<Value % Divisor == 0 && Divisor != Prime,
            typename factorization<Value / Divisor, Divisor, Divisor, Prime,
                    Primes...>::type,
            typename factorization<
                    Value % Divisor == 0 ? Value / Divisor : Value,
                    Divisor + (Value % Divisor != 0), Prime, Primes...>::type>::type type;
};

// Last recursion step
template<std::intmax_t Value, std::intmax_t ... Primes> 
struct factorization<Value, Value, Primes...>
{
    typedef typename factorization<1, Value, Value, Primes...>::type type;
};

// Finalize
template<std::intmax_t Divisor, std::intmax_t ... Primes> 
struct factorization<1, Divisor, Primes...>
{
    typedef factors<Primes...> type;
};

// Main
int main() {
    typename factorization<18>::type x;
    return 0;
}

This code should list the prime factors of a number without repetition: for example, factorization<18>::type should be equal to factors<2, 3>

But it fails with the following error:

prog.cpp: In instantiation of ‘struct factorization<4ll, 2ll, 2ll>’:
prog.cpp:36:79:   required from ‘struct factorization<9ll, 2ll, 2ll>’
prog.cpp:18:67:   required from ‘struct factorization<18ll>’
prog.cpp:67:28:   required from here
prog.cpp:36:79: error: ambiguous class template instantiation for ‘struct factorization<2ll, 2ll, 2ll>’
             typename factorization<Value / Divisor, Divisor + 1>::type>::type type;
                                                                               ^
prog.cpp:32:8: error: candidates are: struct factorization<Value, Divisor, Prime>
 struct factorization<Value, Divisor, Prime>
        ^
prog.cpp:41:8: error:                 struct factorization<Value, Divisor, Prime, Primes ...>
 struct factorization<Value, Divisor, Prime, Primes...>
        ^
prog.cpp:53:8: error:                 struct factorization<Value, Value, Primes ...>
 struct factorization<Value, Value, Primes...>
        ^
prog.cpp:36:79: error: invalid use of incomplete type ‘struct factorization<2ll, 2ll, 2ll>’
             typename factorization<Value / Divisor, Divisor + 1>::type>::type type;
                                                                               ^
prog.cpp:10:8: error: declaration of ‘struct factorization<2ll, 2ll, 2ll>’
 struct factorization;
        ^
prog.cpp: In function ‘int main()’:
prog.cpp:67:30: error: invalid combination of multiple type-specifiers
  typename factorization<18>::type x;
                              ^
prog.cpp:67:36: error: invalid type in declaration before ‘;’ token
  typename factorization<18>::type x;
                                    ^
prog.cpp:67:35: warning: unused variable ‘x’ [-Wunused-variable]
  typename factorization<18>::type x;
                                   ^

Compilation error   time: 0 memory: 0 signal:0

prog.cpp: In function ‘int main()’:
prog.cpp:67:30: error: ‘type’ in ‘struct factorization<18ll>’ does not name a type
  typename factorization<18>::type x;
                              ^
prog.cpp:67:36: error: invalid type in declaration before ‘;’ token
  typename factorization<18>::type x;
                                    ^
prog.cpp:67:35: warning: unused variable ‘x’ [-Wunused-variable]
  typename factorization<18>::type x;
                                   ^

How to solve this problem ?

Answer 1

There is no specialization (as far as I can tell) that matches factorization<18>, unless you're omitting some code. Every one of your specializations seems to assume at least two parameters are being passed into factorization.

From the comments you've added, it seems you're assuming that the specialization labelled "initial specialization" will catch the case where you just pass in a single number. This isn't true. Try running factorization<18, 2> to see that in action. If this is indeed what you want, then either omit the 2 in your specialization and keep the body the same, or add one final specialization that simply matches on a single number and sets type to typename factorization<N, 2>::type.

Answer 2

Here is a working version. Note that using std::conditional is a bad idea, because both branches still have to be expanded. Specialization works much better.

// List of factors
template<std::intmax_t...> 
struct factors { };

// Declaration
template<bool no_remainder, std::intmax_t Value, std::intmax_t Divisor, std::intmax_t ... Primes> 
struct factorization_remove_repeated;
template<bool no_remainder, std::intmax_t Value, std::intmax_t Divisor, std::intmax_t ... Primes> 
struct factorization_check;

// wraps the remainder check to reduce code duplication
template<template<bool, std::intmax_t ...> class T, std::intmax_t Value, std::intmax_t Divisor, std::intmax_t ...Primes> 
struct factorization_advance
{
    typedef typename T<(Value % Divisor) == 0, Value, Divisor, Primes...>::type type;
};

// end case
template<template<bool, std::intmax_t ...> class T, std::intmax_t Divisor, std::intmax_t ... Primes> 
struct factorization_advance<T, 1, Divisor, Primes...>
{
    typedef factors<Primes...> type;
};

// No more repeats of Divisor, move to Divisor+1
template<std::intmax_t Value, std::intmax_t Divisor, std::intmax_t ... Primes> 
struct factorization_remove_repeated<false, Value, Divisor, Primes...>
{
    typedef typename factorization_advance<factorization_check, Value, Divisor + 1, Primes...>::type type;
};

// removed a repeat of Divisor, continue doing so, without adding to primes list
template<std::intmax_t Value, std::intmax_t Divisor, std::intmax_t ... Primes>
struct factorization_remove_repeated<true, Value, Divisor, Primes...>
{
    typedef typename factorization_advance<::factorization_remove_repeated, Value / Divisor, Divisor, Primes...>::type type;
};

// found that Divisor isn't a factor, move to Divisor+1
template<std::intmax_t Value, std::intmax_t Divisor, std::intmax_t ... Primes> 
struct factorization_check<false, Value, Divisor, Primes...>
{
    typedef typename factorization_advance<::factorization_check, Value, Divisor + 1, Primes...>::type type;
};

// Found first occurrence of a factor, add to primes list, remove repeats
template<std::intmax_t Value, std::intmax_t Divisor, std::intmax_t ... Primes>
struct factorization_check<true, Value, Divisor, Primes...>
{
    typedef typename factorization_advance<factorization_remove_repeated, Value / Divisor, Divisor, Primes..., Divisor>::type type;
};

// Convenience wrapper
template<std::intmax_t Value> 
struct factorization
{
    typedef typename factorization_advance<factorization_check, Value, 2>::type type;
};

• Demo: http://rextester.com/NPGBU58803

• Earlier version that also works but less maintainable IMO: http://ideone.com/Ia9hnd