我正在学习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的上下文中提到了这个问题（How to make perfect power algorithm more efficient?）。尽管我试图理解它并翻译语法，但事实并非如此。我希望提出这个问题也会帮助那些研究Ruby的人，就像它帮助了我一样。
您可以使用素数分解：
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 =23⋅33。然后找到指数的最大公约数，这是最大可能的指数k。如果它小于2，你输了。否则，从碎片计算基础m。
您的PC需要大约4.1秒来检查2到200之间的数字。我需要大约0.0005秒，大约需要2.9秒来检查数字2到400000。
想瞬间解决这样的大数字吗？有一个更短的解决方案？
pp(908485319620418693071190220095272672648773093786320077783229)
=> [29, 41]
然后继续阅读:-)。这将是一个小小的旅程......
让我们首先让你的代码更好，而不用改变逻辑。只需将变量重命名为m和k并使用each循环：
def pp1(n)
ans = nil
(2...n).each do |m|
(2...n).each do |k|
if m**k == n
ans = [m, k]
break
end
end
end
ans
end
检查n最多200我需要大约4.1秒（与你的原始相同）：
> require 'benchmark'
> puts Benchmark.measure { (1..200).each { |n| pp1(n) } }
4.219000 0.000000 4.219000 ( 4.210381)
第一次优化：如果我们找到解决方案，请立即归还！
def pp2(n)
(2...n).each do |m|
(2...n).each do |k|
if m**k == n
return [m, k]
end
end
end
nil
end
可悲的是，测试仍需要3.9秒。下一步优化：如果mk已经太大了，那就不要尝试更大的k！
def pp3(n)
(2...n).each do |m|
(2...n).each do |k|
break if m**k > n
if m**k == n
return [m, k]
end
end
end
nil
end
现在它太快了，我可以在大约相同的时间内运行1000次测试：
> puts Benchmark.measure { 1000.times { (1..200).each { |n| pp3(n) } } }
4.125000 0.000000 4.125000 ( 4.119359)
让我们改为n = 5000：
> puts Benchmark.measure { (1..5000).each { |n| pp3(n) } }
2.547000 0.000000 2.547000 ( 2.568752)
现在我们不再计算m**k，而是使用一个我们可以更便宜地更新的新变量：
def pp4(n)
(2...n).each do |m|
mpowk = m
(2...n).each do |k|
mpowk *= m
break if mpowk > n
if mpowk == n
return [m, k]
end
end
end
nil
end
可悲的是，这几乎没有让它变得更快。但还有另一个优化：当mk太大时，我们不仅可以忘记用更大的k来尝试这个m。如果它对于k = 2太大，即m2已经太大，那么我们也不需要尝试更大的m。我们可以停止整个搜索。我们试试看：
def pp5(n)
(2...n).each do |m|
mpowk = m
(2...n).each do |k|
mpowk *= m
if mpowk > n
return if k == 2
break
end
if mpowk == n
return [m, k]
end
end
end
nil
end
现在这可以在大约0.07秒内完成5000次测试！我们甚至可以在6秒内检查所有数字，最高可达100000：
> puts Benchmark.measure { (1..100000).each { |n| pp5(n) } }
5.891000 0.000000 5.891000 ( 5.927859)
无论如何，让我们看看大局。我们正在尝试m = 2..和每个m我们试图找到一个k，以便m**k == n。嘿，数学有一个解决方案！我们可以将k计算为k = logm（n）。我们开始做吧：
def pp6(n)
(2...n).each do |m|
k = Math.log(n, m).round
return if k < 2
return [m, k] if m**k == n
end
nil
end
再次测量：
> puts Benchmark.measure { (1..100000).each { |n| pp6(n) } }
28.797000 0.000000 28.797000 ( 28.797254)
嗯，慢一点。好吧，另一个想法：让外环为k而不是m。现在对于给定的n和k，我们如何找到m使得mk = n？取第k个根！
def pp7(n)
(2...n).each do |k|
m = (n**(1.0 / k)).round
return if m < 2
return [m, k] if m**k == n
end
nil
end
再次测量：
> puts Benchmark.measure { (1..100000).each { |n| pp7(n) } }
0.828000 0.000000 0.828000 ( 0.836402)
尼斯。 400000怎么样，我的其他答案中的分解解决方案在2.9秒内解决了？
> puts Benchmark.measure { (1..400000).each { |n| pp(n) } }
3.891000 0.000000 3.891000 ( 3.884441)
好吧，这有点慢。但是......通过这个解决方案，我们可以解决非常大的问题：
pp7(1000000035000000490000003430000012005000016807)
=> [1000000007, 5]
pp7(908485319620418693071190220095272672648773093786320077783229)
=> [29, 41]
> pp7(57248915047290578345908234051234692340579013460954153490523457)
=> nil
所有这些结果立即出现。分解解决方案也快速解决了2941案例，但对于10000000075案例和最终的随机类型案例，它很慢，因为因子分解很慢。
附：注意，对数和平方根得到浮点数。这可能导致数量非常大的问题。例如：
irb(main):122:0> pp7(10**308 + 1)
=> nil
irb(main):123:0> pp7(10**309 + 1)
FloatDomainError: Infinity
from (irb):82:in `round'
from (irb):82:in `block in pp7'
from (irb):81:in `each'
from (irb):81:in `pp7'
from (irb):123
from C:/Ruby24/bin/irb.cmd:19:in `<main>'
在这种情况下，那是因为10309对浮动来说太大了：
> (10**309).to_f
=> Infinity
此外，数量足够大可能存在准确性问题。无论如何，您可以通过为对数和根写入整数版本来解决这些问题。但这是另一个问题。