Finding primes with template metaprogramming in modern C++

I was watching Herb Sutter's keynote from CppCon 2024 when he reached a slide showing code, credited to Erwin Unruh in 1994, for calculating prime numbers and printing them in compiler error messages. Curious, I decided to try it myself, but as written (Godbolt), it did not produce the errors he was showing in the talk.

template <int i> struct D { D(void*); operator int(); };

template <int p, int i> struct is_prime {
    enum { prim = (p%i) && is_prime<(i>2 ? p : 0), i - 1>::prim };
};

template <int i> struct Prime_print {
    Prime_print<i-1> a;
    enum { prim = is_prime<i, i-1>::prim };
    void f() { D<i> d = prim; }
};

struct is_prime<0, 0> { enum {prim=1}; };
struct is_prime<0, 1> { enum {prim=1}; };
struct Prime_print<2> { enum {prim=1}; };

main() {
    Prime_print<10> a;
}

Now, perhaps he copied it from historical slides, and maybe it compiled^[1] in 1994 with an ancient version of a compiler that existed then, but the earliest GCC in Godbolt is 3.4.6, released in 2006, and none of the compilers I tried could get past basic syntax errors.

However, even after fixing the unintentional errors, the program compiles with none of the intentional ones because Prime_print::f is never instantiated. Adding a call to it in main leads to an error in it (Godbolt), at the initialization of local variable d, but not for the reason we want: there is no conversion from the anonymous enum (the type of value prim) to one of the types accepted by a constructor of D, either D itself or void*.

template <int i> struct D { D(void*); operator int(); };

template <int p, int i> struct is_prime {
    enum { prim = (p%i) && is_prime<(i>2 ? p : 0), i - 1>::prim };
};

template <int i> struct Prime_print {
    Prime_print<i-1> a;
    enum { prim = is_prime<i, i-1>::prim };
    Prime_print() { D<i> d = prim; }
};

template <> struct is_prime<0, 0> { enum {prim=1}; };
template <> struct is_prime<0, 1> { enum {prim=1}; };
template <> struct Prime_print<2> { enum {prim=1}; };

int main() {
    Prime_print<10> a;
}

At this point, it wasn't clear how to fix this program in a way that best preserved the author's intent, but I tried to find one that most closely resembles the original code.

First, recognize that is_prime checks whether its first template argument is divisible by any positive integer between 2 and its second argument, inclusive. The instantiation in Prime_print effectively tests whether i is prime by verifying that it is not divisible by any integer less than itself (excluding 1). The result is stored in an enum, which can serve as a constant expression: 1 if i is prime and 0 otherwise. We then exploit the fact that 0 can initialize a pointer while 1 cannot to make the compiler diagnose whether i is prime in the constructor of Prime_print. Conventional template recursion, terminated by specializations, iterates over every candidate integer.

In the end, I was able to trim it down to the following (Godbolt):

template <int i, int one> struct D { D(void* = one); };

template <int p, int i> struct is_prime {
    enum { prim = (p%i) && is_prime<p, i - 1>::prim };
};

template <int i> struct Prime_print {
    Prime_print<i-1> a;
    enum { prim = is_prime<i, i-1>::prim };
    Prime_print() { D<i, prim> d; }
};

template <int p> struct is_prime<p, 1> { enum {prim=1}; };
template <> struct Prime_print<1> {};

int main() {
    Prime_print<30> a;
}

Now we can see that the program is not designed to print the first 10 primes, as Herb's sample output suggested, but rather all primes less than or equal to 10. To get the first 10 primes, I changed it to compute primes up to 30. It even works in GCC 3.4.6!

<source>: In constructor `Prime_print<i>::Prime_print() [with int i = 29]':
<source>:10:   instantiated from `Prime_print<i>::Prime_print() [with int i = 30]'
<source>:17:   instantiated from here
<source>:10: error: default argument for parameter of type `void*' has type `int'
<source>: In constructor `Prime_print<i>::Prime_print() [with int i = 23]':
<source>:10:   instantiated from `Prime_print<i>::Prime_print() [with int i = 24]'
<source>:10:   instantiated from `Prime_print<i>::Prime_print() [with int i = 25]'
<source>:10:   instantiated from `Prime_print<i>::Prime_print() [with int i = 26]'
<source>:10:   instantiated from `Prime_print<i>::Prime_print() [with int i = 27]'
<source>:10:   instantiated from `Prime_print<i>::Prime_print() [with int i = 28]'
<source>:10:   instantiated from `Prime_print<i>::Prime_print() [with int i = 29]'
<source>:10:   instantiated from `Prime_print<i>::Prime_print() [with int i = 30]'
<source>:17:   instantiated from here
<source>:10: error: default argument for parameter of type `void*' has type `int'
<source>: In constructor `Prime_print<i>::Prime_print() [with int i = 19]':
...

Footnotes