ruby - 范围内最高的唯一素因子

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)< br/>对于 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

解决方案

您示例中的数字只是第一个质数的乘积，如果您想在最大化因子数量的同时最小化乘积，这实际上是有意义的。

看到这个整数 sequence了解更多信息:

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

代码

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一旦 block 返回真值就停止搜索，所以 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