素因数分解（Ruby） - Camera Obscura

素因数分解は結局素数で順に割っていくしかないのだけれど、素数をわざわざ求めてというのは却って大変ですね。

うまいやり方としては、2 および 3 以上の奇数で割るという方法があります。これは多少のムダは出るけど、全部の数で割るより効率的ですね。さらにうまいやり方があって、2, 3 以上は 5, 7, 11, 13, 17, 19, 23, 25, 29 .... と、ステップ幅を 2 と 4 の交代にして割っていくという方法があります。かしこいですね。これは例えば Ruby でこんなふうに書けます。
prime_factorize.rb

def prime_factorize(n)
  if n <= 1 or !n.class.ancestors.include?(Integer)
    raise ArgumentError, "#{n} incorrect."
  end
  result = {}
  divide = ->(i) {
    while (n % i).zero?
      result[i] = result.has_key?(i) ? result[i] + 1 : 1
      n /= i
    end
  }
  divide[2]
  divide[3]
  k, step = 5, 2
  guard = Math.sqrt(n).to_i
  while n != 1
    divide[k]
    k += step
    return result if k > guard    #高速化
    step = 6 - step
  end
  result
end

if __FILE__ == $0
  p prime_factorize(15141523320)    #=>{2=>3, 3=>3, 5=>1, 7=>2, 11=>1, 19=>1, 37=>2}
end

結果はハッシュで返ります。

なお、素因数分解は Ruby では標準添付ライブラリにあるので、実際はそれを使えばよいですね。ちなみに例えば 69316536495422 の素因数分解をやると、上のプログラムではフリーズしますが（笑）、ライブラリのメソッドだと苦もなく瞬時に素因数分解します。
（※追記：2行付け加えただけで劇的に高速化しました。これだと 69316536495422 の素因数分解でも一瞬です。（4/29））