• ベストアンサー

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

以下のようなプログラムを作ってみたのですが、計算結果を出すのに大体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; }

質問者が選んだベストアンサー

  • ベストアンサー
  • txrx
  • ベストアンサー率45% (83/184)
回答No.1

sqrtに時間がかかりますので、 for(j=3;j<=sqrt(i);j+=2){ 　　　↓ for(j=3;j*j<=i;j+=2){ のようにするとかなり早くなりそうな気がします。

その他の回答 (8)

回答No.9

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

Keita_since_1983
質問者

お礼

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

回答No.8

> もすこし簡単なやつなら 2n+1 改め 4n-1, 4n+1 を素数の候補に。 ごめんなさい。マチガイ。 正解は 6n-1, 6n+1 です。

回答No.7

> ちなみに資料によると1,000,000番目の素数は 15,485,863 です＞#3. あれ? 一個ズレたかも ^^; > あと, (2, 3, 5 以外の) 素数を 30 で割ったときの余りが 8通りしかないことを使うともうちょっと速くはなります. もすこし簡単なやつなら 2n+1 改め 4n-1, 4n+1 を素数の候補に。

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.6

100,711,433 より小さな素数 (580万個) の表は既にありますね. ちなみに資料によると1,000,000番目の素数は 15,485,863 です＞#3. 手元の計算機では 18.6秒くらいでした. あと, (2, 3, 5 以外の) 素数を 30 で割ったときの余りが 8通りしかないことを使うともうちょっと速くはなります.

回答No.5

> 90万番目以降の素数だから、90万番目の素数を予め計算しておく。 100万以下ならば 1000までの素数表があれば十分。

noname#30727
noname#30727
回答No.4

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

回答No.3

> 見つけた素数を覚えておくという手はどうでしょう。 これでやってみた。 見つけた素数の中に割り切るものがなければそれは素数。 百万番目は 15476729 (僕の環境で20秒)

Keita_since_1983
質問者

補足

素数を記憶させるということですが、配列を使うんですよね？ 僕もそれで試そうとしてみたのですが、配列が５０万個ぐらいまでしか定義できませんでした。 それ以下なら定義できて計算時間も大幅に短縮されたのですが、僕が欲しいのは９０万番目あたりの素数なので配列もそれくらい必要ですよね。恐らく。 なので、もし良かったらどうやればそれくらい定義できるか教えていただけませんか？ もしくは他の方法があれば教えてもらえると嬉しいです。 よろしくお願いいたします。

回答No.2

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

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. C・C++・C#

関連するQ&A

  • C言語＜素数を求めるプログラム＞

    #include<stdio.h> int j; int prime(int n) { int i; if(n < 2) return 0; if(n == 2) return 1; if(n%2 == 0) return 0; for(i = 3; i*i<= n; i += 2){ if(n%i == 0) return 0; } return 1; } int main(void) { int n; for(n=1; n <= 1000; n++) { if(prime(n)){ printf("%d\n",n); j++; } } printf("素数の個数は全部で %d 件見つかりました。\n",j); return 0; } このプログラムは1から1000までの素数のみを表示させるプログラムでありますが、このアルゴリズムが全くわかりません。 int prime(int n)の中身のアルゴリズムがどういう仕組みになっているのかお分かりになりますでしょうか？

  • プログラム

    下のようなプログラムを作ったのですが、10進2進変換をj=n>>2&1の部分にあるようなビットシフトではなく、 for(i=1;i<8;i++){printf("bit[%d]=%d\n",i,n%2);n=n/2;}に変えて剰余計算で行うプログラムにしたいのですが、分かる方がいましたら教えて下さい。お願いします。 #include <stdio.h> int main(void) { int i,j,n; i=2; printf("数字を入力="); scanf("%d",&n); printf("Dec=%d\n",n); printf("heX=0x%x\n",n); j=n>>2&1; printf("bit[%d]=%d\n",i,j); return(0); }

  • プログラムを組んだのにエラーが出る！！！

    #include <stdio.h> #include <stdlib.h> #include <math.h> int main(void) { int i, j; int m, flag, count; FILE *fp; if (NULL == (fp = fopen("prime.txt", "w"))) { printf("Cannot open output file\n"); exit(1); } count = 0; for (i = 2; i < 1000; i++) { m =sqrt(i); flag = 1; for (j = 2; j <= m; j++) { if (i % j == 0) { flag = 0; break; } count++; } if (flag) { printf("%4d ", i); fprintf(fp," %4d", i); } } printf("\n乗除回数:%d\n", count); fprintf(fp,"\n乗除回数 %d\n", count); fclose(fp); return 0; } （通常課題2-3 1000以下の正の整数値のうち，素数をすべて計算し，結果をファイルに格納するプログラムを作れ． ．また、計算の実行の中で乗除を行った回数もあわせて表示し、ファイルに格納すること 実行結果 2 3 5 7 11 13 17 … 991 997 乗除回数：78022 どこが間違ってるのか指摘してください お願いします！

  • 配列の要素数に変数を入れたい

    配列に数の入力履歴を入れて最後にその数を出力したいのですが、変数を入れることはできないと勉強した記憶がありまさにその通りコンパイルエラーが出ました。 他に何か方法はありませんでしょうか。 /* 課題1-3 */ #include <time.h> #include <stdio.h> #include <stdlib.h> #include <math.h> int main(void) { int i; int no1; /* 範囲1 */ int no2; /* 範囲2 */ int max; /* 大きい乱数 */ int min; /* 小さい乱数 */ int y; /* 当てさせる数 */ int stage; /* 入力回数 */ int x; /* 読み込んだ値 */ int n; /* 入力制限 */ srand(time(NULL)); no1 = rand(); no2 = rand(); if(no1 > no2){ max = no1; min = no2; } else{ max = no2; min = no1; } y = min + rand() % (max-min); n = ceil(log(max-min)/log(2)); int a[n]; /*←配列の要素数をn個にしたい*/ printf("%d以上%d以下の整数を当ててください。\n", min, max); stage = 0; do{ printf("残り%d回。いくつでしょう：\n", n - stage); scanf("%d", &x); a[stage++] = x; if(y > x) printf("小さいです。\n"); else if(y < x) printf("大きいです。\n"); }while(y != x && stage < n); if(y != x) printf("残念でした。正解は%dです。", y); else printf("正解です。%d回目で正解しました。", stage); puts("\n---入力履歴---"); for(i=0; i<stage; i++) printf("%2d : %4d %+4d\n", i+1, a[i], a[i] - y); return (0); }

  • 位数を求めるプログラム

    a^e≡1(mod n)を満たす最小の正の整数eを 法nに関するaの位数です。 これを法３１における１、２,...、３０の位数を求めるプログラムを以下のように作ったのですが 位数は３１が素数なので３０の約数であるはずなのですが１１とか１２などが出てきてしまいます。 問題のある箇所を教えてください。 #include <stdio.h> int main(void) { int h,i,j,k,n; //法３１ n=31; //1の位数は１ printf("1:1\n"); for(j=2;j<n;j++){ k=1; for(i=1;i<=(n-1)/2;i++){ //j^iを求める。 k=j*k; for(h=2;h*n<k;h++); //余りが１になるものを位数とする。 if(!((k-1)%((h-1)*n))){ printf("%d:%d\n",j,i); break; } } //i<=（n-1）/2までに余りが1あまるものがなければn-1（３０）を位数とする。 if(i>(n-1)/2)printf("%d:%d\n",j,n-1); } return 0; }

  • 素数のプログラムについて教えてください

    3000000以下の素数を降順に表示するプログラムをつくりたいのですが、int mainのところがわかりません。 #include <iostream> int PRIME(int m) int main() { int m, j; for(m = 3000000; m <= 2; m--) } int prime( int n ) { int i; for ( i = 2; i < n; i++ ) { if ( n % i == 0 ) { return 0; } } return 1; } 誰か教えていただけないでしょうか？ よろしくお願いします。

  • ネイピア数（ｅ）のプログラム

    テイラー展開によってネイピア数の近似値を求める プログラミングが全くわかりません。 e = 2.71828 18284 59045 23536 02874 71352 … を計算したいのですが。 #include <stdio.h> #include <math.h> int kaijou(int p) { int cnt; int val=1; for(cnt=1 ; cnt<=p ; cnt++){ val=val*cnt; } return(val); } double napier(int p) { printf("eを計算します。E = (1+(1/k))^k\n"); printf("k=いくつまで計算しますか ?\n"); scanf("%d", &n); double E[n]; E[1] = 1; for (j = 1; j <= n; j++){ E[j] = E[j] + 1; } for (k = 1; k <= n; k++) { K = K + 1; A = 1 / K; // printf("A = %e, ",A); B = 1 + A; // printf("B = %e\n",B); for ( i = 1; i<=k; i++){ E[k] = E[k] * B; // printf("E[%3d]= %e\n",k,E[k]); } void main(void) { int n; int cnt; double answer; printf("計算する最大の項nを入力してください:"); scanf("%d",&n); for(cnt=1 ; cnt<=n ; cnt++){ answer=napier(cnt); printf("第%d項までの近似値:%f 真値:%f 差:%f\n",cnt,answer,exp(1),answer-exp(1)); } }

  • 英語入力するプログラム

    月名の日本語を入力して英語にするプログラムを書こうとしている のですが、うまく動作しません。 たとえば。 「3月：」と表示されたら大文字か小文字、もしくは組み合わせで marchと入力すれば「正解です。」と表示されるようにです。 具体的には、ランダムで月名が表示されていくのですが何を入力しても 正解と表示されてしまいます。 たとえば、marchなのにdなどと入力しても正解になってしまいます。 何がおかしいのでしょうか？ #include<stdio.h> #include<time.h> #include<stdlib.h> #include<ctype.h> #include<string.h> #define swap(type,x,y) do{type t=x;x=y;y=t;}while(0) char *tukistr[]={"January","Feburary","March","April","May","June","July", "August","September","October","November","December"}; int main(void) { char nstr[12]={0,1,2,3,4,5,6,7,8,9,10,11}; char tuki[10]; int num; int seikai=0; int k=0; int seiho[12]; int huseiho[12]; int m=0; int i,j; srand(time(NULL)); printf("月名の英語を入力してください。入力は大文字でも小文字でも構いません。\n"); for(i=11;i>0;i--) { j=rand()%i; swap(int,nstr[j],nstr[i]); } for(i=0;i<12;i++) { printf("%d月 : ",nstr[i]+1); scanf("%s",tuki); do{ for(j=0;j<strlen(tuki);j++) { if(isalpha(tuki[j])!=isalpha(tukistr[nstr[i]][j])) { printf("違います。正解を見ますか？ 0-いいえ/1-はい:"); scanf("%d",&num); if(num==1) { huseiho[m++]=nstr[i]; } break; } } }while(num==0 && j<strlen(tuki)); if(j==strlen(tuki)) { printf("正解です。\n"); seikai++; seiho[k++]=i; } else if(num==1) { printf("%d月は%sです。\n",nstr[i],tukistr[i]); } } printf("12個のうち%d個が正解でした。\n",seikai); printf("正解した月:"); for(j=0;j<12;j++) { if(j==seiho[j]) { printf("%d月,",j+1); } } printf("\n\n"); printf("間違えた月："); for(j=0;j<12;j++) { if(j==huseiho[j]) { printf("%d月,",j+1); } } return 0; }

  • プログラムの説明をお願いします！

    http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1319406053 の回答を参考にして、入力されたnに対するn!を求めるプログラムを作りました。(0<=n<10000) 実行して出力できたのですが、情けない話ですがプログラムがどう動いているのかがさっぱりわかりません。 どなたか解説をお願いします。 #include <stdio.h> int main(void) { int c[10000]; int i, j, t, n; for (i=0; i<9999; i++) { c[i] = 0; } c[9999]=1; scanf("%d", &n); for (i=1; i<=n; i++) { t=0; for (j=9999;j>=0; j--){ c[j] = c[j] * i + t; t = c[j] /10000; c[j] %= 10000; } } for (i=0; i<10000; i++) {　　/* (1) */ if (c[i] > 0) { break; } } printf("%d", c[i++]); for(i=i; i<10000; i++) { printf("%04d", c[i]); /* (2) */ printf("\n"); return 0; } 特に、 (1)ここの繰り返しは何をやっているのでしょうか？ (2)なぜ４ケタ０詰めにするのでしょうか？ よろしくお願いします。

  • 素数であるかを判断するプログラムについて

    Ｃ言語を学習していて「独習Ｃ」48ページの次のプログラムが分かりませんでした。 ～～～～～～～～～～～～～～～～ #include <stdlib.h> #include <stdio.h> int main(void) { int num, i, is_prime; printf("判定したい数を入力してください"); scanf("%d", &num); /*ここからがわかりません*/ is_prime = 1; for(i=2; i<=num/2; i=i+1) if((num%i)==0) is_prime = 0; if(is_prime==1) printf("素数です"); else printf("素数ではありません"); return 0; } ～～～～～～～～～～～～～～～ 私はこうなると考えています。どこが間違っているでしょうか？ numが０のとき、2<=0となり、素数 numが１のとき、2<=0.5となり、素数でない numが２のとき、2<=1となり、素数でない numが３のとき、2<=1.5となり、素数でない

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する