「プロジェクトオイラー解説問7」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー解説問7 - (2014/01/09 (木) 16:17:28) のソース

*Problem 7 「10001番目の素数」 †
素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 である.
10001 番目の素数を求めよ.

解法
http://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9
Wikiにあるエラトステネスの篩を使います。
エラトステネスの篩とは素数リストを得るための効率的な方法です。
素数の判定は非常に奥が深く難しい理論がたくさんありますが。
一般向けではこの篩と試し割がわかれば大体大丈夫です。
言語によっては素数判定メソッドが使えるものもありますのでそれを使うのも手です。


篩の具体的な実装については
http://blog.livedoor.jp/add20/archives/1059267.html
を参考にしてください。
リンク先のprimeをそのまま使用します。

自然数1～ｎまでの間に素数は大体ｎ*1/10個ありますので。
安全マージンを取って20万個の配列を用意します。

そして配列に対してエラトステネスの篩を適用します。
あとはi=２から初めて 
prime[i]=1なら素数が一個あったとカウントしていき。
10001番目の素数が見つかったらその数を答えとします。
篩適用後のコードのイメージは以下の通りとなります。

 int count=0;
 int i;
 for(i=2;i<200000;i++){
      if(prime[i]==1)count++;
      if(count==10001)break;
 }
 printf("ans=%d",i);