我正在学习 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 的人,就像它帮助了我一样。
最佳答案
您可以使用质因数分解:
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
。
你的电脑需要大约 4.1 秒来检查从 2 到 200 的数字。我的大约需要 0.0005 秒,检查数字 2 到 400000 大约需要 2.9 秒。
关于ruby - 在 Ruby 中迭代大量数字的更快方法是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48015768/