素因数分解

素因数分解は良く知られているように, 2 で割ったあと, 順に奇数で割っていくという, 単純な algorithm が取られている。これ以外の方法があるとすれば, 並列計算が出来るときは, 一方で Eratosthenes の篩(ふるい)を用いて素数表を作っておき, それで順に割っていくということも考えられるが, 並列計算が出来なければ, そのための table をあらかじめ充分大きな素数まで生成しておかねばならない為, programming が面倒になる。

一般に素因数分解にはあまり良い algorithm がないということが, 公開鍵暗号の基礎になっていたりする。

実際の program では次のようになっている

// 以下奇素数の処理。
for(p = 3, step = 2; x >= p; p += step){
	if(x % p == 0){
		while(x % p == 0){
			q++;
			x /= p;
		}
		if(flag == true)	result += " * ";
		else			flag = true;
		result += Long.toString(p) + " ^ " + Long.toString(q);
		q = 0;
	}
	if(p > 5){
		if(step == 2)	step = 4;
		else		step = 2;
	}
}

ここで step という変数を使って見慣れない操作をしているのは, 奇数全部を調べるのを止めて, 3 の倍数のみを skip しているのである。これで多少速くなっているかもしれないが, 表示の algorithm を簡単にする為に通常 p <= x^1/2 までしか調べないのだが, そこをさぼって x に等しくなるまで調べているので, それほど速くはなっていないのではないかと思われる。

尚, 最初, for 文中の最初の if 文の closed brace "}" の位置を間違えていた為, とんでもない誤動作をして, debug に非常に時間がかかってしまった。

Wednesday, 3rd May, 2000.