素数を求めるプログラム

質問

1000以下の素数を求めるプログラムについての問題について考えているのですが、何故2の数のとき、乗除を行う回数が加算されないのかが分かりません。また、3のとき乗除を1回しか行わないのか分かりません。理論的に2が素数となるのは定義付けられているから必要ないのか、とも思ったのですがそれならcounter++で2が範囲にあるのに加算されないという理由がよくわかりません。
初歩的な問題ですみませんが回答頂けると有難いです。
プログラムは下記の通りです。

#include <stdio.h>

int main(void)
{
int i,no;
unsigned long counter = 0;

for (no = 2; no <= 1000; no++) {
for (i = 2; i < no; i++) {
counter++;
if (no % i == 0)
break;
}
if (no == i)
printf("%d\n" , no);
}

printf("乗除を行った回数：%lu\n" , counter);

return (0);
}

回答No.1

asuncion · ベストアンサー

noが2のとき、

＞for (i = 2; i < no; i++) {

このfor文は
for (i = 2; i < 2; i++) {
と同じですね。そうすると、i < 2 の条件を初回から満たしませんので、
このfor文の中身（counter++; など）をスキップします。
counterの値は不変です。

次に、noが3のとき、

＞for (i = 2; i < no; i++) {

このfor文は
for (i = 2; i < 3; i++) {
と同じですね。そうすると、
iは2なので、i < 3 の条件を満たします。counter++; を実行します。
iをインクリメントし、3になります。そうすると、
i < 3 の条件を満たしませんので、for文のループを抜けます。
counterをインクリメントしたのは一度だけです。

お礼

そういった意味なんですね。言われてやっとプログラムの意味が理解できました。ご回答ありがとうございます。

回答No.5

yosiyosi25

#include <stdio.h>
bool flag;
int main(){
for (unsigned int k=2;k<=1000; k++){
flag=1;
for (unsigned int i=2;i*i<=k;i++){
if (k%i==0){
flag=0;
break;
}
}
if (flag==1){
printf("%d\n",k);
}

}
getchar();}
//このコードのほうがましでした。訂正します。しかし更に
//効率のいいコードがあるかもしれません。

回答No.4

yosiyosi25

#include <stdio.h>
#include <math.h>
#include <windows.h>
int flag=0;
int main(){
for (double k=2;; k++){
int square=(int)sqrt(k);
flag=1;

for (int i=2;i<=square;i++){
if ((int)k%i==0){
flag=0;
}
}
if (flag==1){
printf("%d\n",(int)k);
Sleep(100);
}

}
getchar();}

こんなのはどうでしょうか。参考にならなかったらごめんなさい。

回答No.3

goosyu

このソース（ロジック）では剰余回数と素数の数が一致していませんので，素数であってもcounterが加算されません。
　もし素数の数を求める場合は新しくカウンタ用の変数(int sosuCounter = 0;)を定義してから，次のif文内に追加すべきと考えます。
if (no == i) {
printf("%d\n" , no);
sosuCounter++; /* 素数表示回数をカウントする */
}
}
printf("乗除を行った回数：%lu 素数の数 : %d\n" , counter, sosuCounter);

☆全くはずしていたらごめんなさい。少しでも疑問が解決すれば幸いです。

回答No.2

redfox63

回答は #1氏の通りですね
どうでもいいことですが … 『乗除』じゃなくて『剰余』だと思いますよ

お礼

ご回答ありがとうございます。この他に素数を求めるプログラム文が５つあって他のところで乗法を使うので関連性を持たせるため、乗除とおいてるのだと思います。ただ剰余処理が除法処理のうちに入るのかと言われると私にもわかりません。例題を示されて、剰余を求める際に除法をするから除法に入るのか、と首を傾げた程度です。