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

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<int i>
struct NthPrime
{
	template<int p>
	struct IsPrime
	{
		template< int n >
		struct Divisors
		{
			template< int N , int M >
			struct DivisorsDo
			{
				static const int val = DivisorsDo<N,M-1>::val + ((N%M)==0);
			};
		
			template<int N>
			struct DivisorsDo<N,1>
			{
				static const int val = 0;
			};
		
			static const int val = DivisorsDo<n,n-1>::val;
		};
		static const int val = (Divisors<p>::val==0);
	};

	template<int n, int m>
	struct NthPrimeDo
	{
		static const int val =  NthPrimeDo<n-(IsPrime<m>::val),m+1>::val;
	};

	template<int m>
	struct NthPrimeDo<1,m>
	{
		static const int val = m-1;
	};
	static const int val = NthPrimeDo<i,3>::val;
};




int main(int argc, 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);
	return 0;
}

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
Advertisements

3 Responses to Finding the Nth Prime At Compile-time in C++

  1. Daniel Krügler says:

    Nice article! It may be of interest for you, that in C++0x you can use constexpr functions 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() {}

    • Jax says:

      Yes, I saw on Wikipedia the constexpr feature, 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?

      • Daniel Krügler says:

        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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: