プログラムについて

質問

よろしければ教えてください。
大きな桁数（１０進５０桁程度）の整数を因数分解するアルゴリズム
（エラトステネスのふるいを除く）に
ついて調べ、実際に因数分解するプログラムを実装しなさい。

という課題が出されたのですが
問題の基本的なところから理解できていません。

初歩的なところから説明していただける方がいましたら
回答お願いします。

回答No.4

R_Earl

お礼文を見てふと思ったのですが、質問者さんは
「中学校の頃に習った素因数分解の方法」を
プログラム化するつもりなのでしょうか？
課題で問われているのはそういうことではないと思います。

課題は

素因数分解アルゴリズムについて調べて、
プログラムを実装しなさい

となっています。
中学校の頃に習った方法は既に知っているのですから、
「調べる」というのは変ではないでしょうか。
課題で問われているのは

既知の「中学校の頃に習った方法」や「エラトステネスのふるい」以外の
素因数分解方法を調べ、それをプログラム化しなさい

ということではないでしょうか？
例えば「ρ法」や「数体ふるい法」等のようなものを調べて
実装するということだと思います。

> どのようなプログラムにするか考えてみたものの
> 2、3、5、7…といったようにどこまで数字を用意して
> いいのか分からずいきづまっています。
> よろしければサンプルみたいなものをいただけんしでしょうか?

これは「中学校の頃習った素因数分解法」をプログラム化しようとしているのでしょうか？
課題の主旨から外れているかもしれませんが、
プログラム化の参考になるかもしれないので、一応書いてみます。

まず、素数を用意する必要ありません。
例えば7429を素因数分解したいなら

7429 ÷ 2が割り切れるかチェック
7429 ÷ 3が割り切れるかチェック
7429 ÷ 4が割り切れるかチェック
7429 ÷ 5が割り切れるかチェック
7429 ÷ 6が割り切れるかチェック
7429 ÷ 7が割り切れるかチェック
・
・
・

というように、わる数を1ずつ増やしていくようにすればよいです。
「÷2と÷3を試したなら、÷6を試すのは無駄だ」と思うかもしれません。
実際にそれは正しいです。
ただ、割る数に素数だけをもってくるようにプログラムを組むのは難しいです。
それだったら多少無駄が発生しても、簡単に作れるやり方を選ぶというのもありです。

どこかで割りきれたら、今度はその商をまた同様の手順で割っていけば良いです。
7429は17で割りきれて商が437になるので、次は

437 ÷ 2が割り切れるかチェック
437 ÷ 3が割り切れるかチェック
437 ÷ 4が割り切れるかチェック
437 ÷ 5が割り切れるかチェック
437 ÷ 6が割り切れるかチェック
437 ÷ 7が割り切れるかチェック
・
・
・

としていきます(本当は、また÷2からスタートする必要はなかったりします)。

上記の方法でやるなら、プログラムは次のような感じになります。

N … 素因数分解したい数
変数temp … 割られる数
変数i … 割る数

temp = N
for(i = 2; i ≦ temp; i = i + 1){
　if(temp ÷ iが割りきれる){
　　変数iの値を表示
　　文字「,」を表示
　　temp = temp ÷ i
　　i = 1
　}
}

C言語またはJava言語がわかれば意味が分かると思います
(質問者さんが何言語を使うか分からないので、疑似的なコードで書きました)。
とても無駄が多いアルゴリズムですが、ソースコードは単純です。

回答No.3

R_Earl

> プログラムを一から作る
> ことになれておらず作ることが
> 出来ません.
> どのように作成していけばよいか
> アドバイスいただけるとうれしいです。

使用するプログラミング言語の入門書や入門webサイト等を見て、
プログラミングをしっかり勉強する方が良いと思います。
計算アルゴリズムをプログラムするなら、
変数と制御文(if文、while文、for文等)を使いこなせるようにして下さい。
while文やfor文等のループ文に関しては、
二重ループまで使いこなせるようになった方がいいでしょう。

プログラムを書くだけでなく、
プログラムを読む練習もした方が良いと思います。
入門書等に記載されているプログラムを読み、
頭の中(または紙に書いて)でそのプログラムを動作させるんです。

素因数分解のプログラムを書く際は、
いきなりプログラムを作るのではなく、
設計図を作ってからプログラム化した方が良いでしょう。
処理手順やその流れを図に書き(これが設計図です)、
それをプログラム化するんです。
フローチャートを用いると、制御文の使い方を把握しやすいと思います
(フローチャートについては参考URLの方を見て下さい)。
厳密なフローチャートを用いる必要はないです。
「この処理をしたら、次はこの処理」とか、
「この処理をしたら、以前実行したこの処理に戻る」とか
そういったことが把握できるようにしていれば良いです。

参考URL：

http://ja.wikipedia.org/wiki/%E3%83%95%E3%83%AD%E3%83%BC%E3%83%81%E3%83%A3%E3%83%BC%E3%83%88

お礼

どのようなプログラムにするか考えてみたものの
2、3、5、7…といったようにどこまで数字を用意して
いいのか分からずいきづまっています。
よろしければサンプルみたいなものをいただけんしでしょうか?

回答No.2

neKo_deux

エラストテネスのふるいは、直接素因数分解を行うアルゴリズムで無いので、置いといても良いかと。

普通に与えられた数を素因数分解する時にどうしますか？
まずは、手計算でやるときにどうなるか？考察してみては。

> 問題の基本的なところから理解できていません。

数値が大きい、計算量が多すぎて出来ないってのは別にして、簡単な数値でも手計算できないのでは、話になりません。
まずは、素因数分解について、教科書をひっくり返すとか。

お礼

素因数分解については理解しているんですが
それをどうプログラムにするのかが難しくて…

回答No.1

R_Earl

> 問題の基本的なところから理解できていません。
>
> 初歩的なところから説明していただける方がいましたら

「基本的なところ」とはどういう意味でしょうか？
何が理解できていなくて、何を説明してほしいのでしょうか？

> 大きな桁数（１０進５０桁程度）の整数を因数分解するアルゴリズム
> （エラトステネスのふるいを除く）に
> ついて調べ、実際に因数分解するプログラムを実装しなさい。

[1]
まず、整数の因数分解(素因数分解？)のアルゴリズムに
どのようなものがあるか調べてみましょう。
何種類もあると思いますが、
全部のアルゴリズムを深く理解する必要はありません。
とりあえずは広く浅く調べる感じで良いです。

[2]
各アルゴリズムの概要を見て、
プログラムで実装するアルゴリズムを1つ決めてください。

[3]
[2]で決めたアルゴリズムの詳細を詳しく調べ、
プログラムの作成をしましょう。

とりあえず[1], [2]の手順が終わらないことにはどうしようもないです。
「性能の良いアルゴリズム」よりも
「自分が取り組みやすいアルゴリズム」の方が良いと思います。

Google等でキーワード「素因数分解　アルゴリズム」で検索してみると、
素因数分解用のアルゴリズムがいくつか見つかります。
アルゴリズム名は載っていても、
アルゴリズムの詳細が書かれていない場合もあるかもしれません。
その場合は図書館で調べてみるのも良いと思います。

お礼

ありがとうございます。
因数分解と書いていたので
何をしていいのかわからず
質問してしまいました。
(素因数分解ですね)笑

いろいろ調べてみたものの
プログラムを一から作る
ことになれておらず作ることが
出来ません.
どのように作成していけばよいか
アドバイスいただけるとうれしいです。

お返事ありがとうございました。