The highest unique underlying factors in the range

Question

I am trying to scale the solution that I have for practicing Hackerrank.

In general, the question is to find the maximum number of simple factors in the range.

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

This is my decision

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

It lasts forever for n = 10000000000.

I can look at the solution from the wrong point of view. How to scale this solution?

Answer 1

Decision

The numbers in your example are just the products of the first prime numbers, which makes sense if you want to minimize the product and maximize the number of factors.

:

a (n) - N n

require 'prime'

n = 50000

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

n = 10000000000:

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

i+1 , n. i .

, i n, Range (1..n) . find , , , range.max n Float::INFINITY.

i, , , , : k , k!, O(Γ**-1(n)) .

?

, :

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

:

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

Answer 2

2 n m , P(m) <= n < P(m+1), P(m) = p 1*p 2*...*p m, p i i th . ( ) . , q 1*q 2*...*q m+1 - . p i<= q i i = 1...m+1, q n.

require 'prime'

def max_number_primes(n)
  return 0 if n < 2
  t = 1
  Prime.each_with_object([]) do |p, a|
    tmp = p*t
    return a if tmp > n
    a << p
    t = tmp
  end
end

max_number_primes(50)              #=> [2, 3, 5]
max_number_primes(50_000)          #=> [2, 3, 5, 7, 11, 13] 
max_number_primes(10_000_000_000)  #=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]