范围内最高的唯一素因子

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

解决方案

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

有关详细信息，请参阅此整数 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 一旦阻止 returns 一个真值就停止搜索，所以 range.max 是 n 甚至 Float::INFINITY.[=28 都没有关系=]

计算每个 i 的乘积并不是很有效，但是找到解决方案的速度如此之快，这可能无关紧要：前 k 个素数的乘积比 [=24 增长得更快=]，因此需要不到 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₁*p₂*...*p_m,p_i 是第 i 大素数。证明（反证法）很简单。假设q₁*q₂*...*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]

范围内最高的唯一素因子

Highest unique prime factors in range

ruby

math

prime-factoring

解决方案

代码

说明

哪个号码？