- ベストアンサー
超初心者です。HowTo本"独習C"の内容について
Cを勉強し始めてまだ3日なのですが、 参考書の内容でどうしても理解できない箇所があります。 周りに聞ける人がいないのでここでみなさんにお聞きしてみました。 以下、2つのプログラムでわからない場所があります。 /* 2から1000までの素数を求める */ #include <stdio.h> int main(void) { int i,j,prime; for(i=2;i<1000;i++){ prime=1; for(j=2;j<=i/2;j++) if(!(i%j)) prime=0; if(prime) printf("%dは素数です\n",i); } return 0; } iをjで割ったときに余りが0でなければ素数だということはわかるのですが、 for(j=2;j<=i/2;j++) この行の意味が分かりません。 これはiが2から1000までインクリメントされる間になにをしているのでしょうか？ 条件判定部 j<=i/2 はどういった解釈をしたらよいのか分かりません。 あと、本当に基礎的なことなんですがiが2から1000までインクリメントされるのは1回なのですか？ jが2の時にiが1から1000、jが3の時にiが1から1000という意味ではないですよね。 あくまでiが2から1000までインクリメントされるループは1回限りで、その中でjの式が実行されるということですよね。
- hisa_a10
- お礼率100% (8/8)
- C・C++・C#
- 回答数3
- ありがとう数3
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
＞for(j=2;j<=i/2;j++) ＞ ＞この行の意味が分かりません。 素数を求めたいんですよね？ i=500の時を考えて見ましょう。 j<=250になりますね？ではj=251のときどうなるでしょうか？ 500%251を計算します。でも、250より大きい数で割っても当然割り切れることはないですよね？ ここまで説明すればわかりますでしょうか。 つまり、j<=i/2は素数になりうる数だけを取り出そうとしています。 ＞iが2から1000までインクリメントされるのは1回なのですか？ iを使ったforループが１回しか出てないからそうですね。 ＞jが2の時にiが1から1000、jが3の時にiが1から1000という意味ではないですよね。 そのようにするためには for(j=2;j<1000;j++) { for(i=2;i<=1000;i++){} } のようにしなければいけません。 ＞あくまでiが2から1000までインクリメントされるループは1回限りで、その中でjの式が実行されるということですよね。 そうです。
その他の回答 (2)
- a-saitoh
- ベストアンサー率30% (524/1722)
for(j=2;j<=i/2;j++) if(!(i%j)){ prime=0;break;} としたいところですが．． iが素数でないとしたら，その素因数のうち最小のものは√i 以下です． そこで，２～int(sqrt(i))までの数でiを割ってどれも割り切れ化ければ素数です．が，浮動小数点演算を避けるために，(無駄ですが)i/2にしているのでしょう．
お礼
回答していただいてありがとうございます。 >２～int(sqrt(i))までの数でiを割ってどれも割り切れなければ素数です この説明ですべてが理解できました。 本質的にはそのような形で行われる計算なのですね。 int(sqrt(i))の代わりにi/2を使用しているということですね。 また、機会がありましたらよろしくお願いします。
僕はC言語を読める人間ではないのでアルゴリズムに関することだけ (どーしてもif(!(i%j)) prime=0; if(prime) printf("%dは素数です\n",i);が中括弧でくくられていないと落ち着かないんだけど、あってるのかなあ...知らないけど^^;;) >for(j=2;j<=i/2;j++) なくても動きます。効率が悪いだけで。 iがjで割り切れたら任意の自然数mを用いてi=j*mという形で書けるわけですよね j>i/2ならm>2ならばj*m>iですから、約数になれません。m=1の時、これを満たすjはiそのものしか存在しませんから、i/2<j<iはiの約数にはなりえないんです。 >あくまでiが2から1000までインクリメントされるループは1回限りで、その中でjの式が実行されるということですよね。 そうです。
お礼
回答していただいてありがとうございます。 数学的解釈が苦手、というかまったくわからないのですが（なのにCをやっている？）理解できました。 精進します^^; あと、Cの構文的に for(j=2;j<=i/2;j++) のターゲットが if(!(i%j)) prime=0; のみで、 if(prime) printf("%dは素数です\n",i); は for(i=2;i<1000;i++) のほうのターゲットに含まれているので全体をコードブロック{}で囲む必要はないみたいです（たぶん）。 またお世話になる時があったらそのときはよろしくお願いします。
関連するQ&A
- 独習C 素数テスタ・・・分からない
忙しい中失礼します。 ”素数”を確認するプログラムについて質問があります。 現在独習Cを用いて勉強中なのですが、下記のプログラム理解に苦しんでいます。 宜しければアドバイスを下さい。 下記のプログラム/*素数テスタ*/内から、 質問(1)部：for(; num <=1; )の意味は’１’よりも大きな数字を入れれば、for文のループを抜ける→この考えで合っている、と自分では思っていますが、間違っているのでしょうか? ご指摘願います。 質問(2)部： １．num=5の場合、for ( i=2; i <= num / 2; i = i+1) → i <= num / 2はi <= 2となる。→i <= 2となり、for文のループを抜ける。→ if ((num % i) == 0) の条件は成り立たない。→ is_prime = 1のため、"素数です"と表示される。→納得！ ２．num=9の場合、for ( i=2; i <= num / 2; i = i+1)→ i <= num / 2は i(=2) <= 4となり、 i = i+1の’i’部が’4’となった後for文のループを抜ける。→if ((num % i) == 0)はnum % iは 9%4で’1’余り、となり、if ((num % i) == 0) の条件は成り立たない。→is_prime == 1 の状態がキープされる。→"素数です"と表示される、と思いきや"素数ではありません"と表示される。 で、ここで何故"素数ではありません"と表示されるのかが分かりません。頭の中では’９’が素数ではないのは分かりますが、プログラムの中でどういう経路を辿り、"素数ではありません"と表示されるのでしょうか。その過程の説明を欲しています。 宜しければ、アドバイスを下さい。 /*素数テスタ*/ #include <stdio.h> int main(void) { int num = 0, i, is_prime; for(; num <=1; ){ //質問(1) printf("判定したい数を入力して下さい: "); scanf("%d", &num); } /*約数があるかどうかを調べる*/ is_prime = 1; for ( i=2; i <= num / 2; i = i+1) //質問(2) if ((num % i) == 0) //質問(2) is_prime = 0; //質問(2) if (is_prime == 1 ) printf("素数です"); else printf("素数ではありません"); 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#
- Cプログラミング
素数を判定するプログラミングの作成で以下のプログラミングを作成したのですが、すべて 素数でないとでてしまいます。どなたか間違いをおしえていただけませんでしょうか。 #include<stdio.h> int main(void) { int num,i; printf("Please input a number:"); scanf("%d",&num); for (i=2; i < num ; i++){num % i; if (num % i == 0) break; } if (num % i == 0) printf("%d is not prime. \n" ,num); else printf("%d is prime. \n" ,num); return 0; }
- ベストアンサー
- C・C++・C#
- C言語 素数の和
任意の数から任意の数までの素数の和算出するプログラムが大体できましたがうまく動きません。どこを追加・削除すればいいのでしょうか？ 実行例1 数1:10 数2:2 素数の和:17 実行例2: 数1:900 数2:1000 素数の和:13330 参考 2+3+5+7=17 907+911+919+929+937+941+947+953+967+971+977+983+991+997=13330 任意の数から任意の数までの素数の和算出するプログラムがどうしても分かりません。どう作成すればいいのでしょうか？ 実行例1 数1:10 数2:2 素数の和:17 実行例2: 数1:900 数2:1000 素数の和:13330 参考 2+3+5+7=17 907+911+919+929+937+941+947+953+967+971+977+983+991+997=13330 #include <stdio.h> #include <math.h> int main(void) { int i, j, k, tmp; int number1, number2, total; printf("数1:"); scanf("%d", &number1); printf("数2:"); scanf("%d", &number2); total = 0; if (number1 > number2) { tmp = number1; number1 = number2; number2 = tmp; } if (number1 == 2) { number1++; total = 2; } if (number1 % 2 == 0) { number1++; } for (i=number1; i<=number2; i+=2) { k=0; for (j=3; j<=sqrt(i); j+=2) { if (i%j==0) { k=1; break; } } if (k==0) { total += i; } } printf("素数の和:%d\n", total); return 0;
- ベストアンサー
- C・C++・C#
- 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言語の質問です
下記の素数か素数でないか調べるコードで、 (1)変数名にis_primeとありますが、isは何を意味しているのですか？ (2)is_prime = 1;とするのがわかりません。 (3)以下、return 0; まで、どういう流れかわかりません よろしければコメント以下から１行ずつ教えてもらえるとうれしいです。 #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 && num > 1) printf("素数です"); else if (num > 1) printf("素数ではありません"); return 0; }
- ベストアンサー
- C・C++・C#
- 素数であるかを判断するプログラムについて
Ｃ言語を学習していて「独習Ｃ」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となり、素数でない
- ベストアンサー
- C・C++・C#
- C言語の問題を教えてください。初心者です。
1000以下の整数を入力して、それ以下の素数を出力するプログラムをつくっています。 一応自分でやってみたのですが、どうもうまくできません。自分ではどこが間違っているのかさっぱりなので間違い箇所を指摘し、どうすれば良いのかを教えていただきたいです。ほかに効率的なやりかたがあったらあわせてお願いします。 初心者なので易しく説明していただけるとありがたいです。 ＜自分でやってみた＞ #include <stdio.h> int main(){ int i,j,N; int a[1000]; for (i=2; i<=1000; i++) { a[i]=1; } for (i=2; i<=1000; i++) { for (j=i++; j<=1000; j++) { if (a[j]=1 && j%i==0) { a[j]=0; } } } printf("2以上1000以下の整数を入力してください\n"); scanf("%d",&N); printf("%d以下の素数は\n",N); for (i=2; i<=N; i++) { if (a[i]=1) { printf("%d\n",i); } } } よろしくお願いしますm(_ _)m
- ベストアンサー
- C・C++・C#
- Ｃ言語の問題
以下はＣ言語の問題です。お教えください。 1000以下の素数を求めるプログラム prog.c を作成せよ。各素数を整数4桁で出力し、15個の素数を出力した時点で改行処理 を行うこと。作成したプログラムを提出せよ。 です。 僕の考えでは、 #include <stdio.h> #include <math.h> main(){ int i; int j; int ix; int k; printf("正の整数を入力して下さい: "); scanf("%d",&i); ix=(int)(sqrt((double)i)); k=0; for(j=2;j<=ix;j++) { if(i%j==0) { k=1; } } if(k==0) { printf("%d は素数です\n",i); } else { printf("%d は素数ではありません\n",i); } となると思うのですが。どうやら違うようです。全然わからないので、正しい答えを教えてください。
- ベストアンサー
- その他（プログラミング・開発）
お礼
丁重な解説をしていただいてありがとうございます。 最初は回答していただいた内容を呼んでも理解できなかったのですが、ようやく分かりました！ つまりiを2で割った数よりもjが大きい場合は割り切れる数字がないので計算する意味がない、だから最初からj<=i/2以上の値は除外しているというわけですね。 ループの構成についても理解することができました。 これで次に進むことができそうです。 ありがとうございます。