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

質問

以下のようなプログラムを作ってみたのですが、計算結果を出すのに大体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 · ベストアンサー

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

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

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

回答No.9

επιστημη（@episteme）

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

お礼

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

回答No.8

επιστημη（@episteme）

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

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

回答No.7

επιστημη（@episteme）

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

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

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

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

回答No.6

Tacosan

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

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

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

回答No.5

επιστημη（@episteme）

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

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

回答No.4

noname#30727

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

回答No.3

επιστημη（@episteme）

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

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

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

補足

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

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

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

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

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

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

回答No.2

water-cooled

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