C++のテンプレートで素数を求める

ふと、C++のテンプレートで素数の計算をさせてみようと思い立ち、コードを書いてみた。書いた後でググってみたら同じことを考えた人がやっぱりいたけど気にしない。これは車輪の再発明ではなくてパズル遊びだから。コードの書き方も違うしね。因みに、このテンプレートによる素数計算ではコンパイル完了時に既に素数が求まっており、実行ではそれを表示するだけなので、ある意味、最速の素数計算プログラムと言えるかも。

短いコードだから読めばわかると思うけど、一応説明しておく。Primesに渡したテンプレートパラメータnを1ずつ減らしながら順番にPrimeに渡して、それが素数なら出力する。素数の判定では、Primeのテンプレートパラメータdの初期値を2とし、dを増やしながらnとの剰余を求め、途中で剰余0となれば特殊化されたPrime<n, d, 0, false>が呼ばれて何もしない。dについてはテンプレートの入れ子を減らしてコンパイル時間を短くするために、2および3で割り切れない値を次のdとしている。dの二乗がnより大きくなった時点(つまりnがnの平方根以下の整数で割りきれなかった場合)、特殊化されたPrime<n, d, r, true>が呼ばれて値を出力する。

以下に100までの素数を出力するコードを示す。main関数のPrimes<100>();の数値を変更すれば任意の数までの素数を出力できる。

#include <iostream> template<int n, int d = 2, int r = 1, bool is_prime = false> struct Prime { Prime() { Prime<n, (d > 2) ? ((d + 2) % 3 ? d + 2 : d + 4) : d + 1, n % d, (n < d * d)>(); } }; template<int n, int d> struct Prime<n, d, 0, false> {}; template<int n, int d, int r> struct Prime<n, d, r, true> { Prime() { std::cout << n << std::endl; } }; template<int n> struct Primes { Primes() { Primes<n - 1>(); Prime<n>(); } }; template<> struct Primes<1> {}; int main() { Primes<100>(); return 0; }