【Project EulerにRubyで挑戦シリーズ】問3:Largest prime factor

スポンサーリンク

今回の問題

Largest prime factor

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

13195 の素因数は 5, 7, 13, 29 である。
600851475143 の素因数のうち最大のものを求めよ。

書いた内容

ライブラリを探してみた

600851475143を素因数分解してその最大値を求める問題です。
とりあえず楽できないかとライブラリを探してみたらありました!
Primeライブラリ

素数や素因数分解を扱うライブラリのようで、
intger型のオブジェクトに対してprime_divisionメソッドを使えば、
素因数とその指数から成るペアを要素とする配列を2次元配列の形でそれぞれ返してくれるそうです。

各要素の配列 [n,e] は、
n が レシーバ の素因数、e が n**e で レシーバ を割り切る最大の自然数 e
というわけです。

require 'prime'
p Prime.prime_division(600851475143)
#=> [[71, 1], [839, 1], [1471, 1], [6857, 1]]

つまり、
600851475143 = 71の1乗 × 839の1乗 × 1471の1乗 × 6857の1乗
だと言う結果を示しています。

2次元配列最後の要素の第一要素を取り出したい

この時点で求める解は 6857 と分かりましたが、
どうせなら 6857 を返してくれるコードを書きたい!ということで続けます。

「2次元配列最後の要素の第一要素を取り出したい」という言葉通り、
2次元配列に対してlastメソッドで、 [6857, 1] という配列を取り出し、
firstメソッドで 6857 を取り出してみました。

それ以外にも、mapメソッドのブロック内部でfirstメソッドを使うことで
[71, 839, 1471, 6857] という配列を取り出して加工する方法もありました。

ということで複数の記載方法を掲載しておきます。

require 'prime'
puts Prime.prime_division(600851475143).last.first #=> 6857

puts Prime.prime_division(600851475143).map(&:first).max #=> 6857
# 右記と同じ Prime.prime_division(600851475143).map { |n| n.first }.max

puts Prime.prime_division(600851475143).map(&:first).last #=> 6857
# 右記と同じ Prime.prime_division(600851475143).map { |n| n.first }.last

ライブラリを用意してくれているのがありがたいです。
今回は以上です。

※Project Eulerのリポジトリ

この記事の内容が役に立ったと思いました、SNSで記事を共有していただけますと幸いです。