# Finding the Nth Prime At Compile-time in C++

March 22, 2010 3 Comments

In C++, you can use template meta-programming to preform calculations at compile-time. The usual example, as shown on the linked page, is the factorial function.

An actual problem I’ve had before is finding the N-th prime number, where N is known at compile time. You can either have a table, but then you forget to edit it and then run out of prime numbers and that is annoying. Alternatively you can work it out at run-time, but since prime numbers don’t change, that seems like a waste of time too.

So this is a case where template meta-programming might actually be useful! The code is as follows:

// TemplateTest.cpp#include "stdio.h"template<inti>structNthPrime{template<intp>structIsPrime{template<intn >structDivisors{template<intN,intM >structDivisorsDo{staticconstintval = DivisorsDo<N,M-1>::val +((N%M)==0);};template<intN>structDivisorsDo<N,1>{staticconstintval = 0;};staticconstintval = DivisorsDo<n,n-1>::val;};staticconstintval =(Divisors<p>::val==0);};template<intn,intm>structNthPrimeDo{staticconstintval = NthPrimeDo<n-(IsPrime<m>::val),m+1>::val;};template<intm>structNthPrimeDo<1,m>{staticconstintval = m-1;};staticconstintval = NthPrimeDo<i,3>::val;};intmain(intargc,char* argv[]){printf("Prime 1: %i\nPrime 2: %i\nPrime 3: %i\nPrime 4:%i\nPrime 5:%i\nPrime 6:%i\n",NthPrime<1>::val,NthPrime<2>::val,NthPrime<3>::val,NthPrime<4>::val,NthPrime<5>::val,NthPrime<6>::val);while(1);return0;}

Finding each prime can add a few seconds to the compile time, and on the testing computers it couldn’t really work out any higher than the 50th prime number. However, it would’ve been quite cool for my purposes (although my solution at the time of using Mathematica’s CForm output probably worked better).

Meta-programming with templates makes you think about things in exactly the same way as you would for Recursive functions in Logic.

The first thing to do is to make a function which counts the number of proper divisors of a number, call it *n*. To do this, it should check if *n-1* is, if *n-2* is, and so on. Thus you get something like:

Divisors(n) := DivisorsDo(n,n-1) DivisorsDo(n,m) := (1 if n|m, 0 otherwise) + DivisorsDo(n,m-1) DivisorsDo(n,1) := 0

Now we can easily check if a number is prime:

IsPrime(n) := (Divisors(n)==0)

Thus finding the Nth prime requires us to look up the numbers (in the second argument) and decrease the number we still need to find (in the first argument):

NthPrime(n) := NthPrimeDo(n,3) NthPrimeDo(n,m) := if ( IsPrime(m) ) then NthPrimeDo(n-1,m+1) else NthPrimeDo(n,m+1) NthPrimeDo(1,m) := m-1

Nice article! It may be of interest for you, that in C++0x you can use

constexprfunctions to realize the same thing, but both simpler and much nearer to the formal presentation. The following works with gcc 4.6:constexpr int divisors_do(int n, int m) {

return m == 1 ? 0 : divisors_do(n, m – 1) + ((n % m) == 0);

}

constexpr int divisors(int q) {

return divisors_do(q, q – 1);

}

constexpr bool is_prime(int p) {

return divisors(p) == 0;

}

constexpr int nth_prime_do(int n, int m) {

return n == 1 ? m – 1 : nth_prime_do(n – is_prime(m), m + 1);

}

constexpr int nth_prime(int i) {

return nth_prime_do(i, 3);

}

static_assert(nth_prime(1) == 2, “nth-prime error”);

static_assert(nth_prime(2) == 3, “nth-prime error”);

static_assert(nth_prime(3) == 5, “nth-prime error”);

static_assert(nth_prime(4) == 7, “nth-prime error”);

static_assert(nth_prime(5) == 11, “nth-prime error”);

static_assert(nth_prime(6) == 13, “nth-prime error”);

static_assert(nth_prime(7) == 17, “nth-prime error”);

static_assert(nth_prime(8) == 19, “nth-prime error”);

static_assert(nth_prime(9) == 23, “nth-prime error”);

static_assert(nth_prime(10) == 29, “nth-prime error”);

static_assert(nth_prime(20) == 71, “nth-prime error”);

static_assert(nth_prime(30) == 113, “nth-prime error”);

static_assert(nth_prime(40) == 173, “nth-prime error”);

static_assert(nth_prime(50) == 229, “nth-prime error”);

static_assert(nth_prime(60) == 281, “nth-prime error”);

static_assert(nth_prime(70) == 349, “nth-prime error”);

static_assert(nth_prime(80) == 409, “nth-prime error”);

static_assert(nth_prime(90) == 463, “nth-prime error”);

static_assert(nth_prime(100) == 541, “nth-prime error”);

static_assert(nth_prime(200) == 1223, “nth-prime error”);

int main() {}

Yes, I saw on Wikipedia the

constexprfeature, although I did not know the exact syntax. It is much nicer, yes. Would constexpr still work OK if you programmed it in the usual procedural way (i.e. with a for loop), rather than in the more functional way you used above?As of the current working draft of C++0x they are only allowed to have a single return expression, i.e.

excluding loops 😦

I’m convinced that constexpr function will have a lot of interesting use-cases and depending on those

such restrictions could be removed in future versions of the standard. They are they only compile-time tool that I’m aware of, that will allow for direct compile-time operations on string literals, for example.