追伸 「1から順に総当りで求める」というアルゴリズムは除外させて頂きます。
エレガントな回答をお願いします。
まず,素数を列挙して配列とする。
その配列内の,「素数+1番目」の要素を返せばよい。
(終わり)
コメント欄で難しいことを書いてしまってごめんなさい。
こういうことですよね。
[2,3,5,7,11,13,・・・]
という配列の,2+1番目=5, 3+1番目=7,5+1番目=13,・・・
PHPで素数をリスト化しましたが、メモリが足りず2,631,000あたりまでしか走りませんでした。
Array ( [0] => 2 [1] => 3 ・・・ [191953] => 2630951 [191954] => 2630989 )
となりましたので、素数 2,630,951 未満の素数の数は 191,953 で素数。
メモリを増やしてまたやってみます。
あっさり見つかりました。
とはいえ、実質的に「総当たり」なので回答条件を満たしているかどうかは微妙です。
N=2147483579、N未満の素数の数=105097561
求めた手法:
2^31-1以下の素数の逆順リストを用意し、先頭から「その要素以降の要素数が素数になっているか」を調べて最初に見つかったものが答え。
コードはこちら (Gauche Schemeです):
https://gist.github.com/shirok/9d271de7c59292a45a11
Core i7, 16GBのマシンで2分くらいでした。素数のリストを作る時間がほとんどで、探索は一瞬です。
メモリの余裕があまりなかったので、上限が増えるとこの手法ではつらいですね。コメント欄にあるようにπ(x)を厳密に求めるには何らかの形でそれ以下の素数の情報をとっておくのが一番なので、大きい改善は思いつきません。定数倍の改善でしたら、「N以下の素数の数が偶数なら最初から除外できる」ことからリストを1個飛びに保存しておくとか、もう少し工夫してトリビアルな合成数番目の要素は保存しないとかできそうですが。