Javaで素因数分解メソッドを作る - 文系プログラマーのプログラミング備忘録

ある数を素因数分解して、その結果を返すメソッドを作ります。

素因数分解とは、Wikipediaによれば

・ある正の整数を素数の積の形で表すこと

だそうです。ある数Nを

・N = 2^a * 3^b * 5^c * ......

を表すということですね。今回は、N をこの形で出力するメソッドを作ります。

さて、素因数分解をするにあたっては、さまざまなアルゴリズムが存在しています。その中でも今回は、身の丈にあったアルゴリズムということで、以下の試し割り法を使うことにしました。

ja.wikipedia.org

試し割り法というのは、読んで字のごとく、N を 2,3,5,7...... と順番に素数で割っていって、それぞれ何回割れるかを調べていくアルゴリズムです。

試し割り法をおこなうには、N を i で割る際に i が素数であるかどうか判定する必要があります。
素数判定には、以下のメソッドを用います。

//素数判定メソッド
static boolean isPrime (int n) {
	if (n==2) return true;
	if (n<2 || n%2==0) return false;
	int d = (int)Math.sqrt(n);
	for (int i=3; i<=d; i+=2) {
		if(n%i==0){return false;}
	}
	return true;
}

この素数判定メソッドを踏まえて、実際に作成した素因数分解メソッドが以下になります。

//素因数分解メソッド
static TreeMap<Integer, Integer> primeFactorization (int n) {

	TreeMap<Integer, Integer> map = new TreeMap<>();
	int sq = (int)Math.sqrt(n);

	//nが素数ならn^1の形で返す
	if (isPrime(n) == true) {
		map.put(n, 1);
		return map;
	}

	for (int i=2; i<=sq; i++) {
		//n<iなら明らかにnをiで除算できないので終了（ループを余計に回さない）
		if (n < i) break;

		//iが素数なら、nをiで何回除算できるか、その回数をmapに記録する
		if (isPrime(i) == true) {
			int count = 0;
			while (n%i == 0) {
				n /= i;
				count++;
			}
			if (count > 0) {　//1回以上割れた場合のみ、mapに記録する
				map.put(i, count);
			}
		}

	}

	//2～sqrt(n)で除算した結果、なお残った数をmapに追加する
	if (n != 1) map.put(n, 1);

	return map;

}

処理結果は Map に保存します。例えば n が 2 で5回割り切れるなら、key=2, value=5 を Map に追加します。

i をいちいち素数かどうか判定するのではなく、あらかじめ sqrt(n) 以下の素数のリストを作っておいたほうがいいような気もしますが、今回はとりあえず形だけ作ることを目標にしたので、処理速度面はあまり考えていません。Map も使っちゃってますしね。

メソッドの冒頭では、n がもともと素数であるかどうかを以下の部分で判定しています。

//nが素数ならn^1の形で返す
if (isPrime(n) == true) {
	map.put(n, 1);
	return map;
}

これを入れないと、桁の大きい素数を受け取ったときに、計算量が多くなりすぎてしまうようです。
例えば、競プロでは有名な 10^9+7の場合。
上記の部分を書かずに処理すると計算量が約30万となりますが、上記の部分を書くことで約1万まで抑えることができます。

では、実際に作成した素因数分解メソッドを動かしてみます。
入力と出力は、以下のように記述しておこないます。

void solve () {

	//入力
	int n = 55440;
	TreeMap<Integer, Integer> map = primeFactorization(n);

	//出力
	out.print(n+" = ");
	int i = 0;
	for (Map.Entry<Integer, Integer> e: map.entrySet()) {
		if (i == 0) out.print(e.getKey()+"^"+e.getValue());
		else out.print(" * "+e.getKey()+"^"+e.getValue());
		i++;
	} out.println();

}