読者です 読者をやめる 読者になる 読者になる

ゆとりーなの日記

日記的な事を書いて行くと思はれる

実行時に素数計算とかアド損

元ネタはこちら。http://ideone.com/lq0xC
これに対する弗先生の煽りを受けて、世紀末素数生成ですよと。
発起人のK先生と弗先生が0xやBoostの環境があるのかどうか分からなかったので現行C++でも通るようにしといたんで安心ですね。

// 出力補助テンプレート引き数用クラス
struct ha {};
struct banmenososu {};

// 出力用テンプレートクラス
template <int Sosu, typename Ha, int Bango, typename BanmenoSosu>
struct output {};

// 悪さして警告を出すことにより型名を強制表示
template <typename T>
struct print {
  enum {
    n = sizeof(T) > -1
  };
  typedef void type;
};

// 出力しない時用のダミークラス
struct not_print {
  typedef void type;
};

// ループを止める仕掛け用のクラス
template <bool>
struct end_for {};

template <>
struct end_for<true> {
  typedef void type;
};

// コンパイル時条件分岐用のクラス
template <bool, typename Then, typename Else>
struct if_ {
  typedef typename Then::type type;
};

template <typename Then, typename Else>
struct if_<false, Then, Else> {
  typedef typename Else::type type;
};

// テンプレート引数の意味
// I:割る数, J:割られる数, K:素数でない数の個数, M:m番目の素数, N:求めたいN番目の素数, 

// KとMを運搬するクラス
template <int K, int M>
struct km {
  static const int k = K;
  static const int m = M;
  typedef km<k, m> type;
};

// 内側のfor文でやっていることを表すテンプレートクラス
template <int I, int J, int K, int M, typename T = void>
struct for2 {
  // 割れなかったらここでチェックの出力の部分
  // (I * I > J)が真の時のみ型名が出力される
  typedef typename if_<(I * I > J),
                       print<output<J, ha, M, banmenososu> >,
                       not_print>::type print_type;
  // 何かで割れたら「素数でない」にカウントして次のj(割られる数)へと
  // 割れなかったらここでチェックをやってる部分
  // (J != I && !(J % I))が真ならKに1たして次のjへ
  // 上が偽で(I + I > J)が真ならMに1足して次のjへ
  // 全て偽なら割る数を1足して再帰
  // 世紀末プログラミングではループは書けないので必然的に再帰となる
  typedef typename if_<J != I && !(J % I),
                       km<K + 1, M>,
                       if_<(I * I > J),
                           km<K, M + 1>, 
                           for2<I + 1, J, K, M> > >::type type;
};

// (I == J)が真の時にループが止まるように特殊化した内側のfor文でやっていることを表すテンプレートクラス
template <int I, int J, int K, int M>
struct for2<I, J, K, M, typename end_for<I == J>::type> {
  typedef typename if_<(I * I > J),
                       print<output<J, ha, M, banmenososu> >,
                       not_print>::type print_type;
  // ループの最後を表すので再帰の項は不要、代わりに現状のKとMを維持して次のjへ
  typedef typename if_<J != I && !(J % I),
                       km<K + 1, M>,
                       if_<(I * I > J),
                           km<K, M + 1>, 
                           km<K, M> > >::type type;
};

// 外側のfor文を表すテンプレートクラス
// Tはループを止めるための仕掛け
template <int J, int K, int M, int N, typename T = void>
struct for_ {
  // 内側のfor文を表すテンプレートクラスの結果を保持しておく
  typedef typename for2<2, J, K, M>::type type;
  // ループの代わりに再帰
  static const bool value = for_<J + 1, type::k, type::m, N>::value; 
};

// (J - K > N)が真の時にループが止まるように特殊化した外側のfor文を表すテンプレートクラス
template <int J, int K, int M, int N>
struct for_<J, K, M, N, typename end_for<(J - K > N)>::type> {
  // 終わった感をアピールするためtrueを返す
  static const bool value = true;
};

int main() {
  const int n = 10; //求めたいn番目の素数 本当は10001
  for_<2, 1, 1, n>::value; // コンパイル時に計算
  return 0;
}

諸事情によりコメント多めにしておいたので更に安心です。
注意としては、コンパイル時に計算しているのでコンパイルして出来た./a.outを実行しても何も起きないところですかね。代わりにこのソースをg++ -Wallでコンパイルすると出力結果によーく目を凝らすことでoutput<29, ha, 10, banmenososu>のような文字列を含む警告文が見つかるはずです。
以下コンパイル時の出力です。

$ g++ sosu.cc -Wall
sosu.cc: In instantiation of ‘print<output<2, ha, 1, banmenososu> >’:
sosu.cc:35:31:   instantiated from ‘if_<true, print<output<2, ha, 1, banmenososu> >, not_print>’
sosu.cc:82:41:   instantiated from ‘for2<2, 2, 1, 1, void>’
sosu.cc:100:43:   instantiated from ‘for_<2, 1, 1, 10>’
sosu.cc:114:19:   instantiated from here
sosu.cc:12:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
sosu.cc: In instantiation of ‘print<output<3, ha, 2, banmenososu> >’:
sosu.cc:35:31:   instantiated from ‘if_<true, print<output<3, ha, 2, banmenososu> >, not_print>’
sosu.cc:61:41:   instantiated from ‘for2<2, 3, 1, 2, void>’
sosu.cc:100:43:   instantiated from ‘for_<3, 1, 2, 10, void>’
sosu.cc:102:63:   instantiated from ‘const bool for_<2, 1, 1, 10>::value’
sosu.cc:114:21:   instantiated from here
sosu.cc:12:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
sosu.cc: In instantiation of ‘print<output<5, ha, 3, banmenososu> >’:
sosu.cc:35:31:   instantiated from ‘if_<true, print<output<5, ha, 3, banmenososu> >, not_print>’
sosu.cc:40:31:   recursively instantiated from ‘if_<false, km<2, 4>, for2<3, 5, 2, 3, void> >’
sosu.cc:40:31:   instantiated from ‘if_<false, km<3, 3>, if_<false, km<2, 4>, for2<3, 5, 2, 3, void> > >’
sosu.cc:72:59:   instantiated from ‘for2<2, 5, 2, 3, void>’
sosu.cc:102:63:   recursively instantiated from ‘const bool for_<3, 1, 2, 10, void>::value’
sosu.cc:102:63:   instantiated from ‘const bool for_<2, 1, 1, 10>::value’
sosu.cc:114:21:   instantiated from here
sosu.cc:12:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
sosu.cc: In instantiation of ‘print<output<7, ha, 4, banmenososu> >’:
sosu.cc:35:31:   instantiated from ‘if_<true, print<output<7, ha, 4, banmenososu> >, not_print>’
sosu.cc:40:31:   recursively instantiated from ‘if_<false, km<3, 5>, for2<3, 7, 3, 4, void> >’
sosu.cc:40:31:   instantiated from ‘if_<false, km<4, 4>, if_<false, km<3, 5>, for2<3, 7, 3, 4, void> > >’
sosu.cc:72:59:   instantiated from ‘for2<2, 7, 3, 4, void>’
sosu.cc:102:63:   recursively instantiated from ‘const bool for_<3, 1, 2, 10, void>::value’
sosu.cc:102:63:   instantiated from ‘const bool for_<2, 1, 1, 10>::value’
sosu.cc:114:21:   instantiated from here
sosu.cc:12:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
sosu.cc: In instantiation of ‘print<output<11, ha, 5, banmenososu> >’:
sosu.cc:35:31:   instantiated from ‘if_<true, print<output<11, ha, 5, banmenososu> >, not_print>’
sosu.cc:40:31:   recursively instantiated from ‘if_<false, km<6, 6>, for2<4, 11, 6, 5, void> >’
sosu.cc:40:31:   instantiated from ‘if_<false, km<7, 5>, if_<false, km<6, 6>, for2<4, 11, 6, 5, void> > >’
sosu.cc:40:31:   recursively instantiated from ‘if_<false, km<6, 6>, for2<3, 11, 6, 5, void> >’
sosu.cc:40:31:   instantiated from ‘if_<false, km<7, 5>, if_<false, km<6, 6>, for2<3, 11, 6, 5, void> > >’
sosu.cc:72:59:   instantiated from ‘for2<2, 11, 6, 5, void>’
sosu.cc:102:63:   recursively instantiated from ‘const bool for_<3, 1, 2, 10, void>::value’
sosu.cc:102:63:   instantiated from ‘const bool for_<2, 1, 1, 10>::value’
sosu.cc:114:21:   instantiated from here
sosu.cc:12:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
sosu.cc: In instantiation of ‘print<output<13, ha, 6, banmenososu> >’:
sosu.cc:35:31:   instantiated from ‘if_<true, print<output<13, ha, 6, banmenososu> >, not_print>’
sosu.cc:40:31:   recursively instantiated from ‘if_<false, km<7, 7>, for2<4, 13, 7, 6, void> >’
sosu.cc:40:31:   instantiated from ‘if_<false, km<8, 6>, if_<false, km<7, 7>, for2<4, 13, 7, 6, void> > >’
sosu.cc:40:31:   recursively instantiated from ‘if_<false, km<7, 7>, for2<3, 13, 7, 6, void> >’
sosu.cc:40:31:   instantiated from ‘if_<false, km<8, 6>, if_<false, km<7, 7>, for2<3, 13, 7, 6, void> > >’
sosu.cc:72:59:   instantiated from ‘for2<2, 13, 7, 6, void>’
sosu.cc:102:63:   recursively instantiated from ‘const bool for_<3, 1, 2, 10, void>::value’
sosu.cc:102:63:   instantiated from ‘const bool for_<2, 1, 1, 10>::value’
sosu.cc:114:21:   instantiated from here
sosu.cc:12:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
sosu.cc: In instantiation of ‘print<output<17, ha, 7, banmenososu> >’:
sosu.cc:35:31:   instantiated from ‘if_<true, print<output<17, ha, 7, banmenososu> >, not_print>’
sosu.cc:40:31:   recursively instantiated from ‘if_<false, km<10, 8>, for2<5, 17, 10, 7, void> >’
sosu.cc:40:31:   instantiated from ‘if_<false, km<11, 7>, if_<false, km<10, 8>, for2<5, 17, 10, 7, void> > >’
sosu.cc:40:31:   recursively instantiated from ‘if_<false, km<10, 8>, for2<4, 17, 10, 7, void> >’
sosu.cc:40:31:   instantiated from ‘if_<false, km<11, 7>, if_<false, km<10, 8>, for2<4, 17, 10, 7, void> > >’
sosu.cc:40:31:   recursively instantiated from ‘if_<false, km<10, 8>, for2<3, 17, 10, 7, void> >’
sosu.cc:40:31:   instantiated from ‘if_<false, km<11, 7>, if_<false, km<10, 8>, for2<3, 17, 10, 7, void> > >’
sosu.cc:72:59:   instantiated from ‘for2<2, 17, 10, 7, void>’
sosu.cc:102:63:   recursively instantiated from ‘const bool for_<3, 1, 2, 10, void>::value’
sosu.cc:102:63:   instantiated from ‘const bool for_<2, 1, 1, 10>::value’
sosu.cc:114:21:   instantiated from here
sosu.cc:12:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
sosu.cc: In instantiation of ‘print<output<19, ha, 8, banmenososu> >’:
sosu.cc:35:31:   instantiated from ‘if_<true, print<output<19, ha, 8, banmenososu> >, not_print>’
sosu.cc:40:31:   recursively instantiated from ‘if_<false, km<11, 9>, for2<5, 19, 11, 8, void> >’
sosu.cc:40:31:   instantiated from ‘if_<false, km<12, 8>, if_<false, km<11, 9>, for2<5, 19, 11, 8, void> > >’
sosu.cc:40:31:   recursively instantiated from ‘if_<false, km<11, 9>, for2<4, 19, 11, 8, void> >’
sosu.cc:40:31:   instantiated from ‘if_<false, km<12, 8>, if_<false, km<11, 9>, for2<4, 19, 11, 8, void> > >’
sosu.cc:40:31:   recursively instantiated from ‘if_<false, km<11, 9>, for2<3, 19, 11, 8, void> >’
sosu.cc:40:31:   instantiated from ‘if_<false, km<12, 8>, if_<false, km<11, 9>, for2<3, 19, 11, 8, void> > >’
sosu.cc:72:59:   instantiated from ‘for2<2, 19, 11, 8, void>’
sosu.cc:102:63:   recursively instantiated from ‘const bool for_<3, 1, 2, 10, void>::value’
sosu.cc:102:63:   instantiated from ‘const bool for_<2, 1, 1, 10>::value’
sosu.cc:114:21:   instantiated from here
sosu.cc:12:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
sosu.cc: In instantiation of ‘print<output<23, ha, 9, banmenososu> >’:
sosu.cc:35:31:   instantiated from ‘if_<true, print<output<23, ha, 9, banmenososu> >, not_print>’
sosu.cc:40:31:   recursively instantiated from ‘if_<false, km<14, 10>, for2<5, 23, 14, 9, void> >’
sosu.cc:40:31:   instantiated from ‘if_<false, km<15, 9>, if_<false, km<14, 10>, for2<5, 23, 14, 9, void> > >’
sosu.cc:40:31:   recursively instantiated from ‘if_<false, km<14, 10>, for2<4, 23, 14, 9, void> >’
sosu.cc:40:31:   instantiated from ‘if_<false, km<15, 9>, if_<false, km<14, 10>, for2<4, 23, 14, 9, void> > >’
sosu.cc:40:31:   recursively instantiated from ‘if_<false, km<14, 10>, for2<3, 23, 14, 9, void> >’
sosu.cc:40:31:   instantiated from ‘if_<false, km<15, 9>, if_<false, km<14, 10>, for2<3, 23, 14, 9, void> > >’
sosu.cc:72:59:   instantiated from ‘for2<2, 23, 14, 9, void>’
sosu.cc:102:63:   recursively instantiated from ‘const bool for_<3, 1, 2, 10, void>::value’
sosu.cc:102:63:   instantiated from ‘const bool for_<2, 1, 1, 10>::value’
sosu.cc:114:21:   instantiated from here
sosu.cc:12:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
sosu.cc: In instantiation of ‘print<output<29, ha, 10, banmenososu> >’:
sosu.cc:35:31:   instantiated from ‘if_<true, print<output<29, ha, 10, banmenososu> >, not_print>’
sosu.cc:61:41:   instantiated from ‘for2<6, 29, 19, 10, void>’
sosu.cc:40:31:   instantiated from ‘if_<false, km<20, 10>, if_<false, km<19, 11>, for2<6, 29, 19, 10, void> > >’
sosu.cc:72:59:   instantiated from ‘for2<5, 29, 19, 10, void>’
sosu.cc:40:31:   [ skipping 2 instantiation contexts ]
sosu.cc:40:31:   recursively instantiated from ‘if_<false, km<19, 11>, for2<4, 29, 19, 10, void> >’
sosu.cc:40:31:   instantiated from ‘if_<false, km<20, 10>, if_<false, km<19, 11>, for2<4, 29, 19, 10, void> > >’
sosu.cc:40:31:   recursively instantiated from ‘if_<false, km<19, 11>, for2<3, 29, 19, 10, void> >’
sosu.cc:40:31:   instantiated from ‘if_<false, km<20, 10>, if_<false, km<19, 11>, for2<3, 29, 19, 10, void> > >’
sosu.cc:72:59:   instantiated from ‘for2<2, 29, 19, 10, void>’
sosu.cc:102:63:   recursively instantiated from ‘const bool for_<3, 1, 2, 10, void>::value’
sosu.cc:102:63:   instantiated from ‘const bool for_<2, 1, 1, 10>::value’
sosu.cc:114:21:   instantiated from here
sosu.cc:12:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
sosu.cc: In function ‘int main()’:
sosu.cc:114:26: warning: statement has no effect [-Wunused-value]

分かりにくければ標準エラーを標準出力にリダイレクトして適当にgrepかければ一目瞭然ですね。

$ g++ sosu.cc -Wall 2>&1 | grep 'print.*> >.:'
sosu.cc: In instantiation of ‘print<output<2, ha, 1, banmenososu> >’:
sosu.cc: In instantiation of ‘print<output<3, ha, 2, banmenososu> >’:
sosu.cc: In instantiation of ‘print<output<5, ha, 3, banmenososu> >’:
sosu.cc: In instantiation of ‘print<output<7, ha, 4, banmenososu> >’:
sosu.cc: In instantiation of ‘print<output<11, ha, 5, banmenososu> >’:
sosu.cc: In instantiation of ‘print<output<13, ha, 6, banmenososu> >’:
sosu.cc: In instantiation of ‘print<output<17, ha, 7, banmenososu> >’:
sosu.cc: In instantiation of ‘print<output<19, ha, 8, banmenososu> >’:
sosu.cc: In instantiation of ‘print<output<23, ha, 9, banmenososu> >’:
sosu.cc: In instantiation of ‘print<output<29, ha, 10, banmenososu> >’:

ちなみに手元のg++ではn=158までいけました。それより先はテンプレートの深さが残当してコンパイルエラーになってしまうようです。