数十万番目の素数を表示させるプログラム

以下のようなプログラムを作ってみたのですが、計算結果を出すのに大体10分くらいかかってしまいます。自分の知識の範囲でできる限りの工夫はしてみたのですが、10分はちょっと長すぎなのでもう少し短縮できる方法をどなたか教えてください。よろしくお願いします。

#include <stdio.h>
#include <math.h>
#include <time.h>

int main(void)
{
int gakuseki,n,no,i,prime,j;
time_t t1,t2;

printf("学籍番号を入力して下さい。\n");
scanf("%d",&gakuseki);

time(&t1);

n=gakuseki%100000+900000;

printf("%d番目の素数を計算中...\n",n);

no=1;

if(n==1){
i=2;
}else{
i=1;
while(no<n){
prime=1;
i+=2;
for(j=3;j<=sqrt(i);j+=2){
if(i%j==0){
prime=0;
break;
}
}
if(prime==1) no+=1;
}
}
time(&t2);

printf("%d番目の素数は%dです。\n",no,i);
printf("計算時間は%ld秒でした。\n",t2-t1);
return 0;
}

No.1 ベストアンサー 回答者： txrx 回答日時： 2004/10/07 16:25

sqrtに時間がかかりますので、

for(j=3;j<=sqrt(i);j+=2){
　　　↓
for(j=3;j*j<=i;j+=2){

のようにするとかなり早くなりそうな気がします。

No.9 回答者： episteme 回答日時： 2004/10/08 05:19

大きな領域が欲しければ malloc/free を使います。

この回答へのお礼

ありがとうございました！malloc/freeについていろいろ調べてやってみると相当速くなりました。100万番目の素数で大体8秒くらいです。本当嬉しいです！感謝しています。

お礼日時：2004/10/08 14:01

No.8 回答者： episteme 回答日時： 2004/10/07 18:07

> もすこし簡単なやつなら 2n+1 改め 4n-1, 4n+1 を素数の候補に。

ごめんなさい。マチガイ。
正解は 6n-1, 6n+1 です。

No.7 回答者： episteme 回答日時： 2004/10/07 17:54

> ちなみに資料によると1,000,000番目の素数は 15,485,863 です＞#3.

あれ? 一個ズレたかも ^^;

> あと, (2, 3, 5 以外の) 素数を 30 で割ったときの余りが 8通りしかないことを使うともうちょっと速くはなります.

もすこし簡単なやつなら 2n+1 改め 4n-1, 4n+1 を素数の候補に。

No.6 回答者： Tacosan 回答日時： 2004/10/07 17:41

100,711,433 より小さな素数 (580万個) の表は既にありますね.

ちなみに資料によると1,000,000番目の素数は 15,485,863 です＞#3.
手元の計算機では 18.6秒くらいでした.

あと, (2, 3, 5 以外の) 素数を 30 で割ったときの余りが 8通りしかないことを使うともうちょっと速くはなります.

No.5 回答者： episteme 回答日時： 2004/10/07 17:35

> 90万番目以降の素数だから、90万番目の素数を予め計算しておく。

100万以下ならば 1000までの素数表があれば十分。

No.4 回答者： noname#30727 回答日時： 2004/10/07 17:20

90万番目以降の素数だから、90万番目の素数を予め計算しておく。

No.3 回答者： episteme 回答日時： 2004/10/07 17:13

> 見つけた素数を覚えておくという手はどうでしょう。

これでやってみた。
見つけた素数の中に割り切るものがなければそれは素数。

百万番目は 15476729 (僕の環境で20秒)

この回答への補足

素数を記憶させるということですが、配列を使うんですよね？

僕もそれで試そうとしてみたのですが、配列が５０万個ぐらいまでしか定義できませんでした。

それ以下なら定義できて計算時間も大幅に短縮されたのですが、僕が欲しいのは９０万番目あたりの素数なので配列もそれくらい必要ですよね。恐らく。

なので、もし良かったらどうやればそれくらい定義できるか教えていただけませんか？

もしくは他の方法があれば教えてもらえると嬉しいです。

よろしくお願いいたします。

補足日時：2004/10/08 02:13

No.2 回答者： water-cooled 回答日時： 2004/10/07 16:28

速くなるかどうか不明ですが、見つけた素数を覚えておくという手はどうでしょう。