ruby - 在 Ruby 中迭代大量数字的更快方法是什么？

Question

我正在学习 Ruby，目前这是我的练习:

使用任意一对数字，证明整数 n 是完美幂。如果没有对，则返回 nil。

In mathematics, a perfect power is a positive integer that can be expressed as an integer power of another positive integer. More formally, n is a perfect power if there exist natural numbers m > 1, and k > 1 such that mk = n

目前这是我的代码:

def pp(n)
# [m,k] m^k

idx1=2
  while idx1 <n
  idx2=2
    while idx2<n
        if idx1**idx2 == n
          ans = [idx1,idx2]
          break
        end
     idx2 +=1
    end
    idx1 +=1
  end
return ans

end

我想这样写，对于给定的随机大数，我的 repl.it 不会超时。

提前致谢!

                                      ###Edit###

在 Python 的上下文中提到(How to make perfect power algorithm more efficient?)这个问题。尽管我试图理解它并翻译语法，但我做不到。我希望提出这个问题也能帮助那些学习 Ruby 的人，就像它帮助了我一样。

Answer 1

您可以使用质因数分解:

require 'prime'

def pp(n)
  pd = n.prime_division
  k = pd.map(&:last).reduce(&:gcd)
  return if k < 2
  m = pd.map { |p, e| p**(e / k) }.reduce(:*)
  [m, k]
end

例如 n = 216 你得到 [[2, 3], [3, 3]]，意思是 216 = 2³⋅3³。然后找到指数的最大公约数，即最大可能的指数 k。如果它小于 2，你就输了。否则，从片段中计算基 m。

你的电脑需要大约 4.1 秒来检查从 2 到 200 的数字。我的大约需要 0.0005 秒，检查数字 2 到 400000 大约需要 2.9 秒。