ヽ|∵|ゝ(Fantom) の 開発blog? ホーム » Java »【Java】素因数分解をする

【Java】素因数分解をする  


 素数関連のアルゴリズムとして、簡単な「素因数分解」もやってみよう。といってもこれまでとほとんど変わらないので、解説は必要なら「試し割り」や「エラトステネスの篩」の記事を見て欲しい。コードも少し手を加えただけの代物なので、必要あれば色々改造して使うと良いだろう。

●素因数分解のリストを作る
import java.util.ArrayList;
import java.util.List;

/**<h1>素因数分解のリストを作る</h1>
* @param n : 素因数分解する値 (>=0)
* @return<b>List<Integer></b> : 素因数分解のリスト
*/
public static final List<Integer> primeFactor(int n) {
final List<Integer> list = new ArrayList<Integer>();
if (n < 2) { //n が2以上とわかっていれば、ここは不要
return list;
}

while (n != 1 && n % 2 == 0) { //2で割り切れるだけ割る
list.add(2);
n >>>= 1; //÷2 の代わり
}

for (int i = 3; i * i <= n; i += 2) { //奇数のみ [O(√n[/2])で可]
while (n % i == 0) {
list.add(i);
n /= i;
}
}

if (n != 1) {
list.add(n);
}
return list;
}


//メインでは...
int n = 240;
List<Integer> factor = primeFactor(n);
for (int v : factor) {
System.out.print(v + " ");
}

2 2 2 2 3 5

 今回も素数系のアルゴリズムの関連になるため、ポイントは変わらない(というより本当に同じようなコードばかりで書けることがわかる(笑))。念のため n が0と1のときにも対応させてあるが、素数とは「1とそれ自身でしか割り切れない、2以上の整数」と定義されているので、不要なら0と1ははじめから除外しても良い(2以上を使うこと前提ならば、関数内冒頭の「if (n < 2)~」は削除しても構わない)。

 上記の例では個々の素因数を要素にしているが、それぞれの値とその個数のように連想配列にするのも良い。以下の例では戻値の型を変更しただけで、内容は同じものだ。用途によって使い分けるのが良いだろう。

●素因数分解の連想配列を作る
import java.util.HashMap;
import java.util.Map;

/**<h1>素因数分解の連想配列を作る</h1>
* @param n : 素因数分解する値 (>=0)
* @return<b>Map<Integer, Integer></b> : <値, 個数> の連想配列
*/
public static final Map<Integer, Integer> primeFactorMap(int n) {
final Map<Integer, Integer> map = new HashMap<Integer, Integer>();
if (n < 2) { //n が2以上とわかっていれば、ここは不要
return map;
}

while (n != 1 && n % 2 == 0) { //2で割り切れるだけ割る
if (map.containsKey(2)) {
map.put(2, map.get(2) + 1);
} else {
map.put(2, 1);
}
n >>>= 1; //÷2 の代わり
}

for (int i = 3; i * i <= n; i += 2) { //奇数のみ [O(√n[/2])で可]
while (n % i == 0) {
if (map.containsKey(i)) {
map.put(i, map.get(i) + 1);
} else {
map.put(i, 1);
}
n /= i;
}
}

if (n != 1) {
map.put(n, 1);
}
return map;
}


//メインでは...
int n = 240;
List<Integer> factor = primeFactorMap(n);
for (Map.Entry<Integer, Integer> e : factor.entrySet()) {
System.out.print(e.getKey() + " = " + e.getValue() + ", ");
}

2 = 4, 3 = 1, 5 = 1,

 戻値は「素因数の値=その個数」となる。つまり、上の例の場合「素因数の 2 が 4 個、3 が 1 個、 5 が 1 個(2×2×2×2×3×5 = 240)」という意味になる。

 素因数分解にも「ポラード・ロー素因数分解法」や「数体ふるい法」などのより高度なアルゴリズムもある。ググッてみれば pdf の資料などがいくつか見つかるので、興味があれば調べてみるのも良いだろう。だがまぁ、オンラインジャッジの出題などではこの程度のアルゴリズムでも十分いける。

(参考)
素因数分解アルゴリズム
数体篩法


(関連記事)
【Java】素数判定①(試し割り法)
【Java】素数判定②(エラトステネスの篩(ふるい))
【Java】素数判定③(サンダラムの篩(ふるい))
【Java】素数判定④(アトキンの篩(ふるい))


■参考になる書籍


スポンサーサイト

category: Java

thread: プログラミング

janre: コンピュータ

tag: 算術関数  素数 
tb: 0   cm: --


トラックバック

トラックバックURL
→http://fantom1x.blog130.fc2.com/tb.php/213-bfafafa7
この記事にトラックバックする(FC2ブログユーザー)

プロフィール

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR

▲ Pagetop