素数判定を再帰処理で

質問

お世話になります。
与えられた数が素数、あるいは素数同士の積かどうかを判定するプログラムを再帰処理で書きたいのですが、どのように書いたらいいのかがわかりません。
素数判定は単に数を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は素数あるいは素数同士の積）

どなたかわかる方、宜しくお願いします。

回答No.10

osu_neko09 · ベストアンサー

#5です。
戻り値が　int　ではなく　int[]　であることにお気づきですか？
素因数分解する関数とは別に、与えられた数はいくつで割れるのかを計算する関数を示したつもりなのですが。
1173を与えられると、（391と3）を返すのです。

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

補足

ありがとうございます。ではブログにコメントさせていただきますね！

回答No.9

tom11

課題なら、課題と最初から言っていれば
もっとスムーズだったと思いますが。

課題の問題には、いろいろ条件もあるし、
条件も、最初から、提起していただけないと
後出し、じゃんけんになります。

しかし私のgoogleとあなたのgoogleとは、違うのかな
私が、ググルト、あなたの質問の次に、
ヒットしいるのですが。!!!!!!!
あなたが、示した。キーワードと同じです。

今度は、forとwhileを使っちゃ駄目とか！！！
ちょっと、わたしにも、そのフローが思いつきませんが。
多少も使っちゃ駄目なのかな？？？

しめしたURLのコードを見ても解るように
再帰も、再帰じゃないコードのちょっとした改良に
なっています。

まず、あなたが、作った、再帰ではないコードを
公開して、誰かに改良してもらったら
いかがですか。？？？

補足

＞課題なら、課題と最初から言っていれば
どうやら私をせめているようですが、別にこの場合課題などという必要はありません。
はじめから「これを再帰で」、と明記しているので。
同じグーグルで同じように検索結果が出ないのが謎ですけど

回答No.8

komi1341

> それでも課題はあくまで再帰で、再帰処理が使われていればいい、ということではなく、「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桁くらいじゃ落ちないか、と、自分の勉強にも使ってみる。

補足

ありがとうございます！ちょっと試してみます！

回答No.7

komi1341

#4さんの仰るとおりですね。「java 因数分解」で検索したら一発で、再帰を使った因数分解のJavaサンプルが見つかりましたよ。しかもこのサイト内でした。
http://okwave.jp/qa2283060.html

「ある数を2つの因数に分解する」処理を再帰で無理に作ろうとしていませんか？　本件の目的をより正確に言えば、「素」因数分解を再帰で解くプログラムの作成、ですよね。2つの因数を見つけるのにわざわざ再帰を使うことはありません。仰るとおり、順に割っていって余りが0になる数を探せばいいのですから、forループで書けば充分でしょう。問題は、因数が素数でなかった場合です。このときその因数についてさらに因数分解をする必要があるわけで、その部分についてならまた同じ処理をするわけですから、再帰で書いた方が楽だろうなと思います。

課題の詳細は知りませんが、再帰処理が使われていればいい、という程度ではないでしょうか？　素数判定を再帰でやれとか、そういう細かい指示ではないように思われます。

補足

「java 素因数分解　再帰」で検索していたのですが、見つけられませんでした。再帰って入力しなくてよかったのか・・・
再帰を無理に使う必要はないというのは初めからわかっています。
それでも課題はあくまで再帰で、再帰処理が使われていればいい、ということではなく、「forやwhileループは使わずに」という指示が出ているのです。
ですのでこんがらがってしまっているわけです。

回答No.6

tom11

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

学校の、指示、それとも、上司の指示？？？

個人の趣味なら、再帰に、こんなにこだわりは、ないのでしょうけど

私の見つけたところは、再帰じゃないものと、再帰の物が
並んで、それも、javaのソースコードとして、
ありましたが。

そんなに、難しいキーワードを使ってもいないし、、

そんなに検索が、難しいでしょうかね。

googleで検索しましたが。

あと、個人の趣味で、いろいろなフローになるのでしょうから。
どんな方法で、出すかによって、プログラムは、
変わるでしょうけど！！！

補足

再帰にこだわってるわけではありません。課題なので仕方がないのです。
再帰などの必要なキーワードを入力してググりはしましたが再帰処理のソースコードは見つけられませんでした。
よろしければＵＲＬを貼っていただけませんか？

回答No.5

osu_neko09

＞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は素数あるいは素数同士の積）」を表示
割り切れる数がなければ、「～は素数」を表示

補足

関数の呼び出しも含めて、osu_neko09さんのコードを元に自分なりに書いてみたのですが、

public class Homework{

public static void main(String[] args){ //メイン

int func_call = func(1173, 2);

}

public static int func(int prime, int div){ //再帰処理

if(prime%div==0){
System.out.println(prime+"="+prime/div+"*"+div+"; are thse factors either prime or products of rime?");
return func(prime/div, div);
}else if(div*div>prime){
System.out.println(prime+" is prime");
System.out.println(div+" is prime");
System.out.println(prime*div+" is the product of primes");
return　0;　←ここで返す値がいまいちわかりません
}else{
return func(prime,div+1);
}
}

}

このようにすると
1173=391*3; are these factors either prime or products of rime?
391=23*17; are these factors either prime or products of rime?
23 is prime
17 is prime
391 is the product of primes
以上のような出力結果になりました。319の証明はこれで出来たのですが、次に3の証明ができません。
391の証明が終わったときには div　の　値がすでに17に変わってしまっています。
osu_neko09さんは、
return new int[]{x/div,div};//商と除数を返す
というように、メインに値を返しているのでしょうか。
物分りが悪くて申し訳ありません。このプログラムをどのように直したら良いか教えていただけないでしょうか？宜しくお願いします。

回答No.4

tom11

学校の宿題？？？

ネットサーフィンしてみた？？？

なんとなく、そのものずばりの、javaソースを
見つけましたけど、

そんなに、難しい検索では、なかったですよ。

補足

はじめに検索してみつけたどなたかのプログラムはあるのですが、再帰ではなく、これを再帰にするには自分にはちょっと複雑すぎたのでこちらで質問させていただきました。

回答No.3

komi1341

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

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

補足

はい、すみません。素因素分解の過程を再帰処理で行いたいのです。

メイン関数（調べる値の定義）と再帰処理用の関数2つを用意しようと思うのですが、
再帰処理用の関数では、メインから受け取った値の因数を調べるわけですから
まず2で割って（上の例で1173を2で割る）、割り切れたらその商と2の因数を調べるためにまた2から割っていって・・・
2で割り切れなければ次は3で割っていってという繰り返しの処理を再帰でやろうと思うのですが、
この再帰の方法と、「1173　=　391　×　3：これらの数は素数か、あるいは素数同士の積か？」という文を一体どうやって表示させればよいのかがわかりません。
6が入力されても、まず2で割って因数を求めるわけですから再起用の関数は使わなければいけませんよね？
8だと2×2×2で同じ因数が3つ続くので2が素数であると判定できればそれでいいと思うのですが・・・。
すいません。再帰だとこんがらがってしまいます・・・

回答No.2

Tacosan

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

回答No.1

Tacosan

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

補足

わかりづらくて申し訳ありません。つまり与えられた数（素数）を素因数分解するのですが、その過程を一つ一つ証明（因数の因数を一つ一つ）していくプログラムです。
まず1173の場合だと、因数は391と3。なので次に391と3両方の因数を出します。
391の因数は23と17。なので次に23と17の因数ですが、これらは素数ですので、「391は素数の積」ということで391の証明は終わりです。
次に3の因数ですが、これは素数ですので「3は素数」ということで3の証明は終わりです。
これで391と3が素数、あるいは素数の積という証明がすみましたので、「1173は素数の積」といえます。これを再帰を用いて、

1173　=　391　×　3：これらの数（391と3）は素数か、あるいは素数の積か？
391　=　23　×　17：これらの数（23と17）は素数か、あるいは素数の積か？
23は素数。
17は素数。
よって391は素数の積である。
3は素数。
よって1173は素数の積である。

このように画面に出力していきたいのです。
恐らく今回のプログラムでは、0と1は試されないものと考えていいと思います。
1048576も同じようにしていきます。まず因数を求めなければならないので、まず2で割っていきます。1048576は2で割り切れるので因数は524288と2です。（もし割り切れなければ次は3で割っていきます）
次に524288の因数をまた2で割って求めます。結果262144と2。
なので次は262144の因数を・・・と1つ1つ繰り返し求めていき、最終的に1048576が因数の積かを証明していきます。