![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?8acaa2e)
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の式が実行されるということですよね。
No.1ベストアンサー
- 回答日時:
>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ループが1回しか出てないからそうですね。
>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の式が実行されるということですよね。
そうです。
丁重な解説をしていただいてありがとうございます。
最初は回答していただいた内容を呼んでも理解できなかったのですが、ようやく分かりました!
つまりiを2で割った数よりもjが大きい場合は割り切れる数字がないので計算する意味がない、だから最初からj<=i/2以上の値は除外しているというわけですね。
ループの構成についても理解することができました。
これで次に進むことができそうです。
ありがとうございます。
No.3
- 回答日時:
for(j=2;j<=i/2;j++)
if(!(i%j)){ prime=0;break;}
としたいところですが..
iが素数でないとしたら,その素因数のうち最小のものは√i 以下です.
そこで,2~int(sqrt(i))までの数でiを割ってどれも割り切れ化ければ素数です.が,浮動小数点演算を避けるために,(無駄ですが)i/2にしているのでしょう.
回答していただいてありがとうございます。
>2~int(sqrt(i))までの数でiを割ってどれも割り切れなければ素数です
この説明ですべてが理解できました。
本質的にはそのような形で行われる計算なのですね。
int(sqrt(i))の代わりにi/2を使用しているということですね。
また、機会がありましたらよろしくお願いします。
![](http://oshiete.xgoo.jp/images/v2/common/profile/M/noimageicon_setting_08.png?8acaa2e)
No.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が見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# C 言語の Gauss Jordan 法について 2 2022/12/28 11:16
- C言語・C++・C# C言語 3 2022/11/09 13:27
- C言語・C++・C# c言語 プログラムのエラー 1 2023/02/11 20:31
- C言語・C++・C# C言語の課題が出たのですが自力でやっても分かりませんでした。 要素数がnであるint型の配列v2の並 3 2022/11/19 17:41
- C言語・C++・C# プログラミング c言語 4 2023/03/07 01:05
- C言語・C++・C# c言語の問題です 3 2023/01/10 16:15
- 大学・短大 C言語線形リストの問題です 3 2022/12/22 00:45
- C言語・C++・C# C言語プログラム変更 2 2022/12/21 15:03
- C言語・C++・C# c言語の問題です 課題1 (二分探索木とセット) 大きさ size の配列 array を考える。す 2 2023/01/10 21:08
- C言語・C++・C# 質問です 下記のコードを分かりやすく解説お願いします 初心者です #include ‹stdio.h 3 2022/05/26 22:03
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
プログラムで関数は使わない方...
-
UWSCにてある一定の動作を無限...
-
PHPの否定文
-
if文の中にfor文なのか、for文...
-
超初心者です。HowTo本"独習C"...
-
break文でループを一気に抜ける...
-
整定時間
-
プログラミングで質問です。言...
-
制御に関するプログラム
-
C言語 a * b / c の計算
-
どうしてもわからないC言語の問題
-
プログラムの解説をお願いします。
-
c言語のリダイレクトによる円...
-
吸湿性のあるものを天秤で秤量...
-
2÷3などの余りについて
-
プログラミング初心者です。 Py...
-
printf で二進表示を行いたい。
-
マイナスからプラスへ転じた時...
-
【C言語教えてください】sin波...
-
O(n log n)について2
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
break文でループを一気に抜ける...
-
入力した文字列から母音だけを...
-
ループを途中で抜けたいのですが。
-
do-while文が禁止される理由
-
入力した数値を倍々するプログラム
-
C言語forループが完結した場合...
-
if文の中にfor文なのか、for文...
-
プログラミングC言語についての...
-
エクセルVBAで Do While (1)って?
-
For文の終了値を関数にしても問...
-
エクセルでC言語のfor文と同じ...
-
Delphiで・・・
-
ループの特定入力終了
-
UWSCにてある一定の動作を無限...
-
C言語、自己参照構造体のプログ...
-
C言語 数字を削除する関数
-
Excel VBAで年度をまたぐ期間の...
-
プログラムで関数は使わない方...
-
Cプログラムが終了しない
-
VBScriptでSQLに接続し、CSV出...
おすすめ情報