<p>如果存在A<em>b</em>和<em>e</em>,则一个数<em>n</em>是一个理想幂。例如216=6^3=2^3*3^3是一个完美的幂,但72=2^3*3^2不是。在</p>
<p>如果小于em>的幂是小于em>的,那么要知道这个数是</em>的。此外,只需要测试素数的素数,因为如果一个数是复合指数的完美幂,那么它也将是复合分量素因子的完美幂;例如,2^15=32768=32^3=8^5是完美的立方根,也是完美的第五根。在</p>
<p>下面所示的函数<code>isPerfectPower</code>首先用牛顿方法计算整数根,然后对结果进行验证,以检查它是否等于<em>n</em>,从而测试每个小于log2<em>n</em>的素数。辅助函数<code>primes</code>用埃拉托斯thenes的筛子计算一个素数列表,<code>iroot</code>用牛顿法计算整数<em>k</em>次根,<code>ilog</code>通过二元搜索计算出以<em>b</em>为底的整数对数。在</p>
<pre><code>def primes(n): # sieve of eratosthenes
i, p, ps, m = 0, 3, [2], n // 2
sieve = [True] * m
while p <= n:
if sieve[i]:
ps.append(p)
for j in range((p*p-3)/2, m, p):
sieve[j] = False
i, p = i+1, p+2
return ps
def iroot(k, n): # assume n > 0
u, s, k1 = n, n+1, k-1
while u < s:
s = u
u = (k1 * u + n // u ** k1) // k
return s
def ilog(b, n): # max e where b**e <= n
lo, blo, hi, bhi = 0, 1, 1, b
while bhi < n:
lo, blo, hi, bhi = hi, bhi, hi+hi, bhi*bhi
while 1 < (hi - lo):
mid = (lo + hi) // 2
bmid = blo * pow(b, (mid - lo))
if n < bmid: hi, bhi = mid, bmid
elif bmid < n: lo, blo = mid, bmid
else: return mid
if bhi == n: return hi
return lo
def isPerfectPower(n): # x if n == x ** y, or False
for p in primes(ilog(2,n)):
x = iroot(p, n)
if pow(x, p) == n: return x
return False
</code></pre>
<p>关于<a href="https://programmingpraxis.com/2012/03/13/perfect-power-predicate/" rel="nofollow">my blog</a>的完全幂谓词还有进一步的讨论。在</p>