ある範囲から素数を見つける C言語

Question

c言語で１００〜１０００の範囲の素数を見つけるプログラムを作っているのですが、以下のプログラムでは素数ではない数も素数と判定されてしまいます。修正すべき点を教えていただきたいです。

#include <stdio.h>
#include <stdint.h>

int judge(int a, int b)
{
    if( a % b == 0 ) return 0;
    else return 1;
}

int main(void)
{
     int n,m;
     int c = 0;

    for(n = 100; n <= 1000; n++) {
        for(m = 2; m < n; m++){
            
        if(judge(n,m) == 1) {
            printf("整数 %d は素数.\n", n);
            c++;
            break;
        }
        }
    }
        
    if (c != 0)
        printf("100 〜 1000 の範囲に素数は %d 個ありました。\n",  c);

    else
        puts("100 〜 1000 の範囲に素数はありませんでした。\n");

    return 0;
}

Answer 1

どんな数字が素数となったでしょうか?
例えば、 105 ?

if(judge(n,m) == 1) {

n以下の全ての mで、割り切れない事を判定しないといけないと思いますが、一度でも割り切れない場合、素数と見なしている事が問題ではないでしょうか?

Comments

[退会済みユーザー]

どのようにしたら全ての数で割り切れない場合、素数とする。とかけるのでしょうか。教えていただきたいです。

Answer 2

その数以下に、割り切れない数が１つでもあれば素数としてしまっています。
2からその数未満のすべての数で割り切れないときが素数です。

Comments

[退会済みユーザー]

2からn未満にmの範囲を変更したのですが、全ての数で割り切れない時、素数となるようにするにはどのように書いたら良いのかわかりません。教えていただけると嬉しいです。

[otn]

簡単には、「割り切れたフラグ」を設けて、
mのループで、割り切れたらフラグをセットしてbreak
mのループが終わった時点で、フラグを見て、セットされていなければ、途中で一度も割り切れなかったということです。

[退会済みユーザー]

ありがとうございます、がんばってみます

[otn]

「繰り返しの中で、条件を満たす要素が１つでもあるか、あるいは、全くないか、を調べる」というのはよくあるパターンです。自分のものにしましょう。
例：
・ファイルの中に「abc」という文字列があるか？ないか？
・今までにこの場所に来たことがあるか？

Answer 3

for(n = 100; n <= 1000; n++) {
for(m = 2; m <= n; m++){

m == n のとき、nがどんな数であろうと絶対に割り切れます。

Comments

[退会済みユーザー]

m<nに修正しました。この後すべきことを教えていただきたいです

[LouiS0616]

他の回答で指摘されているとおり、『一度でも～～できたら素数』というロジックが間違っています。
手計算で一度試し割法をなぞってみると分かり易いでしょう。

Answer 4

if(judge(n,m) == 1) {

        printf("整数 %d は素数.\n", n);

一回judgeが通ったら素数判断してますが、これじゃダメですよね。

Comments

[退会済みユーザー]

どのようにしたら全てjudgeが通ったら素数判断、ができるのでしょうか

[y_waiwai]

すべて通せばいいのです