O(sqrt(n))

tmp-prime.cpp

#include <iostream>
template<bool Cond>
struct bool_;
template<>
struct bool_<true> {
    static const bool value = true;
};
template<>
struct bool_<false> {
    static const bool value = false;
};

template<bool Cond, class Then, class Else>
struct if_;

template<class Then, class Else>
struct if_<true, Then, Else> {
    typedef Then type;
};

template<class Then, class Else>
struct if_<false, Then, Else> {
    typedef Else type;
};
template<class T, T arg0, T arg1>
struct lt {
    static const bool value = arg0 < arg1;
};
template<int N, int M>
struct is_prime {
    static const bool value = 
        if_< lt<int,N,M*M>::value, bool_<true>,
        typename if_< (N%M==0) ,bool_<false>, is_prime<N,M+1> >::type >::type::value;
};

int main() {
    if(is_prime<1009,2>::value) {
        std::cout<<"prime"<<std::endl;
    }
    else {
        std::cout<<"not prime"<<std::endl;

    }

    return 0;
}