２以上の数値で素因数分解を求めるプログラム

Question

このソースコードは変数xが入力された値を格納しint型のyへ渡しているという認識です。
初歩的な質問かもしれませんが、なぜforの中でさらにwhileで繰り返す必要があるのかわかりません。
for、whileの中のコードの理解が出来ていないです。
そもそも、繰り返し処理を記述しなければいけないのでしょうか？
条件分岐でもこのプログラムは実現出来る気がするのですが、解説お願いします。

###該当のソースコード

	public static void main(String[] args) {

		System.out.println("数値を入力して下さい");
		Scanner num = new Scanner(System.in);
		int x = num.nextInt();
		int y = x;

		for (int i = 2; x > i; i++) {
			while ((y % i) == 0) {
				System.out.println(i);
				y = y / i;
			}
		}
	}
}

Answer 1

ループの中で何をしているのか

for、whileの中のコードの理解が出来ていないです。

((y % i) == 0)という条件式で、何をコントロールしているのかじっくり考えてください。

ループの中にループがある理由

なぜforの中でさらにwhileで繰り返す必要があるのかわかりません。

『ループが入れ子になっている』『ネストしている』という表現をします。

元のプログラムでループが入れ子になっているのは、二回以上用いられる約数のためです。
内部のループを外すと、24 = 12223が計算できません。

そもそも

二重ループにしているのは無駄だと思います。以下で充分。

int i = 2;
while(y != 1) {
    if(y % i == 0) {
        System.out.println(i);
        y /= i;
    }
    else {
        i++;
    }
}

繰り返しは必要か

そもそも、繰り返し処理を記述しなければいけないのでしょうか？

再帰処理を用いれば実現可能です。(ただし、非推奨)

private void recursionPrime(int arg, int div) {
    if(arg == 1) return;

    if(arg % div == 0) {
        System.out.println(div);
        recursionPrime(arg/div, div);
    }
    else {
        recurtionPrime(arg, div+1);
    }
}
private void printPrimeFactor(int arg) {
    recursionPrime(arg, 2);
}

なんか、Javaっぽくないプログラムになってしまいました...
raccyさんの指摘のとおり、Javaでの安易な再帰処理の使用は推奨されません。
特に拘りや制約条件のない限り、ループで処理するのがよいでしょう。

重要

コードはバッククオート三つで括ってください。
よくわからない場合は、マークダウン記法について調べてみてください。
これをしているかどうかで、回答の量と質が変わってきます。
(マークダウン記法を用いていない質問者には回答しない、という方針の人もいます。)

追記

anahina1979さんが、以下のとおり驚くべき真実を教えてくださいました。

ちなみに、素数は2以外の偶数は存在しない

それを反映するとこうなります。

while(y % 2 == 0) {
    System.out.println(2);
	y /= 2;
}

i = 3;
while(y != 1) {
    if(y % i == 0) {
      	System.out.println(i);
       	y /= i;
    }
    else {
       	i+=2;
    }
}

処理速度が上がって、オーダーで言うとO(n)からO(n)になりましたね！

Comments

[momon-ga]

ずいぶん原型なくなっちゃいましたが（ｗ
これなら、y使わないで直接ｘを除算でよいですね。

[LouiS0616]

『とりあえずfor文使っとけ』という風潮が問題な気もします。
どちらかと言うとwhile文の方が汎用性が高いと思うのですが...

おっしゃるとおり、yの存在意義はもはやないです。

[退会済みユーザー]

ちなみに、

素数は2以外の偶数は存在しない

[LouiS0616]

実行速度とスマートさどっちを取るかだと思いますね。
最初だけ分岐すると、ちょっと汚くなるように感じるのです。

[raccy]

Javaは末尾再帰最適化をサポートしていないため、素因数が大きめの数字ではスタックオーバーフローで止まってしまうのではないでしょうか？再帰回数がそれなりに少ないことがわかっていないなら、Javaで再帰関数は使うべき(勧めるべき)では無いと思われますが、いかがですか？(私としては、そもそもJavaを勧めないんですけど)

[LouiS0616]

質問の『そもそも、繰り返し処理を記述しなければいけないのでしょうか？』という記述に対する返答であって、勧める意思はないです。
誤解のないよう、非推奨であることを追記させていただきますね。

[LouiS0616]

raccyさんの質問／回答／コメントではいつも勉強させていただいています。
コメントありがとうございます。

Answer 2

実際に紙面上で素因数分解しながら読んでください。例えば540の素因数分解を考えます。
0. まず一番小さな素数"2"で割れるか試します(for文でi=2)。
0. その素数で割れるだけ割ります(while(y%i==0))。
540/2=270,270/2=135,135は2で割れない
0. 次の素数"3"で割れるか試します(forの更新文i++)。
0. その素数で割れるだけ割ります(while(y%i==0))。
135/3=45,45/3=15,15/3=5,5は3で割れない
0. 次の素数"5"で割れるか試します。
正確にはいったんiは4になりますが、前のステップで2で割れるだけ割っているため、
4では絶対割り切れないのでwhile文に入れず次のforに入る。
0. その素数で割れるだけ割ります(while(y%i==0))。
5/5=1

という行程を踏むループになっています。

Answer 3

なぜforの中でさらにwhileで繰り返す必要があるのかわかりません。

whileは置いといて、for文からですが、素因数を求める為に、割り算に使う i を２から
自分の数字の１つ前までのループさせれば良しとしています。もれは無いでしょう。
なのでfor (int i = 2; x > i; i++){ .... }

さらにプログラムは素因数分解を求める為に、whileを使っているいます。
（整数が、どんな数であっても、素数の積によって表すことができる）

素因数分解を行うには、順に小さいものから割りまくるです。
割り算する数字が同じでも、割り切れている内は何回でも割ります。yは減っていきますけど。
例えば ２０ の場合２，２，５になります。（構成しているのは素数です。）

これをwhileで実現しています、（割り切れている間は回る）
実際２０の場合、割切れる２は２回ループして
y、が５になった時点で２では割り切れず、forループへ移ります。y/i は次の次の次の５で割り切れます。
forループは５から先の１９までループして終了します。ちょっとだけ効率化するとして yが１になった時点で
forループをberakすれば良いかな。

入力が素数の場合でもforループの回数は入力数の半分で良いのですけれどね。