- ベストアンサー
数十万番目の素数を表示させるプログラム
以下のようなプログラムを作ってみたのですが、計算結果を出すのに大体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; }
- Keita_since_1983
- お礼率18% (15/80)
- C・C++・C#
- 回答数9
- ありがとう数3
- みんなの回答 （9）
- 専門家の回答
質問者が選んだベストアンサー
その他の回答 (8)
- επιστημη（@episteme）
- ベストアンサー率46% (546/1184)
- επιστημη（@episteme）
- ベストアンサー率46% (546/1184)
- επιστημη（@episteme）
- ベストアンサー率46% (546/1184)
- Tacosan
- ベストアンサー率23% (3656/15482)
- επιστημη（@episteme）
- ベストアンサー率46% (546/1184)
- επιστημη（@episteme）
- ベストアンサー率46% (546/1184)
> 見つけた素数を覚えておくという手はどうでしょう。 これでやってみた。 見つけた素数の中に割り切るものがなければそれは素数。 百万番目は 15476729 (僕の環境で20秒)
補足
素数を記憶させるということですが、配列を使うんですよね？ 僕もそれで試そうとしてみたのですが、配列が５０万個ぐらいまでしか定義できませんでした。 それ以下なら定義できて計算時間も大幅に短縮されたのですが、僕が欲しいのは９０万番目あたりの素数なので配列もそれくらい必要ですよね。恐らく。 なので、もし良かったらどうやればそれくらい定義できるか教えていただけませんか？ もしくは他の方法があれば教えてもらえると嬉しいです。 よろしくお願いいたします。
- water-cooled
- ベストアンサー率14% (76/538)
お礼
ありがとうございました！malloc/freeについていろいろ調べてやってみると相当速くなりました。100万番目の素数で大体8秒くらいです。本当嬉しいです！感謝しています。