素数判定を再帰処理で

Question

お世話になります。
与えられた数が素数、あるいは素数同士の積かどうかを判定するプログラムを再帰処理で書きたいのですが、どのように書いたらいいのかがわかりません。
素数判定は単に数を2から繰り返し割って、割り切れなければ次は3で繰り返し割って・・・とやればよいと思うのですが、再帰ではどのように書いたらよいのでしょうか。
出力結果は以下のようにしなければなりません。例として1173は素数同士の積かを判定します。

1173　=　391　×　3：これらの数は素数か、あるいは素数同士の積か？
391　=　23　×　17：これらの数は素数か、あるいは素数同士の積か？
23は素数。
17は素数。
よって391は素数同士の積である。（23と17は素数あるいは素数同士の積）
3は素数。
よって1173は素数同士の積である。（391と3は素数あるいは素数同士の積）

次に36でやると、
36　=　18　×　2：これらの数は素数か、あるいは素数同士の積か？
18　=　9　×　2：これらの数は素数か、あるいは素数同士の積か？
9　=　3　×　3：この数は素数か、あるいは素数同士の積か？
3は素数。
9は3の2乗、すなわち素数あるいは素数同士の積である。
2は素数。
よって18は素数同士の積である。（9と2は素数あるいは素数同士の積）
2は素数。
よって36は素数同士の積である。（18と2は素数あるいは素数同士の積）

どなたかわかる方、宜しくお願いします。

osu_neko09 · Accepted Answer

#5です。
戻り値が　int　ではなく　int[]　であることにお気づきですか？
素因数分解する関数とは別に、与えられた数はいくつで割れるのかを計算する関数を示したつもりなのですが。
1173を与えられると、（391と3）を返すのです。

課題でしたか。ではまあ勉強のために、ご自身で書いてみるほうがよいのかな。
こちらでは道筋だけ。なお、素数チェックの関数は#5に上げてあります。
メイン（）｛
　素因数分解（1173）
｝
void 素因数分解(int prime){
　int[]ret= 素数チェック(prime,2);
　素数なら｛
　　素数と表示
　　return;
　｝
　何かの二乗なら｛
　　素因数分解（ret[0]）;
　｝
　素因数分解（ret[0]）;
　素因数分解（ret[1]）;  
}

tom11 · Answer

課題なら、課題と最初から言っていれば
もっとスムーズだったと思いますが。

課題の問題には、いろいろ条件もあるし、
条件も、最初から、提起していただけないと
後出し、じゃんけんになります。

しかし私のgoogleとあなたのgoogleとは、違うのかな
私が、ググルト、あなたの質問の次に、
ヒットしいるのですが。!!!!!!!
あなたが、示した。キーワードと同じです。

今度は、forとwhileを使っちゃ駄目とか！！！
ちょっと、わたしにも、そのフローが思いつきませんが。
多少も使っちゃ駄目なのかな？？？

しめしたURLのコードを見ても解るように
再帰も、再帰じゃないコードのちょっとした改良に
なっています。

まず、あなたが、作った、再帰ではないコードを
公開して、誰かに改良してもらったら
いかがですか。？？？

komi1341 · Answer

> それでも課題はあくまで再帰で、再帰処理が使われていればいい、ということではなく、「forやwhileループは使わずに」という指示が出ているのです。
ですのでこんがらがってしまっているわけです。

それはまた難儀なことで…。
まあforにしろ再帰にしろどちらもループ構造なので、一方で書けるなら他方でも書けるはずです。計算速度とか可読性とか使用メモリ量とかで差はでますが。
で、すでに因数分解のサンプルは見つかったわけですから、あとは素数判定が再帰でできればいいわけですね。ざっくり作ってみましたがこんなんどうでしょう。

// 外から呼ぶ際はdivisorに2を指定すること
// nが1以下だったら等の例外処理は省略
boolean isPrime(int n, int divisor) {
if (n == divisor) {
return true;
}
if (n % divisor == 0) {
// 何で割れたか確認してみる
System.out.println(divisor);
return false;
}
if (n / 2 < divisor) {
// ちょっとだけ計算をはしょる
return true;
}
return isPrime(n, divisor + 1);
}

さすがに3桁くらいじゃ落ちないか、と、自分の勉強にも使ってみる。

komi1341 · Answer

#4さんの仰るとおりですね。「java 因数分解」で検索したら一発で、再帰を使った因数分解のJavaサンプルが見つかりましたよ。しかもこのサイト内でした。
http://okwave.jp/qa2283060.html

「ある数を2つの因数に分解する」処理を再帰で無理に作ろうとしていませんか？　本件の目的をより正確に言えば、「素」因数分解を再帰で解くプログラムの作成、ですよね。2つの因数を見つけるのにわざわざ再帰を使うことはありません。仰るとおり、順に割っていって余りが0になる数を探せばいいのですから、forループで書けば充分でしょう。問題は、因数が素数でなかった場合です。このときその因数についてさらに因数分解をする必要があるわけで、その部分についてならまた同じ処理をするわけですから、再帰で書いた方が楽だろうなと思います。

課題の詳細は知りませんが、再帰処理が使われていればいい、という程度ではないでしょうか？　素数判定を再帰でやれとか、そういう細かい指示ではないように思われます。

tom11 · Answer

再帰にこだわっている意味が解りませんが？？？

学校の、指示、それとも、上司の指示？？？

個人の趣味なら、再帰に、こんなにこだわりは、ないのでしょうけど

私の見つけたところは、再帰じゃないものと、再帰の物が
並んで、それも、javaのソースコードとして、
ありましたが。

そんなに、難しいキーワードを使ってもいないし、、

そんなに検索が、難しいでしょうかね。

googleで検索しましたが。

あと、個人の趣味で、いろいろなフローになるのでしょうから。
どんな方法で、出すかによって、プログラムは、
変わるでしょうけど！！！

osu_neko09 · Answer

＞2で割り切れなければ次は3で割っていってという繰り返しの処理を再帰でやろうと思うのですが、
この部分が、どうしても再帰処理でなければいけないんでしょうか？
いえ、出来ないことはないですよ？
int[] div_check(int x,int div){
if(x%div==0){//もし割り切れたら
return new int[]{x/div,div};//商と除数を返す
}else if(div*div>x){//素数なら
return new int[]{x,0};//被除数とゼロを返す
}else{//でなければ
return div_check(x,div+1);//除数を１増やして同じチェックを行なう
}
}

実際にはこんな再帰処理になると思いますが。
1173が渡される
「1173の平方根」を求める
何かの二乗であることがわかれば、この数は素数か・・を表示してその数だけで自分自身を呼び出す。その後、「～の2乗、すなわち素数あるいは素数同士の積である。」を表示
1173を「1173の平方根」以下の自然数で順次割っていき、割り切れる数を探す
3で割り切れることが判るので、　391　×　3これらの数は・・・と表示して、391と3で自分自身を呼び出す。その後、「～素数同士の積である。（391と3は素数あるいは素数同士の積）」を表示
割り切れる数がなければ、「～は素数」を表示

tom11 · Answer

学校の宿題？？？

ネットサーフィンしてみた？？？

なんとなく、そのものずばりの、javaソースを
見つけましたけど、

そんなに、難しい検索では、なかったですよ。

komi1341 · Answer

素数判定ではなく、素因数分解の過程を再帰処理したいんですよね？　素数判定を再帰でやろうとしたら、3桁程度の数字でもメモリ不足で力尽きそうです。

そのへんがはっきりしないので考え方だけ。再帰処理を作るときのコツは、まず実際には再帰しない処理を関数化することです。今回の場合だと2や3（素数）、あるいは6（素数どうしの積）が入力されたときなら、再帰（ループ）処理をしなくて済むと思います。まずはその処理を作ってそれから、それだけでは解けない数（例えば8）が来たときに同じ関数を使いまわせないか、を考えるといいです。

Tacosan · Answer

出力の順序を見れば, 基本的に「再帰じゃない場合と同じ」であることがわかるはず. なぜかというと, 1173 のときにまず「1173 = ...」とあって, その次の行から「よって 391 は」の行までが 391 に対する処理であることがわかるから.
ちょっと 9 の (というか素数の 2乗の) 処理が面倒かもしれんけど, 「再帰しないで処理する」ことができれば本質的に難しいところはありません.

Tacosan · Answer

出力結果として例が示されているのですが, どうすればいいのかを「言葉で」書いてもらえませんか? これだとほかの数のときにどうしていいのかが分かりません.
特に 0 とか 1 とか 1048576 とかのときにどうしていいのかが分からん.
でも, これはあんまり「素数同士の積」とは言わない気もするんだが....

素数判定を再帰処理で

#5です。

この回答への補足

課題なら、課題と最初から言っていれば

この回答への補足

> それでも課題はあくまで再帰で、再帰処理が使われていればいい、ということではなく、「forやwhileループは使わずに」という指示が出ているのです。

この回答への補足

#4さんの仰るとおりですね。

この回答への補足

再帰にこだわっている意味が解りませんが？？？

この回答への補足

＞2で割り切れなければ次は3で割っていってという繰り返しの処理を再帰でやろうと思うのですが、

この回答への補足

学校の宿題？？？

この回答への補足

素数判定ではなく、素因数分解の過程を再帰処理したいんですよね？ 素数判定を再帰でやろうとしたら、3桁程度の数字でもメモリ不足で力尽きそうです。

この回答への補足

出力結果として例が示されているのですが, どうすればいいのかを「言葉で」書いてもらえませんか? これだとほかの数のときにどうしていいのかが分かりません.

この回答への補足

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

素数判定ではなく、素因数分解の過程を再帰処理したいんですよね？　素数判定を再帰でやろうとしたら、3桁程度の数字でもメモリ不足で力尽きそうです。