Rubyで素因数を求める Rubyでオイラープロジェクトを解こう！Problem3

Rubyで素因数を求める ～Rubyでオイラープロジェクトを解こう！Problem3

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 ?

13195の素因数は、5、7、13および29である。

では600851475143の最大の素因数はいくらか。

素因数 - Wikipedia

素因数は自然数で、ある自然数の約数になる素数である。

最小の素数から対象の数を割って割り切れる素数を順次見つけ出す。

def prime_factor(n)
   prime = 2
   result = []
   loop do
     break if n < prime
     while n.modulo(prime).zero?
       n = n / prime
       result << prime
     end
     prime = next_prime(prime)
   end
   result
 end
 def next_prime(prime)
   _next = prime + 1
   loop do
     return _next if prime?(_next)
     _next += 1
   end
 end
 def prime?(n)
   2.upto(n-1) do |i|
     return false if n.modulo(i).zero?
   end
   true
 end
primes = prime_factor(600851475143) # => [71, 839, 1471, 6857]
primes.last # => 6857

Rubyでフィボナッチ数列を求める ～Rubyでオイラープロジェクトを解こう！Problem2

Problem 2 - Project Eulerより

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

フィボナッチ数列の項は前の2つの項の和である。 最初の2項を 1, 2 とすれば、最初の10項は以下の通りである。

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

数列の項が400万を超えない範囲で、偶数の項の総和を求めよ。

先日解いた問題はここの問題だった。

def fibo_even_sum(max, a=1, b=2)
  sum = 0
  loop do
    break if a >= max
    sum += a if a.even?
    a, b = b, a + b
  end
  sum
end
fibo_even_sum 400_0000 # => 4613732

Rubyで3と5の倍数を求める ～Rubyでオイラープロジェクトを解こう！Problem1

Problem 1 - Project Eulerより

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

10未満の自然数で3または5の倍数であるものは、3、5、6および9であり、それらの合計は23である。

では1,000未満で3または5の倍数であるものの合計はいくらか。

Project Eulerというものがあることを知った。刺激されてやってみた。

def multi_of_three_or_five_upto(max)
   sum = 0
   1.upto(max-1) do |n|
     sum += n if (n % 3).zero? or (n % 5).zero?
   end
   sum
 end
 multi_of_three_or_five_upto 1000 # => 233168