Project Euler #5 in Ruby with Prime class

Question:

Smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

I tackle the problem with reference to how I solved #3, which is using the prime_division method in the Prime class. I have created an array of prime_divisions for 2..20.

The array looks like this:

[[2, 1], [3, 1], [2, 2], [5, 1], [2, 1], [3, 1], [7, 1], [2, 3], [3, 2], [2, 1], [5, 1], [11, 1], [2, 2], [3, 1], [13, 1], [2, 1], [7, 1], [3, 1], [5, 1], [2, 4], [17, 1], [2, 1], [3, 2], [19, 1], [2, 2], [5, 1]]

And after using the .uniq method and sorting it, it shortens to the following:

[[2, 1], [2, 2], [2, 3], [2, 4], [3, 1], [3, 2], [5, 1], [7, 1], [11, 1], [13, 1], [17, 1], [19, 1]]

which is then easy, I just multiply the highest index for each factor:

$2^4 times 3^2 times 5 times 7 times 11 times 13 times 17 times 19 = 232792560$

At this last stage, the right thing to do would be to multiply the highest power of each factor. I couldn’t figure out how to do that in an elegant way. However, I realised that coincidentally, the number of occurrences of each factor in array b always equals to the highest power. But I would welcome a more elegant solution to this.

require 'prime'

a=[]
c= 1


# Get all prime factors from 2 to 20
(2..20).each do |n|
    a = a.concat(Prime.prime_division(n))
end

# Select only the unique elements and extract the factor, multiply them all
b = a.uniq
b.each do |n|
    if n[0] != 0 || !n[0].nil?
        c = c * n[0]
    end
end 

puts c

Shortening

Building arrays by concatenating results to an empty list is inelegant. You should strive to define the result “all at once”:

a = (2..20).flat_map { |n| Prime.prime_division(n) }

Usually, one-blocks should be written using { … }. Use do … end if it spans multiple lines.

In the second half, n[0] should always be a prime number, so I don’t see why it would ever be 0 or nil. Therefore, you could finish up by writing

puts a.uniq.map { |prime, power| prime }.inject(:*)

Refining

To find the maximum power of each prime, use Enumerable#group_by.

require 'prime'

puts (2..20).flat_map { |n| Prime.prime_division(n) }
            .group_by { |prime, power| prime }.values
            .map { |factors| factors.max_by { |prime, power| power } }
            .map { |prime, power| prime ** power }
            .inject(:*)

“Smallest positive number that is evenly divisible by all of the numbers” is known as the Lowest Common Multiple. Does Ruby have such a method? Yes she does. Integers have a lcm method, which allows for:

p (1..20).inject(:lcm)