誤作動の原因を教えてください

質問

大学の課題で、あるプログラムを作成することになったのですが、実行しても意図したこととは違ってしか実行しなかったので、その原因と、どう修正すべきかを具体的に教えてください。
技術者向けというわけでもなさそうですが、C言語初心者の私には、小一時間考えてみても分からなかったので、お手柔らかに教えていただけると幸いです。

課題の内容は以下の通りです。

コンソールから入力した整数N以下のすべての素数を表示するプログラムを作成せよ。その際に次の点に配慮せよ。

・2は素数である。
・3は素数である。
・4以上の偶数は素数ではない。
・小さい方から割って、割り切れるかどうかを確認する場合に、素数かどうかを確認したい数の平方根より大きい数で割って確認する必要はない。

さらに、1行に10個の素数を印刷したら、改行するように改良できていたら加点する。

次に実際に私が作成したプログラムを載せます。
ソースをコピペしただけなので、コメント欄がそのまま表示されていたり字下げや改行が見にくくなっていたりしているとは思いますが、ご了承ください。

#include <stdio.h>
#include <math.h>
#define WIDTH 10

int main (int argc, const char * argv[]) {

int i, j, k, n, flag;

printf("自然数を入力してください\n");
scanf("%5d",&n);

k = 1;
printf(" 2"); //2は明らかに素数なので始めから表示するようにしておく。

for(i=3; i<=n; i+=2){ //3から調べていくが、偶数は明らかに素数ではないので奇数だけ調べていく。
flag = 0;

for(j=1; j <= sqrt(i); j+=2){ //平方根以上の数で割って確認する必要はない。3以上の素数は奇数であるから偶数では割り切れない。

if(j != 1 && i%j == 0){ //もしもiが1以外で割り切れたら、
flag = 1; //素数ではないので終了する。
break;
}

if(flag == 0){
printf(" %5d",i);

k++;

if(k >= WIDTH){
printf("\n");
k=0;
break;
}

}

}

}
printf("\n");

return 0;
}

そして実行結果ですが、ここで問題が出てしまいました。
実際の実行結果は諸事情によりここでは載せられませんが、例えば20という数値を入力したときには、

自然数を入力してください
20
2 3 5 7 9 11 11 13 13 15
15 15 17 17 19 19

というようにディスプレイ上に出力されたわけです。
ご覧の通り、
(1)奇数が全て表示されてしまっている(素数ではない9や15が表示されている)。
(2)11以降の数が複数回表示されてしまっている。
(3)その上で1行に10個数が出力すると改行するようになっている。
という点が分かります。
ちなみに大学のPCの動作環境についてはよく分からないし、あまり公言はできませんが、OSはMacで、ソフトはXcodeのCommand Line Utility中のStandard Toolを利用しているということだけは言っておきます。
課題の締め切りは6月29日12時までとなっているので、それに間に合うように解答していただければ幸いです。よろしくお願いします。

回答No.4

f272 · ベストアンサー

致命的なのは
for(j=1; j <= sqrt(i); j+=2){　...(1)
のループの中で
if(j != 1 && i%j == 0){ ...(2)
という判定を行っているが、(1)の最初の値であるj=1のときには必ず(2)がfalseになるのでif(flag == 0){
の中に入って素数だということにされていることです。

回答No.7

asuncion

＞今週は毎日のように課題と試験があるので、ゆっくり6日間考える時間はとれないというわけです

そういう理由があれば、人からもらった回答をそのまま自分のものとして
提出するのはありだと考えているのですか？

そういうことを繰り返していると、やがて「思考停止状態」に陥ったりしませんか？

回答No.6

yama5140

（適切な回答が多く、解決しそうなので、年寄りのソース投稿は締め切り前日に、と思ったのですが忘れちゃいそうで・・）

＞誤作動の原因を教えてください

　これについては、No.2 さん以降の「回答」をじっくり考えて下さい。
　このとき、手元のソースの「字下げ」幅を２倍程度にすると、より早く解決するかもしれません。

　「原因」が判明し、正しく動くようになってから、下のソースを参照してみて下さい。

・質問者様のソースをちょっぴり改変しています。

　　　flag = 1; を「素数」としています（フラグの使い方として、こちらの方が自然？）。
　　　素数の数を、iCnt でカウントアップしています。
　　　数学関数は使っていません（平方根ではなく平方を用いています）。
　　　入力自然数までの「素数」の数を出力します（ちなみに、132 番目は、743 らしいです　http://ja.wikipedia.org/wiki/743 ）。
　　　（投稿上の都合により、_ 使用、コピペ後半角空白に）

　　　! について、「初めて見た、ビックリした」のなら、「 0 == 」に読み換えて下さい。

注：あくまで「参照／試行」にとどめて下さい。自分のが正しく動いたら、思いっきし感動して下さい（ ← ★今後に重要）。

#include <stdio.h>

#define　　WIDTH　　10

int　　main( int argc, const char *argv[] )
{
　　int　　i, j, iNum, flag;
　　int　　iCnt = 2;　　// 2, 3 表示の２個

　　printf( "３以上の自然数を入力してください\n" );

　　scanf( "%5d", &iNum );　　// ５桁まで

　　printf( "_____2_____3" );　　// 2, 3 は明らかに素数なので始めから表示。

　　for( i = 5; i <= iNum; i += 2 ){　　// 5 から調べていくが、偶数は明らかに素数ではないので奇数だけ調べていく。

　　　　flag = 1;　　// 「素数」で初期化

　　　　for( j = 3; ( j * j ) <= i; j += 2 ){　　// 平方「超」の数での確認不要。3 以上の素数は奇数であるから偶数では割り切れない。

　　　　　　if( ! ( i % j ) ){　　// 割り切れるか

　　　　　　　　flag = 0;

　　　　　　　　break;
　　　　　　}
　　　　}
　　　　if( ! flag )　　continue;　　// 素数ではないので次へ

　　　　if( ! ( iCnt++ % WIDTH ) )　　printf( "\n" );

　　　　printf( " %5d", i );
　　}
　　printf( " (%4d)\n", iCnt );

　　return( 0 );
}
注：「字下げ」に全角空白２ケを用いています。コピペ後、タブに一括変換して下さい。

回答No.5

redfox63

設問に
1) 2は素数
2) 3は素数
3) 4以上の偶数は素数でない
4) 小さい方から割って、割り切れるかどうかを確認する場合に、素数かどうかを確認したい数の平方根より大きい数で割って確認する必要はない
とあるのに なぜ3を調べるのでしょう
また『素数は自身と1以外の約数を持たない数』のはずですから
4) の検査をする際に 1からやる必要があるのでしょうか
1から検査をするため 判断用のif文に j!=1 といった無駄な条件を付け加える必要が出てきます

後は f272氏の回答のように
素数の最終判定の位置がおかしいため 検査した値がすべて素数といった結果になってしまっているのでしょう

回答No.3

ESE_SE

言語を問わず、プログラムの基礎構造は
・代入・演算
・条件分岐
・ループ
でほぼ語り尽くされます。

どこかの条件に間違いはありませんか？
ループに入る条件、ループから抜ける条件に不備はありませんか？
11から動作がおかしいのであれば、11が表示されるケースについてプログラムがどのような挙動を取っているか、プログラムの動きを追い掛けましょう。

回答No.2

Quant

'}'の位置を調べてみましょう。

またbreak;もいらないところがあります。これのおかげで40、50と入れても10個以上は表示されない。

回答No.1

asuncion

＞課題の締め切りは6月29日12時まで

まだ６日近くもあるではないですか。
それまでに、「ご自分で」じっくり考えてみましょう。

補足

それは承知しているつもりですが、今週は毎日のように課題と試験があるので、ゆっくり6日間考える時間はとれないというわけです。
ここで締め切りの日をあえて示しているのは、一般的にみて時間が無いからではないのです。