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_division
s 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