或るプログラマの開発日記

日々の勉強したことの備忘録なんかに使っていきます

Rubyで素因数分解を行う

素因数分解C言語Javaで行う場合、自力で小さい素数から順に割っていく方法なんかが取られるかと思いますが、Rubyでは標準モジュールに素因数分解の処理が用意されていたのでメモ。

Primeクラスのprime_divisionメソッド

Rubyでは、このメソッド一発で素因数分解が出来ます。Ruby便利すぎる。。

使い方
require "prime"
p Prime.prime_division(360)#=>[[2, 3], [3, 2], [5, 1]]
p Prime.prime_division(1683)#=>[[3, 2], [11, 1], [17, 1]]
p Prime.prime_division(65536)#=>[[2, 16]]
p Prime.prime_division(8635844967113809)#=>[[89652331, 1], [96325939, 1]]

prime_divisionメソッドは2次元配列で結果を返してきます。

例として360を素因数分解すると、
360=2^3 \times 3^2 \times 5^1
となります。戻り値は各素因数とそのベキ指数の2要素の配列の配列ということですね。

因みに、prime_divisionメソッドにかなり大きい数の素数を引数に与えると結構処理時間が掛かります。