わかるんだけどさ....の続き。
たまたま掲示板でめっけた「再帰を使って素数を探す」
#include <iostream>
// nより大きな最小の素数を求める
int nextprime(int n) {
while ( true ) {
int i = 2; // 最小の素数は2
++n;
// 素数i が√nを超えず、かつnを割れない間
while ( i*i <= n && n % i != 0 ) {
i = nextprime(i);
}
// nを割れる素数がないのならnは素数
if ( i*i > n ) { return n; }
}
}
int main() {
std::cout << nextprime(10000000) << std::endl;
}
効率はともかく、なかなか巧妙なやり方ですな。
nextprime(n)の再帰の深さはnが一億でも高々5段かそこら。