Snippet

project_euler/5.rb

Code:

# Project Euler Problem 5: Smallest Multiple

# https://projecteuler.net/problem=5

# 2520 is the smallest number that can be divided by each of the numbers
# from 1 to 10 without any remainder.
# What is the smallest positive number that is evenly divisible
# with no remainder by all of the numbers from 1 to 20?

def prime_factors(n)
    (2...n).each do |factor|
        if (n % factor == 0) 
            other_factor = n / factor
            return [*prime_factors(factor), *prime_factors(other_factor)]
        end
    end
    return [n]
end

def solve(n)
    freqs = {}
    (2..n).each do |m|
        factors = prime_factors(m)
        for f in factors do
            freqs[f] = [factors.count(f), freqs[f].to_i].max
        end
    end
    product = 1
    freqs.each { |n, e| product *= n ** e }
    return product
end

puts solve(10)
puts solve(20)

Output:

2520
232792560