Calculating Prime Numbers on C ++ Templates

In this post I will tell you how to do a completely useless thing - to calculate simple numbers using C ++ templates.

The algorithms are illustrated with a code in Scheme, so be careful: brackets!

Control structures

We want to get compile-time analog function. In programming on templates, the function is the structure, the template parameters of which correspond to the arguments of the function and the constant static terms to the results.
')

(define (fx) (* xx)) (f 10) ; => 100 

Similar C ++ code:

 template<int x> struct f { static const int value = x * x; }; 

The “call” of such a function occurs through template instantiation:

 int main() { std::cout << f<10>::value << std::endl; // 100 } 

C ++ templates allow you to handle certain values ​​of template parameters in a special way (specialization). This allows you to organize a conditional control structure:

 (define (gx) (if (= x 0) 42 (* xx))) (g 10) ; => 100 (g 0) ; => 42 

 template<int x> struct g { static const int value = x * x; }; template<> struct g<0> { static const int value = 42; }; int main() { std::cout << g<10>::value << std::endl; // 100 std::cout << g<0>::value << std::endl; // 42 } 

For the organization of cyclic processing we will use recursion. The above techniques are enough to describe any function.

Calculation of prime numbers

Formulation of the problem

We want to get a function that returns ie a prime number:

 int main() { std::cout << prime<0>::value << std::endl; // 2 std::cout << prime<1>::value << std::endl; // 3 std::cout << prime<2>::value << std::endl; // 5 std::cout << prime<3>::value << std::endl; // 7 // ... } 

Check for simplicity

This function cannot be implemented right away, you need to start with something simpler. The easiest way to check is whether some n is a prime number. To verify, we check that the remainder of dividing n by all numbers from n-1 to 1 is not equal to zero.

 (define (is-prime n) (is-prime-rec n (- n 1))) (define (is-prime-rec n div) (if (or (= div 1) (= div 0)) #t (and (not (= 0 (remainder n div))) (is-prime-rec n (- div 1))))) (is-prime 2) ; => #t (is-prime 3) ; => #t (is-prime 4) ; => #f (is-prime 5) ; => #t 

 template<int n, int div> struct is_prime_rec { static const bool value = (n % div != 0) && is_prime_rec<n, div - 1>::value; }; template<int n> struct is_prime_rec<n, 1> { static const bool value = true; }; template<int n> struct is_prime_rec<n, 0> { static const bool value = true; }; template<int n> struct is_prime { static const bool value = is_prime_rec<n, n - 1>::value; }; int main() { std::cout << is_prime<1>::value << std::endl; // 1 std::cout << is_prime<2>::value << std::endl; // 1 std::cout << is_prime<3>::value << std::endl; // 1 std::cout << is_prime<4>::value << std::endl; // 0 std::cout << is_prime<5>::value << std::endl; // 1 std::cout << is_prime<6>::value << std::endl; // 0 std::cout << is_prime<7>::value << std::endl; // 1 } 

The question of whether to consider 1 as a prime number is left open, but in this implementation of verification 1 is considered simple.

Finding the next prime number

We define the function that finds the smallest prime number greater than the given one (that is, the following).

 (define (next-prime n) (if (is-prime (+ n 1)) (+ n 1) (next-prime (+ n 1)))) (next-prime 2) ; => 3 (next-prime 3) ; => 5 (next-prime 5) ; => 7 (next-prime 7) ; => 11 

 template<int n> struct next_prime; template<int n, bool cond> struct next_prime_if { static const int value = n + 1; }; template<int n> struct next_prime_if<n, false> { static const int value = next_prime<n + 1>::value; }; template<int n> struct next_prime { static const int value = next_prime_if<n, is_prime<n + 1>::value>::value; }; int main() { std::cout << next_prime<1>::value << std::endl; // 2 std::cout << next_prime<2>::value << std::endl; // 3 std::cout << next_prime<3>::value << std::endl; // 5 std::cout << next_prime<4>::value << std::endl; // 5 std::cout << next_prime<5>::value << std::endl; // 7 std::cout << next_prime<6>::value << std::endl; // 7 std::cout << next_prime<7>::value << std::endl; // 11 } 

Finding just numbers by number

What is a prime number? This is following the (i-1) -m:

 (define (prime i) (if (= i 0) 2 (next-prime (prime (- i 1))))) (prime 0) ; => 2 (prime 1) ; => 3 (prime 2) ; => 5 (prime 3) ; => 7 

 template<int i> struct prime { static const int value = next_prime<prime<i - 1>::value >::value; }; template<> struct prime<0> { static const int value = 2; }; int main() { std::cout << prime<0>::value << std::endl; // 2 std::cout << prime<1>::value << std::endl; // 3 std::cout << prime<2>::value << std::endl; // 5 std::cout << prime<3>::value << std::endl; // 7 std::cout << prime<4>::value << std::endl; // 11 // ... } 

Full source code:
Scheme pastebin.com/21VFjYt0
C ++ pastebin.com/cfSvBRNH