Problem 7 「10001番目の素数」 †
素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 である.
10001 番目の素数を求めよ.
自然数1~nまでの間に素数は大体n*1/10個ありますので。
安全マージンを取って20万個の配列を用意します。
そして配列に対してエラトステネスの篩を適用します。
あとはi=2から初めて
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);
最終更新:2014年01月09日 16:17