Check if a number is prime at compile time in C ++

Question

I have a template class that accepts an unsigned integer as a template parameter, but I have to make sure the number is prime. I can check this in the constructor, for example, but it would be better to do this at compile time.

Here is the Assert template that I use:

template <bool statement> class Assert; template <> struct Assert<true> {}; 

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

I came up with a separate file called “PrimeTest.h” and try to split n into each number from n-1 to 1 by including the same file from this file. Here is how I use it:

 #define SUSPECT n #include "PrimeTest.h" 

This is "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 is the problem: I cannot reduce CURRENT in any way I could come up with, including temporary values ​​and #pragma push_macro directives. Any ideas how to do this?

Answer 1

You do not need a preprocessor to compute something at compile time. Usually, when the calculation is necessary, you use metaprogramming the template (or constexpr functions suggested by Chris in his answer)

Through metaprogramming templates, you can solve the problem as follows:

First you define a pattern that can be checked at compile time if the given value of N is divisible by D or any value below 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 of tmp<N,D>::result is true only if the numbers 2, 3, ... D do not divide N

Using the tool above, creating an is_prime compile time check is pretty simple:

 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 added to additional templates, for example, to your Assert .

Answer 2

C ++ 11 constexpr version, which should be able to check numbers up to about 1500 on any compiler that implements the proposed recursion depth limit:

 constexpr bool is_prime_helper( std::size_t target, std::size_t check ) { return (check*check > target) || ( (target%(check+1) != 0) && (target%(check+5) != 0) && is_prime_helper( target, check+6 ) ); } constexpr bool is_prime( std::size_t target ) { return (target != 0) && (target !=1) && ( ( target == 2 || target == 3 || target == 5 ) || ((target%2 != 0) && (target%3 != 0) && (target%5)!=0 && is_prime_helper( target, 6 ))); } 

to improve this, we had some fun in the binary search tree:

 #include <cstddef> constexpr bool any_factors( std::size_t target, std::size_t start, std::size_t step) { return !(start*start*36 > target) && ( ( (step==1) && ( (target%(start*6+1) == 0) || (target%(start*6+5) == 0) ) ) || ( (step > 1) && ( any_factors( target, start, step/2 ) || any_factors( target, start+step/2, step/2 ) ) ) ); } 

which we then use as follows:

 constexpr bool is_prime( std::size_t target ) { // handle 2, 3 and 5 explicitly: return (target == 2 || target == 3 || target == 5) || ( target != 0 && target != 1 && target%2 != 0 && target%3 != 0 && target%5 != 0 && !any_factors( target, 1, target/6 + 1 ) // can make that upper bound a bit tighter, but I don't care ); } #include <iostream> int main() { std::cout << "97:" << is_prime(97) << "\n"; std::cout << "91:" << is_prime(91) << "\n"; } 

which will be recursive ~ log_2(target/6) times, which means that the recursion limit in constexpr expressions 512, which are standard C ++ 11 queries that compilers execute at least, is no longer a problem.

Live example , with debugging built-in.

This will work mainly with std::size_t restrictions on your system. I tested it with 111111113 .

Answer 3

Here's an amateurish solution that is designed for positive numbers and is executed at compile time, but it cannot go too far before it breaks from outside the recursion limit. I suppose you could add a square root parameter that you calculate manually to allow it to go to what it now has in the square. However, it uses the power of C ++ 11 constexpr to make the syntax more enjoyable to use without additional work. In any case, this could be a good start, and I look forward to hearing more effective answers.

 constexpr bool IsPrime(std::size_t N, std::size_t I = 2) { return (N != 2 ? N%I : true) //make 2 prime and check divisibility if not 2 && (N >= 2) //0 and 1 are not prime && (I >= N-1 ? true : IsPrime(N, I+1)); //stop when I is too big } 

You can even make this square root for you. In this example, I will make IsPrime in the helper so that IsPrime can only be called with N :

 //basically does ceil(sqrt(N)) constexpr std::size_t Sqrt(std::size_t N, std::size_t I = 2) { return I*I >= N ? I : Sqrt(N, I+1); } //our old IsPrime function with no default arguments; works with sqrt now constexpr bool IsPrimeHelper(std::size_t N, std::size_t sqrt, std::size_t I) { return (N != 2 ? N%I : true) && (N >= 2) && (I >= sqrt ? true : IsPrimeHelper(N, sqrt, I+1)); } //our new prime function: this is the interface for the user constexpr bool IsPrime(std::size_t N) { return IsPrimeHelper(N, Sqrt(N), 2); } 

For me, this new version works with number 521, where the other crashes. It even works with 9973. The new expected maximum should be about the square of the old. If you want to go further, you can even change IsPrimeHelper to increase by 1, when I is 2 and 2, if I not equal to 2. This will lead to a new maximum of about two times.