2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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(:*)
\$\endgroup\$
1
\$\begingroup\$

"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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.