Решение

Числа в вашем примере — это просто произведения первых простых чисел, что на самом деле имеет смысл, если вы хотите минимизировать произведение при максимальном количестве факторов.

Дополнительную информацию см. в этой целочисленной последовательности:

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, поэтому поиска в диапазоне (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

Максимальное количество различных простых чисел между 2 и n равно m таким образом, что P(m) <= n < P(m+1), где P(m) = p1*p2*...*pm, pi является ith по величине простым числом. Доказательство (от противного) простое. Предположим, что q1*q2*...*qm+1 — это любая другая последовательность возрастающих простых чисел. Так как pi<= qi для 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]