最早写这个的时候是2006年，我还在上高一。用了大概两个中午的时间。

写完之后才发现原来mathn库里已经有了这个方法。

不过令人欣慰的是我写的比它快！

以下是代码

def prime_division(number)
  raise ZeroDivisionError if number == 0
  result, str = [], number.to_s
  if start = str[/0+$/]    #如果以待分解的数以0结尾
    zeroc = str.length - start.length   #直接把所有0分解为2和5
    result = [2,5] * zeroc
    number = str[0,start.length].to_i
  end
  while number % 2 == 0    #如果是偶数，直接除以2
    result << 2     #把2的分解提取出来，后面可以忽略偶数的情况
    number /= 2
  end
  3.step((number**0.5).to_i,2) do |i|
    while number % i == 0
      result << i
      number /= i
    end
  end
  result << number unless number == 1 #加上最后剩下的那个质数
  return result.sort!
end

看Benchmark测试结果（Ubuntu9.10,ruby1.8.7p22）

Benchmark.bm do |x|
  x.report("mathn") { 1.upto(10000) {|i| i.prime_division } }
  x.report("mine") { 1.upto(10000) {|i| prime_division(i) } }
end
 

=> user system total real
mathn 2.400000 0.010000 2.410000 ( 2.511380)
mine 0.630000 0.000000 0.630000 ( 0.661835)

• 相关文章
• 全局相关文章