ruby – 范围内最高的独特素因子

发布时间：2020-12-17 02:49:40 所属栏目：百科来源：网络整理

导读：我正在尝试扩展我对Hackerrank练习题的解决方案. 总之,问题是找到范围内的素数因子的最大数量. 对于1..500,对于210而言是4 – 2(1),3(1),5(1),7(1) 对于1..5000,对于2310来说它是5 – 2(1),7(1),11(1) 对于1..50000,对于30030来说它是6 – 2(1),11(1),13(1)

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

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

对于1..500,对于210而言是4 – > 2(1),3(1),5(1),7(1)
对于1..5000,对于2310来说它是5 – > 2(1),7(1),11(1)
对于1..50000,对于30030来说它是6 – > 2(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,这需要永远.

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

解决方法

解

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

有关更多信息,请参阅此整数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)将绰绰有余.如果block返回一个truthy值,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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!