Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Check if number is prime during compilation in C++

I have a template class that takes an unsigned integer as template parameter, but I have to make sure that number is a prime. I can check it in the constructor, for instance, but it would be better to do it during compilation.

Here's the Assert template I'm using:

template <bool statement>
class Assert;

template <>
struct Assert<true> {};

I can simply create an object of this type in any piece of code which is going to be compiled, using my condition as parameter, and it won't compile if that condition is false. The problem is that I have to check if some number is prime. Let it be n.

I've came up with the idea of including a separate file "PrimeTest.h" and trying to divide n by each number from n-1 to 1 by including the same file from inside that file. That is how I use it:

#define SUSPECT n
#include "PrimeTest.h"

This is the "PrimeTest.h":

#ifdef SUSPECT

    #ifndef CURRENT
        #define CURRENT (SUSPECT-1)
    #endif // CURRENT

    #ifndef FINISHED

    #if CURRENT>100
        #define IS_PRIME
        #define FINISHED
    #else
        #if SUSPECT%CURRENT==0
            #define IS_NOT_PRIME
            #define FINISHED
        #else
            #define CURRENT (CURRENT-1)  // THAT DOES NOT WORK!!!
            #include "PrimeTest.h"
        #endif // SUSPECT % CURRENT != 0
    #endif

    #endif // FINISHED

#endif // SUSPECT

But here's the problem: I can't decrement CURRENT in any way I could come up with, including temporary values and #pragma push_macro directives. Any ideas how to do that?

like image 788
Danylo Fitel Avatar asked May 26 '13 16:05

Danylo Fitel


1 Answers

You do not need preprocessor to compute something at compile-time. Usually, when computation is needed, you use template metaprogramming (or constexpr functions as suggested by chris in his answer)

Via template metaprogramming you can solve the task as follows:

First you define a template which can check at compile time if the given value N is divisble by D or any value lower than D greater than 1.

template <int N, int D>
struct tmp {
    static const bool result = (N%D) && tmp<N,D-1>::result;
};

template <int N>
struct tmp<N,1> {
    static const bool result = true;
};

The value tmp<N,D>::result is true only when the numbers 2, 3, ... D do not divide N.

With the above tool at hand, creating is_prime compile-time checker is fairly easy:

template <int N>
struct is_prime {
    static const bool result = tmp<N,N-1>::result;
};

Now the compile-time value is_prime<N>::result is true when N is prime, and false otherwise. The value can be supplied to further templates, like the Assert of yours.

like image 87
CygnusX1 Avatar answered Sep 27 '22 20:09

CygnusX1