![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?e8efa67)
以下のようなプログラムを作ってみたのですが、計算結果を出すのに大体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ベストアンサー
- 回答日時:
sqrtに時間がかかりますので、
for(j=3;j<=sqrt(i);j+=2){
↓
for(j=3;j*j<=i;j+=2){
のようにするとかなり早くなりそうな気がします。
No.7
- 回答日時:
> ちなみに資料によると1,000,000番目の素数は 15,485,863 です>#3.
あれ? 一個ズレたかも ^^;
> あと, (2, 3, 5 以外の) 素数を 30 で割ったときの余りが 8通りしかないことを使うともうちょっと速くはなります.
もすこし簡単なやつなら 2n+1 改め 4n-1, 4n+1 を素数の候補に。
No.6
- 回答日時:
100,711,433 より小さな素数 (580万個) の表は既にありますね.
ちなみに資料によると1,000,000番目の素数は 15,485,863 です>#3.
手元の計算機では 18.6秒くらいでした.
あと, (2, 3, 5 以外の) 素数を 30 で割ったときの余りが 8通りしかないことを使うともうちょっと速くはなります.
No.3
- 回答日時:
> 見つけた素数を覚えておくという手はどうでしょう。
これでやってみた。
見つけた素数の中に割り切るものがなければそれは素数。
百万番目は 15476729 (僕の環境で20秒)
この回答への補足
素数を記憶させるということですが、配列を使うんですよね?
僕もそれで試そうとしてみたのですが、配列が50万個ぐらいまでしか定義できませんでした。
それ以下なら定義できて計算時間も大幅に短縮されたのですが、僕が欲しいのは90万番目あたりの素数なので配列もそれくらい必要ですよね。恐らく。
なので、もし良かったらどうやればそれくらい定義できるか教えていただけませんか?
もしくは他の方法があれば教えてもらえると嬉しいです。
よろしくお願いいたします。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# C言語 プログラミング 4 2022/05/22 11:53
- C言語・C++・C# c言語の問題です 3 2023/01/10 16:15
- C言語・C++・C# プログラミングの授業の課題です 1 2023/01/17 22:15
- C言語・C++・C# バイナリファイルをコピーするのにかかる時間を測りたいのですが実行するとFatel error:gli 2 2022/11/03 01:10
- C言語・C++・C# C言語階乗の総和を求める 2 2023/03/04 23:31
- C言語・C++・C# C言語 3 2022/10/04 15:07
- C言語・C++・C# カードシャッフルのブログラムを使ってc言語でブラックジャックをしたい 2 2022/04/12 15:13
- C言語・C++・C# c言語 プログラムのエラー 1 2023/02/11 20:31
- C言語・C++・C# C言語プログラム変更 2 2022/12/21 15:03
- C言語・C++・C# 10個の実数に対する降順ソート結果を出力するプログラムを作りたいのですが、以下のプログラムをどう直せ 1 2022/07/09 22:16
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
階乗のマクロ
-
VBAで関数をつくる
-
65536は2の何乗なのでしょうか?
-
傾いた四角形内の範囲の条件式
-
EXCELなどで「返す」という表現
-
排他的論理和 BCC(水平パリテ...
-
数値計算の高速化 (cos, sin, exp)
-
引き放し法による除算アルゴリ...
-
matlabで計算終了
-
Excel VBAにてFFT
-
fortranでプログラムをつくった...
-
ReportViewerのテキストボック...
-
関数電卓をc言語でつくりたいの...
-
変化させるセルが変化しない
-
Javaでのある数の小数点乗に...
-
VBでReplace
-
smartyで計算を行う方法
-
VBAの再計算が反映されない件に...
-
数十万番目の素数を表示させる...
-
バッチファイルでウインドウを...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
65536は2の何乗なのでしょうか?
-
変化させるセルが変化しない
-
排他的論理和 BCC(水平パリテ...
-
VBAの再計算が反映されない件に...
-
VBAで関数をつくる
-
バッチファイルでウインドウを...
-
モジュラス103の計算とは何でし...
-
EXCELなどで「返す」という表現
-
数値計算の高速化 (cos, sin, exp)
-
傾いた四角形内の範囲の条件式
-
骨折リスク評価のFRAXについて...
-
matlab計算での進捗状況を知りたい
-
Excel VBAにてFFT
-
C言語についてです。 再帰を使...
-
C言語について 下の画像は do-w...
-
アドオン利率を実質年率に変換
-
エクセルで特定のセルのみを任...
-
電卓でmodの計算
-
引き放し法による除算アルゴリ...
-
y=(x^2 +3x+1)^4を微分の定義を...
おすすめ情報