Templated primality test in C++

prime.cpp

#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>

const int DEPTH = 7;
// Reasonable values are 3,5,7. However the 7 version takes a very long time to compile (a few minutes).
// Use g++ -O3 prime.cpp if possible.

using namespace std;

/** These functions should be always inlined **/
template <unsigned int OFFSET, unsigned int N> inline bool not_dividable_by_offset_or_smaller (unsigned long long base, unsigned long long x) __attribute__((always_inline));
template <> inline bool not_dividable_by_offset_or_smaller<1, 1> (unsigned long long base, unsigned long long x) __attribute__((always_inline));

template <unsigned int N, unsigned int M> struct not_dividable_by_smaller_or_equal
{
    enum { value = not_dividable_by_smaller_or_equal<N, M-1>::value && (N % M) };
};

template <unsigned int N> struct not_dividable_by_smaller_or_equal<N, 2>
{
    enum { value = N % 2 };
};

template <unsigned int N> struct is_prime
{
    enum { value = not_dividable_by_smaller_or_equal<N, N-1>::value };
};

template <> struct is_prime<0>
{
    enum { value = 0 };
};

template <> struct is_prime<1>
{
    enum { value = 0 };
};

template <> struct is_prime<2>
{
    enum { value = 1 };
};

template <unsigned int N> struct prime_fact 
{
    enum { value = is_prime<N>::value ? N * prime_fact<N-1>::value : prime_fact<N-1>::value };
};

template <> struct prime_fact<0>
{
    enum { value = 1 };
};

template <unsigned int N> struct largest_prime_smaller_or_equal 
{
    enum { value = is_prime<N>::value ? N : largest_prime_smaller_or_equal<N-1>::value };
};

template <> struct largest_prime_smaller_or_equal<1>
{
    enum { value = 0 };
};

template <unsigned int OFFSET, unsigned int N> struct good_offset
{
    enum { value = OFFSET % N ? good_offset<OFFSET, largest_prime_smaller_or_equal<N-1>::value >::value : 0 };
};

template <unsigned int OFFSET> struct good_offset<OFFSET, 0>
{
    enum { value = 1 };
};

template <unsigned int N> struct good_offset<1, N>
{
    enum { value = 1 };
};

template <unsigned int OFFSET, unsigned int N> struct largest_offset_smaller_or_equal
{
    enum { value = good_offset<OFFSET, N>::value ? OFFSET : largest_offset_smaller_or_equal<OFFSET-1, N>::value };
};

template <unsigned int N> struct largest_offset_smaller_or_equal<1, N>
{
    enum { value = 1 };
};
template<unsigned int N> inline bool is_prime_lower_or_equal (unsigned long long x)
{
    if (x > N)
    {
        return 0;
    }
    else if (x == N)
    {
        return is_prime<N>::value;
    }
    else
    {
        return is_prime_lower_or_equal<N-1> (x);
    }
};

template <> inline bool is_prime_lower_or_equal<1> (unsigned long long x)
{
    return 0;
};

template <unsigned int N> inline bool not_dividable_by_prime_or_smaller (unsigned long long x)
{
    return ((x % N) && not_dividable_by_prime_or_smaller< largest_prime_smaller_or_equal <N-1>::value >(x));  
}

template <> inline bool not_dividable_by_prime_or_smaller<0> (unsigned long long x)
{
    return true;  
}

template <unsigned int N> inline bool not_dividable_by_prime_smaller_or_equal (unsigned long long x)
{
    return not_dividable_by_prime_or_smaller< largest_prime_smaller_or_equal <N>::value >(x);
};

template <unsigned int OFFSET, unsigned int N> inline bool not_dividable_by_offset_or_smaller (unsigned long base, unsigned long long x)
{
    return (x % (base + OFFSET)) && (not_dividable_by_offset_or_smaller<largest_offset_smaller_or_equal<OFFSET - 1,N>::value, (largest_offset_smaller_or_equal<OFFSET-1,N>::value == 1) ? 1 : N>(base, x));
    /* bool res = (x % (base + OFFSET)) && (not_dividable_by_offset_or_smaller<largest_offset_smaller_or_equal<OFFSET - 1,N>::value, (largest_offset_smaller_or_equal<OFFSET-1,N>::value == 1) ? 1 : N>(base, x));
    cout << "not_dividable_by_offset_or_smaller<" << OFFSET << "," << N << ">(" << base << "," << x << ")";
    cout << "=" << res << endl;
    return res;
    */    
}

template <> inline bool not_dividable_by_offset_or_smaller<1, 1> (unsigned long base, unsigned long long x)
{
    return x % (base + 1);
    /* bool res = x % (base + 1);
    cout << "not_dividable_by_offset_or_smaller<" << 0 << "," << 1 << ">(" << base << "," << x << ")";
    cout << "=" << res << endl;
    return res;
    */
}

template<unsigned int N> inline bool isPrime(unsigned long long x)
{
    if (x <= prime_fact<N>::value)
    {
        if (is_prime_lower_or_equal<prime_fact<N>::value >(x))
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    else if (not_dividable_by_prime_smaller_or_equal< prime_fact<N>::value >(x))
    {
        const unsigned long long maxx = (unsigned long long) sqrt(x);
        register const unsigned long max = maxx > (unsigned long long)ULONG_MAX ? ULONG_MAX : maxx;
        // const unsigned long long step = prime_fact<N>::value;
        register unsigned long base = prime_fact<N>::value;
        while (not_dividable_by_offset_or_smaller<prime_fact<N>::value - 1, N>(base, x) && base < max) base += prime_fact<N>::value;
        if (base < x) return false;
    }
    else
    {
        return false;
    }
    return true;
}

int main(int argc, char** argv)
{
    unsigned long long i;
    istringstream stream(argv[1]);
    stream >> i;
    cout << "isPrime(" << i << ") = " << isPrime<DEPTH>(i) << endl;
}