RubyでProject Euler - Problem 3

Problem 3 (Project Euler) [和訳])

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

素因数分解の問題ですから、素数のリストが必要となります。

Rubyに標準で添付されている「mathn」というライブラリで定義されている"Prime"オブジェクトを使えば簡単なのですが、取りあえず利用しないこととします。

私は下記のように、引数numより大きな直近の素数を返すメソッド"next_prime"で試してみました。

  def next_prime(num)
    loop do
      num += 1
      i = 2
      while i * i <= num
        break if num % i == 0
        i = next_prime(i)
      end
      break if i*i > num
    end
    num
  end

この"next_prime"内で再帰呼び出しをしている関係上、さすがに私のオンボロマシンでは素数が10万に近づく頃には遅さが目立ちます。ただ、この問題に限ってはあっさり答えが得られたのでよしとします。

なお、「mathn」を使っても解答に至るまでの時間はほとんど変わらず、むしろライブラリを読み込む時間が節約できたので却って速いぐらいでした。ばんざい。

ご注意

当分の間、トラックバックの受信を行わないことといたしました。過去に戴いたトラックバックのリストについてはそのまま保持いたします。

トラックバックはありません

コメントはありません。

ご注意

当分の間、JavaScript が有効でないとコメント投稿できないようにします。スパム対策であって、投稿される方の個人情報を取得する目的ではありません。悪しからずご了承ください。