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

Question

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

使用任何一对数字,证明整数n是一个完美的力量.如果没有对,则返回nil.

在数学中,完美的幂是一个正整数,可以表示为另一个正整数的整数幂.更正式地说,如果存在自然数m> 1并且k> 1使得mk = n,则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的上下文中提到了这个问题(如何使完美的幂算法更有效？).尽管我试图理解它并翻译语法,但事实并非如此.我希望提出这个问题也会帮助那些研究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从碎片计算基数.

您的PC需要大约4.1秒来检查2到200之间的数字.我需要大约0.0005秒,大约需要2.9秒来检查数字2到400000.