Javaと素数の判定について・・・

質問

Javaのプログラミングで、素数の判定をfor構文とif構文だけで、どうやったら作れるものでしょうか。教えてください。。

回答No.6

Ishiwara

もう答が出ているようなので、こまかい注意だけ述べます。
因数の候補を作るときに（直前の数＋１）は感心しません。２以外に偶数の素数はないわけですから、４，６，８‥は飛ばします。
また、３の倍数を飛ばすためには、＋２、＋４、＋２、＋４ とすべきでしょう。
なお、√Ｎより大きい数は試す必要がない、ということも盛り込むべきです。

回答No.5

SpiralGalaxy

＞breakというのは、初めて聞くのですが・・・

break　とはループをそこで強制終了させるための命令です。
以下の例では n=0,1,2,3,4.....999 までループするはずですが
途中で処理を打ち切る必要がある条件が成立したとすると
n は 999 に達する前にループを抜け出します。

例）
int n = 0;
if(n = 0; n < 1000; n++) {
　// ... 何らかの処理
　if(何らかの終了条件が成立) {
　　break;
　}
}

またループが二重になっている場合は内側のループを脱出します。
以下の場合(2)のループを抜け出す場合があるということです。
jは0～99まで必ずループしますが
kは50～99を全部ループする場合もあれば途中で終わる場合もあります。

for(int j=0; j<100; j++) { // (1)
　for(int k=50; k<100; k++) { // (2)
　　if(何かの条件) {
　　　break;
　　}
　}
}

＞これにそのbreak構文というのを挿入すれば完成でしょうか・・

んー。もう少し足りないですね。

＞else if (k%m !=0) System.out.println("素数である");

これだと前回説明したように
全部の数で割れるかどうかの判定を行う前に結果を表示しているのでまずいですね。
こんな感じにしてみたらいかがでしょう。

for ( ;k<=n ;k++){

　boolean isSosu = true;　// フラグを使って
　　　　　　　　　　　　　// その数が素数であると仮設定します
　for (;m<=(n-1) ;m++) {

　　// ここで素数かどうか判定
　　// 素数でないことが判明したら
　　// isSosu = false; に設定して break;

　}

　// 内側のループが終わった、
　// ここで結果を判定、表示します。
　// if文でフラグを判定

}

もうひとつ。
println ですけれど…「何が」素数か素数でないのかがわからないので

println(k + "は素数である");
println(k + "は素数ではない");

とした方がいいでしょう。

回答No.4

SpiralGalaxy

ちょっと間違えました。

＞どれで割ってもあまりが出ない場合が「素数」ですので

どれで割っても余りが出る場合が「素数」です。

回答No.3

SpiralGalaxy

おおお。なかなかいいですね。
でも問題の箇所があります。

＞for (;m<=(n-1) ;m++)
for (m=2;m<=(n-1) ;m++)
としないと k=3以降 を計算するときは m の値は増えたままですので
おかしなことになります。m=2 にもどしてやる必要があります。
ついでに { もつけましょう。

＞if (k%m ==0) System.out.println("素数ではない") ;
break がないので、「素数ではない」が何度も何度も表示されてしまいます。

＞else System.out.println("素数である");
たとえば 9 が素数であるかどうか判定する場合
2,3,4,5,6,7,8 までの数で割ってみて、どれで割っても
あまりが出ない場合が「素数」ですので１回の割り算では判定できません。今のままのコードでは 9%2 を計算しただけで判定しているので「素数である」になってしまいます。なので 2～n-1 までの判定がすべて終わったあと、「素数である」は表示しないとなりません。

「素数でない」のは１回でも当てはまれば、そこで打ち切ればいいので break; します。

お礼

おぉ！添削までしてくださるとは！多謝多謝です！
breakというのは、初めて聞くのですが・・・よろしければ使い方を教えてくださいませんか？
アドバイスの結果、このようなプログラミングになったのですが、これにそのbreak構文というのを挿入すれば完成でしょうか・・
int n=Integer.parseInt(args[0]);
int k=2;
int m=2;
for (;k<=n ;k++){
for (m=2;m<=(n-1) ;m++){
if (k%m ==0) System.out.println("素数ではない");
else if (k%m !=0) System.out.println("素数である");
}

回答No.2

SpiralGalaxy

課題か何かでしょうか？
とりあえず、ベタな解き方でヒントだけ。

例えば１から１０００のうちの数字の中から素数だけを抽出するとすると、

for 文で１から１０００までループします。この時のループ値をＮとします。二つ目のループで２からＮ－１までループします。この時のループ値をＭとします。

ＮをＭで割って、再びＭを掛け算してみます。
元のＮになれば割り切れたということ（ここでIF文を使う)なので、素数ではないのでループをブレイクします。二つ目のループで２～Ｎ－１まで繰り返しても割り切れなかった場合は素数ですので
画面にプリントします。

これをループ値Ｎで１～１０００まで繰り返します。

割り切れるかどうかの判定に % を使えばif文の部分はもっと簡潔かもしれません。

お礼

回答ありがとうございましたｍ（..）ｍ大変参考になります。
n/(1～(n-1))を行うわけですね。
つまり、こういう事でしょうか・・・

　int n=Integer.parseInt(args[0]);
int k=2;
int m=2;
for ( ;k<=n ;k++){
for (;m<=(n-1) ;m++)
if (k%m ==0) System.out.println("素数ではない") ;
else System.out.println("素数である");

回答No.1

koko_u_

>素数の判定をfor構文とif構文だけで、どうやったら作れるものでしょうか。
まずはどうやって(どんなアルゴリズムで)素数を判定しようとしているか補足欄にどうぞ。

だいたい、for 構文と if 構文だけでは変数の宣言すらままならないと思いますが。