Highest unique prime factors in range

Question

I am trying to scale a solution I have to a Hackerrank practice question.

The question, in summary is, find the max number of prime factors in a range.

For 1..500 it's 4 for 210 -> 2(1), 3(1), 5(1), 7(1)
For 1..5000 it's 5 for 2310 -> 2(1), 3(1), 5(1), 7(1), 11(1)
For 1..50000 it's 6 for 30030 -> 2(1), 3(1), 5(1), 7(1), 11(1), 13(1)

This is my solution

require 'prime'
max = 0
for d in 1..n
    pfs = d.prime_division.count
    max = pfs if pfs > max
end
puts max

This takes forever for n = 10000000000.

I may be looking at the solution from the wrong perspective.
How do I scale this solution?

Answer 1

Solution

The numbers in your example are just the products of the first Primes, which actually makes sense if you want to minimize the product while maximizing the number of factors.

See this integer sequence for more information :

a(n) is the least number N with n distinct prime factors

Code

require 'prime'

n = 50000

p (1..n).find{|i| Prime.take(i+1).inject(:*) > n}
#=> 6

With n = 10000000000 :

p (1..n).find{|i| Prime.take(i+1).inject(:*) > n}
#=> 10

Explanation

It calculates the product of the first i+1 primes until it is greater than n. In this case, i is the desired output.

Note that i is always smaller than n, so searching the Range (1..n) will be more than enough. find stops the search as soon as block returns a truthy value, so it doesn't matter if range.max is n or even Float::INFINITY.

It isn't really efficient to calculate the product for each i, but the solution is found so fast it probably doesn't matter : The product of the first k primes grows faster than k!, so less than O(Γ**-1(n)) steps are needed.

For which number?

If you want to know for which number it is :

p Prime.inject { |product, prime|
  new_product = prime * product
  break product if new_product > n
  new_product
}
#=> 6469693230

or just :

p Prime.take(10).inject(:*)
#=> 6469693230