# 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)