2015/06/24

最大素因数を求める Project Euler Problem 3

最近寒かったり、汗ばむくらい暖かかったり、不安定な気候に体がついていけてない。なので、GWは室温が安定してるお家に引きこもって遊んでおります。




Project Eulerを利用して言語を学ぶ


というわけでrubyとhaskellの練習のために、ProjectEulerの問題を解いてます。この2つで同じ問題を解くことで、命令型と関数型プログラミングの違いを理解することが狙いです。このサイトはプログラミングのお題が豊富ですが、アルゴリズムに親しくない自分にとっては最初の3問目ですでに結構時間かかってしまう。





約数かつ素数で、最大の数は？


Project EulerのProblem3はこんな問題。




13195の約数のうち、素数である数は5,7,13,29。では600851475143の約数かつ素数のうち、最大の数は？




素数といえばお題としては定番なんでしょうね。





コーディング




今回はrubyで解いてみましたが、まず解き方の方針を以下のようにしました。






  1. 600851475143の約数を列挙する

  2. 1で求めた約数のうち、素数であるものを抽出

  3. 2の中から最大数を求める

それで作成したコードは次のようになりました。


def prime? n
return true  if n == 2
return false if (n < 2) || (n & 1 == 0)
return (2**(n-1))%n == 1
end

def find_max_prime_factor n
head = (n/2).to_i
div_list = []
head.downto(2) do |i|
div_list.push(i) if n%i == 0
end

div_list.each do |x|
return x if prime?(x)
end

return false
end

p find_max_prime_factor 600851475143

find_max_prime_factorメソッドで最大素因数を求めます。素数の判定にはフェルマーの小定理を使い、prime?メソッドを作りました。この素数判定、当初はエラトステネスのふるいで行おうとしたのですが、計算量が多くて今回のお題のような桁の大きな数については時間がかかります。Project Eulerでは作成したプログラムに対して「処理時間が1分以内であること」が

定められています。フェルマー小定理については、こちらのサイト様を参考にしています。あとの工夫点としては、




  1. 約数のは0～n/2の範囲で降順に列挙

  2. 約数リストの先頭から素数判定を行い、最初に真となったものが最大値となる(1で降順に列挙しているため)

というかんじです。続いてhaskellで解いてみようと思うのですが、全然イメージがわかない残念な感じです。すごいH本を買ってきたので、まず言語自体の基本を抑えないといけませんねぇ。




参考






投稿者 時刻:

0 件のコメント:

コメントを投稿

登録: コメントの投稿 (Atom)