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を素因数分解すると、
となります。戻り値は各素因数とそのベキ指数の2要素の配列の配列ということですね。
因みに、prime_divisionメソッドにかなり大きい数の素数を引数に与えると結構処理時間が掛かります。