Project Euler - Problem 3 - gom68の日記

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

Ruby には便利なライブラリがありますね。
singleton method Integer.prime_division

#!/usr/bin/env ruby
require 'mathn'
p 13195.prime_division
p 600851475143.prime_division
# >> [[5, 1], [7, 1], [13, 1], [29, 1]]
# >> [[71, 1], [839, 1], [1471, 1], [6857, 1]]

さすがにつまらないので

自分でも書いてみる。一番簡単な試し割り。

#!/usr/bin/env ruby
prime_div = lambda{|num|
  res = []
  (3..Math::sqrt(num)).step(2) do |i|
    if num % i == 0
      res << i if prime_div.call(i).size == 0
    end
  end
  res
}
p prime_div.call 600851475143
# >> [71, 839, 1471, 6857]

他のアルゴリズムでも書いてみたいが、まずは次に進もう。