范围内最高的独特素因子

Question

我正在尝试扩展我对Hackerrank 练习题的解决方案.

总之,问题是找到范围内的素数因子的最大数量.

因为1..500它是4 for 210 -> 2(1), 3(1), 5(1), 7(1)
因为1..5000它是5 for 2310 -> 2(1), 3(1), 5(1), 7(1), 11(1)
为了1..50000它6 for 30030 -> 2(1), 3(1), 5(1), 7(1), 11(1), 13(1)

这是我的解决方案

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

这需要永远n = 10000000000.

我可能从错误的角度看待解决方案.
如何扩展此解决方案？

Answer 1

解

您的示例中的数字只是第一个Primes的产品,如果您希望在最大化因素数量的同时最小化产品,这实际上是有意义的.

有关更多信息,请参阅此整数序列:

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