- ベストアンサー
for文の条件式について
#include<stdio.h> #define N 30 #define TRUE 1 #define FALSE 0 char is_prime[N+1]; int main(void) { for(i=1;i<=N;i++){ is_prime[i]=TRUE; } is_prime[1]=FALSE for(i=2;i*i<=N;i++）→(1) if(is_prime[i]) for(j=i*2;j<=N;j+=i)→(2) is_prime[j]=FALSE;→(3) printf("%dまでの素数は、\n",N); for(i=1;i<=N;i++) if(is_prime[i]) printf("%d",i); return 0; これはエラトステネスの素数を求めるプログラムですが、(1)のi*iは2 3 5と理解できるんですが（２）の条件式が理解できません。 例えはi=2のときｊは4になるのですが、(3)は is_prime[4]=FALSEとなりｊ+=iは6になりますが、何ゆえこれが増分として出てくるのか理解できません。 ｊ+=iはどういう使われ方をするのか理解できません。どなたかご教授ねがいます。
- PHYOPHYO
- お礼率20% (33/158)
- C・C++・C#
- 回答数4
- ありがとう数1
- みんなの回答 （4）
- 専門家の回答
質問者が選んだベストアンサー
・ 最初、全ての数を素数に設定して、約平方根までチェックし、 素数でないもの除いていきます。 ・ それぞれのiについての処理は、その倍数は素数にはなれませんのですべてFALSEに決定します。そのときの、iの倍数を順に求めるのが j+=i です。つまり for(j=i*2;j<=N;j+=i) で、自分を除くすべてのiの倍数を処理しているわけです。 なお、その前の if(is_prime[i]) は、既にiにFALSEがあるということは、その倍数についてもFALSEとして処理されている事が保障されていますから、無駄なチェックを省いているわけですね。
その他の回答 (3)
- masa6272
- ベストアンサー率66% (93/140)
エラトステネスの篩(ふるい)は、一定の数までの素数を効率よく求める方法の1つです。まず、プログラム云々より、この仕組みを理解してください。 そうすれば、どうしてこんなプログラムになるか分かるはずです。
- xkuonx
- ベストアンサー率41% (23/56)
j+=iはj=j+iと同じ意味です。 また、for文の第一引数(この場合j=i*2)が実行されるのは for文のループが始まる最初だけです。
- koko_u_
- ベストアンサー率18% (459/2509)
j には i の倍数が順々に格納されるので、 何かの数の倍数になっていれば素数ではないということだと思います。
関連する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)の中身のアルゴリズムがどういう仕組みになっているのかお分かりになりますでしょうか？
- ベストアンサー
- C・C++・C#
- プログラミングCの質問です
現在10×10の市松模様を表示させるというプログラムを作成しています。 #define文、IF文、for文の使用、printfを使って■と□を表示させることが条件です。 間違っているところの指摘をお願いします。 #include <stdio.h> #define N 10 int main(void) { for( i=1 ; i<=N ; ++i ) { for( j=1 ; j<=N ; ++j ) ｝ if( (i+j) % 2 ){ printf("■"); }else printf("□"); } printf("\n"); i++; } return 0; }
- 締切済み
- C・C++・C#
- プログラミング for文
プログラミング for文 プログラミングの問題です。 「自然数nを入力し、以下のようなパターンが出力されるようなプログラムをfor文を使って作成せよ。」 (例:n=3のとき) % ./a.out n: 3 * ** *** *__* **_** ****** *__*__* **_**_** ********* (例:n=4のとき) % ./a.out n: 4 * ** *** **** *___* **__** ***_*** ******** *___*___* **__**__** ***_***_*** ************ *___*___*___* **__**__**__** ***_***_***_*** **************** (_で空白を表しましたが、上手く見られないかもしれません…。小さい直角三角形が下に行くにつれ1個ずつ増え、全体的にみると大きい直角三角形が見えるイメージです。) つまり、n=3なら、 * ** *** を単位として、1~3行目にはこれが1つ、4~6行目にはこれが2つ、7~9行目にはこれが3つあります。 一般に、 * ** *** … ********(←n個) を単位とし、n^2-2~n^2行目にこれがn個あるようなパターンです。 私はまず、単位パターンをプログラムしました。 #include <stdio.h> main() { ___int n, i, j; ___printf("n: "); ___scanf("%d", &n); ___for (i=1; i<=n; i++) { ______for (j=1; j<=i; j++) { _________printf("*"); ______} ______printf("\n"); ___} } (_は空白です) しかし、単位パターンを横に2個、3個と並べるプログラムが分かりません。 さらにfor文を使い、3重、4重にするのですか？どなたか教えてください。
- ベストアンサー
- その他（プログラミング・開発）
- １００未満の素数出力の最後
１００未満の素数出力の最後 #include<stdio.h> int main() { int i,j,prime[100]; int N=100; for(i=0;i<N;i++){ prime[i]=1; }//全ての要素を素数の候補とする prime[0]=prime[1]=0; //０と１は素数ではない printf("2の倍数："); for(i=2;i*2<100;i++){ printf("%d ",i*2); prime[i];//←prime[i]に2の倍数を入れてるつもりです。 } prime[i]=0;//それを0にしてるつもりです。 printf("\n3の倍数："); for(i=2;i*3<100;i++){ printf("%d ",i*3); prime[i];//同じく } prime[i]=0;//同じく printf("\n5の倍数："); for(i=2;i*5<100;i++){ printf("%d ",i*5); prime[i];//同じく } prime[i]=0;//同じく printf("\n7の倍数："); for(i=2;i*7<100;i++){ printf("%d ",i*7); prime[i];//同じく } prime[i]=0;//同じく printf("\n100未満の素数を出力\n"); for (i=0;i<N;i++){ printf("%d ",prime[i]!=0);//←prime[i]=0じゃないのを出力してるつもりなんですがうまく表示されません } return 0; } どうしたらいいでしょうか？ 自分なりに考えても０か１しか表示されません；
- ベストアンサー
- C・C++・C#
- 掃出法で連立一次方程式の解を求める
掃出法で連立一次方程式の解を求めるプログラムを作ってみたのですが、ポインタと浮動小数点のエラーが出てしまい、実行できません。どこが間違っているのかさえ分からず困っています。訂正箇所を教えてください。宜しくお願い致します。 #include<stdio.h> #include<math.h> #include <float.h> #define N 3 #define EPSILON 1.0E-5 #define TRUE 1 #define FALSE 0 void sweep(int *flag); void swap(float *wk1,float *wk2); float a[N][N]={{ 2, 6, 3}, {-1, 5,-2}, {-2,-1, 6}}; float x[N],b[N]={6,3,14}; int flag; void main() { int i,j; for(i=0;i<N;i++) { for(j=0;j<N;j++) printf("%10.4f",a[i][j]); printf("%10.4f\n",b[i]); } flag=TRUE; sweep(&flag); if(flag==TRUE) { printf("連立方程式の解\n"); for(i=0;i=N;i++) printf("x[%d]=%10.4f\n",i+1,x[i]); } else printf("解なし\n"); } void swap(float *wk1,float *wk2) { float w; w=*wk1; *wk1=*wk2; *wk2=w; } void sweep(int *flag) { int i,j,k,ik; float ak,aik; for(k=0;k<N;k++) { ak=a[k][k]; if(fabs(ak)<=EPSILON) { ik=k+1; while((ik<N)&&(fabs(a[ik][k])<EPSILON)) ik++; if(ik<N) { for(j=k;j<N;j++) swap(&a[k][j],&a[ik][j]); swap(b[k],b[ik]); ak=a[k][k]; } else { printf("ピボットが零です\n"); *flag=FALSE; goto end; } } for(j=k;j<N;j++) a[k][j]=a[k][j]/ak; b[k]=b[k]/ak; for(i=0;i<N;i++) { if(i!=k) { aik=a[i][k]; for(j=k;j<N;j++) a[k][j]=a[i][j]-aik*a[k][j]; b[i]=b[i]-aik*b[k]; } } for(k=0;k<N;k++) x[k]=b[k]; end:; } }
- 締切済み
- C・C++・C#
- エラーがどこかわからない
#include<stdio.h> #include<math.h> #define NUM 100000 int main(void){ int prime[NUM+1],i,j,Limit; for(i=2;i<=NUM;i++){ prime[i]=1; } Limit=(int)sqrt(NUM); for(i=2;i<=Limit;i++){ if(prime[i]==1){ for(j=2*i;j<=NUM;j+=i){ prime[j]=0; } } } for ( i=2;i<=NUM;i++) { if (prime[i]){ printf("%d\n",i); } } } これは100000未満の素数の総数を求めるプログラムなんですが、実行したらエラーが出てくるんです。何度も確認しても正しいはずなんですがエラー出てきて困っています。どこが間違っているでしょうか？
- 締切済み
- C・C++・C#
- c言語でのダイクストラ法の実装
大学の課題で、c言語におけるダイクストラ法について以下のようなものが出たのですが出力のためにどのようなコードを書けばいいかわかりません。どなたかコードや実装方法を教えていただけないでしょうか。 （入力例） 7 -1 7 3 6 -1 -1 4 7 -1 5 -1 6 -1 -1 3 5 -1 4 1 3 5 6 -1 4 -1 -1 -1 7 -1 6 1 -1 -1 2 -1 -1 -1 3 -1 2 -1 9 4 -1 5 7 -1 9 -1 1 １行目は頂点の数、２行目以降の各行は隣接行列の各要素を空白区切りで表し、最後の行の数はスタートの頂点の番号 [出力] 1. スタートとして選択した頂点から各頂点への最短経路とコストを以下の形式で 出力する．ここで s はスタートの頂点， g はゴールの頂点， c は合計のコス トを表す．また s ... g は最短経路の各頂点を空白区切りとして表す． s-->g : c ( s ... g ) 以下は上記の入力例の場合の出力例 Input>1 <-- スタートとして選択した頂点番号 1-->0 : 7 ( 1 0 ) 1-->1 : 0 ( 1 ) 1-->2 : 5 ( 1 2 ) 1-->3 : 9 ( 1 2 3 ) 1-->4 : 6 ( 1 4 ) 1-->5 : 8 ( 1 2 5 ) 1-->6 : 10 ( 1 2 6 ) ↓自分の書いたコード #include <stdio.h>#include <limits.h>#define FALSE 0 #define TRUE (!FALSE) #define INFINITY INT_MAX #define MAXSIZE 100 int dijkstr(int number_of_vertex, int weight[][MAXSIZE], int start_vertex){ int is_in_mst[MAXSIZE], d[MAXSIZE]; int i, j, number_of_edges, min_d, v; printf("Input>%d\n", start_vertex); for (i = 0; i <number_of_vertex; i++) is_in_mst[i] = FALSE; for (i = 0; i <number_of_vertex; i++) d[i] = INFINITY; d[start_vertex] = 0; for(number_of_edges = 0; number_of_edges<(number_of_vertex-1); number_of_edges++) { min_d = INFINITY; v = INFINITY; for (i = 0; i <number_of_vertex; i++) { if(is_in_mst[i] == FALSE &&d[i] <min_d) { min_d = d[i]; v = i;}} if(v != INFINITY) is_in_mst[v] = TRUE; for (i = 0; i <number_of_vertex; i++) { if(is_in_mst[i] == FALSE &&weight[i][v] != INFINITY &&(weight[i][v] + d[v]) <d[i]) d[i] = weight[i][v] + d[v];}}} int main(void){ int weight[MAXSIZE][MAXSIZE]; int i, j, data, n, start; printf("Input data size>"); scanf("%d", &n); printf("%d\n", n); for (i = 0; i <n; i++) { for(j = 0; j <n; j++) { printf("Input data>"); scanf("%d", &data); printf("%d\n", data); weight[j][i] = data; if(weight[j][i] == -1) weight[j][i] = INFINITY;}} printf("\n"); printf("Input start vertex>"); scanf("%d", &start); return 0;}
- 締切済み
- C・C++・C#
- 数十万番目の素数を表示させるプログラム
以下のようなプログラムを作ってみたのですが、計算結果を出すのに大体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; }
- ベストアンサー
- C・C++・C#
- if文について
ソートのプログラムにおいて昇順・降順を選択して表示させるプログラムを書いてるのですが 下記のように記述するとエラーが出てしまいます。 よく調べたのですがエラー表示もよくわからないものなのでした。 どのようにすればうまく動くようになるのでしょうか？ #include <stdio.h> #define swap(type, x, y) do {type t = x; x = y; y = t; } while (0) void bubble(int a[], int n) { int i, j; for (i = 0; i < n - 1; i++) { for (j = n - 1; j > i; j--) if (a[j - 1] > a[j]) swap(int, a[j - 1], a[j]); } } void bubble2(int a[], int n) { int i, j; for (i = 0; i < n - 1; i++) { for (j = n - 1; j > i; j--) if (a[j - 1] < a[j]) swap(int, a[j - 1], a[j]); } } int main(void) { int i; int x[7]; int nx = sizeof(x) / sizeof(x[0]); int select; printf("%d個の整数を入力せよ。\n", nx); for (i = 0; i < nx; i++) { printf("x[%d] : ", i); scanf("%d", &x[i]); } printf("昇順ですか降順ですか？ 0:昇順／1:降順 ＞"); scanf("%d",&select); if (select == 0) bubble(x, nx); puts("昇順にソートしました。"); for (i = 0; i < nx; i++) printf("x[%d] = %d\n", i, x[i]); else bubble2(x, nx); puts("降順にソートしました。"); for (i = 0; i < nx; i++) printf("x[%d] = %d\n", i, x[i]); return (0); }
- 締切済み
- C・C++・C#
- 100000未満素数の総数を求めるのに困っているので教えてください。
100000未満素数の総数を求めるのに困っているので教えてください。 #include<stdio.h> #include<math.h> #define NUM 100000 int main(void){ int prime[NUM+1],i,j,Limit; for(i=2;i<=NUM;i++){ prime[i]=1; } Limit=(int)sqrt(NUM); for(i=2;i<=Limit;i++){ if(prime[i]==1){ for(j=2*i;j<=NUM;j+=i){ prime[j]=0; } } } for ( i=2;i<=NUM;i++) { if (prime[i]) { printf("%d\n",i); } } } これなんですが、実行したらエラーが出てしまうんですがなぜでしょうか？
- 締切済み
- C・C++・C#
お礼
for(j*2;j<=N;j+=i)の条件式がiの倍数を処理している事が良く分かり、納得しました。有難うございました。