ぜひシェアをお願いします!

【Java】3パターンの素数の出力方法

typing

プログラミング中にふと気づいたことなのですが、素数の出力の仕方には3種類あるのでは?

ということでコードを書いてみました。

(2015/12/29 追記)

効率化のご指摘を受け、一部ソースコードを書き換えました。

スポンサーリンク

1.素数か否かを判定する方法

一つ目は、入力した数字が素数であるかないかを判定するコードです。

今回は、キーボードから入力した数字の判定を行います。

ソースコード

ソースの内容

まず、キーボードから入力する値 num は 2 以上の整数を仮定しています。

boolean 型の変数 sosu には最初に true を代入しておきます。

その後、for 文を使って num を 2, 3, 4….., num-1 で割っていき、もし割り切れて

余りが0になったら素数ではないので、sosu に false を代入してループを抜けます。

割り切れる数字がなければループが最後まで続いても、sosu は true のままなので、最後の if 文で素数か否かを表示させています。

(2015/12/29 追記)

判定する数の半分を超えた値を約数に持つことはないので、for 文の繰り返し条件を修正しました。

入力した数が素数でなければ処理にかかる時間は変わりませんが、素数であった場合は従来の1/2の処理で済みます。

注意点

sosu に false が代入されたら、その後の処理を行う必要はないので break しましょう。

2.最大値を定める方法

1.の方法では、キーボードから入力した一つの数字しか判定できません。

そこで、次は素数を探す数字の範囲を決める方法を考えます。

ソースコード

ソースの内容

今回はキーボード入力で max に 2 以上の数を代入し、2 から max までの間にある素数を出力するプログラムです。

例えば、20 と入力すると

2
3
5
7
11
13
17
19

と出力されます。

これは、2つの for 文を使っています。外側の for 文は 2 から max まで一つずつ整数を指定しています。

所謂、割られる数です。

それを内側の for 文で 2 から(外側で指定している整数-1)で割っていきます。

こっちは割る数です。

最終的に sosu に false が入らなければ、素数として出力します。

(2015/12/29 追記)

こちらも上の場合と同様、処理を半分にしました。

注意点

ループの終わりに再度 sosu に true を代入することを忘れずに。

代入していないと sosu の値がずっと false のままなので、その後の処理が反映されなくなります。

このコードでは、外側のループが始まるたびに boolean 型の sosu を初期化し直しています。

3.個数を定める方法

上の2種類はググってすぐに出てきますが、出力する素数の個数を指定する方法はなかなか見つからなかったので、ここに書いておきます。

ソースコード(変更前)

ソースの内容(変更前)

for 文を使おうとするとループできる回数が指定されてしまうので、例えば5回ループさせたら 5までの素数判定しかできません。

そうすると、個数的には3個しか出力できないことになります。

そこで、while 文を使った繰り返し処理を考えます。

int 型変数 count を使って、素数のときのみカウントしていきます。

count が キーボードから入力した個数 max と等しくなると、while 文のループが終わります。

ソースコード(変更後)

ソースの内容(変更後)

変更前は割られる数 num を2, 3, 4,…と増やしていき、そのそれぞれの数を2から num-1 までの数で割っていくという効率の悪い方法を採っていました。

ここで、これまでの2つの方法のように num の半分までで割れば良い、という考え方もできますが、更に効率のいい方法を教えていただきました。

素数でない数は必ず素数を因数にもつので、素数で割り切ることができなければ、その値は素数になるという考え方を用います。

最初に kosuu[0] だけ設定しておき、2, 3, 4,… と増えていく数を kosuu で割っていきます。

そこで、新たに見つけた素数を kosuu[i] (i = 1, 2, …, max) に代入していき、最後にまとめて表示するようにしました。

注意点

大切なことなので2回言いますが、繰り返しの終わりに sosu を true にし忘れないようにしましょう。

この記事書きながらハマったので……

スポンサーリンク

ぜひシェアをお願いします!

mktia は、Amazon.co.jp を宣伝しリンクすることによってサイトが紹介料を獲得できる手段を提供することを目的に設定されたアフィリエイト宣伝プログラムである、Amazon アソシエイト・プログラムの参加者です。