如何使完美的幂算法更有效? [英] How to make perfect power algorithm more efficient?
问题描述
我有以下代码:
def isPP(n):
pos = [int(i) for i in range(n+1)]
pos = pos[2:] ##to ignore the trivial n** 1 == n case
y = []
for i in pos:
for it in pos:
if i** it == n:
y.append((i,it))
#return list((i,it))
#break
if len(y) <1:
return None
else:
return list(y[0])
由于我在内存中存储了太多内存,因此直到2000年为止,它都能完美工作.我该怎么做才能使它有效地处理大量数字(例如50000或100000).我试图在找到一种情况后结束它,但是如果数量很大,我的算法仍然效率太低.
Which works perfectly up until ~2000, since I'm storing far too much in memory. What can I do to make it work efficiently for large numbers (say, 50000 or 100000). I tried to make it end after finding one case, but my algorithm is still far too inefficient if the number is large.
有什么提示吗?
推荐答案
如果存在 b 和 e n 是一个完美的幂. em>,其中 b ^ e = n .例如216 = 6 ^ 3 = 2 ^ 3 * 3 ^ 3是一个完美的幂,但72 = 2 ^ 3 * 3 ^ 2不是一个完美的幂.
A number n is a perfect power if there exists a b and e for which b^e = n. For instance 216 = 6^3 = 2^3 * 3^3 is a perfect power, but 72 = 2^3 * 3^2 is not.
确定一个数字是否为完美幂的诀窍是要知道,如果该数字是一个完美幂,则指数 e 必须小于log2 n ,因为如果 e 更大,那么2 ^ e 将大于 n .此外,仅需测试素数 e ,因为如果数字是复合指数的完美幂,那么它也是复合成分的质数的完美幂;例如2 ^ 15 = 32768 = 32 ^ 3 = 8 ^ 5是理想的立方根,也是理想的第五根.
The trick to determining if a number is a perfect power is to know that, if the number is a perfect power, then the exponent e must be less than log2 n, because if e is greater then 2^e will be greater than n. Further, it is only necessary to test prime es, because if a number is a perfect power to a composite exponent it will also be a perfect power to the prime factors of the composite component; for instance, 2^15 = 32768 = 32^3 = 8^5 is a perfect cube root and also a perfect fifth root.
下面显示的函数isPerfectPower
通过使用牛顿方法首先计算整数根,然后计算结果是否等于 n <,来测试每个小于log2 n 的素数./em>.辅助函数primes
通过Eratosthenes筛子计算素数列表,iroot
通过牛顿方法计算整数 k 根,而ilog
计算整数对数为 b 通过二进制搜索.
The function isPerfectPower
shown below tests each prime less than log2 n by first computing the integer root using Newton's method, then powering the result to check if it is equal to n. Auxiliary function primes
compute a list of prime numbers by the Sieve of Eratosthenes, iroot
computes the integer kth-root by Newton's method, and ilog
computes the integer logarithm to base b by binary search.
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
在我的博客.
这篇关于如何使完美的幂算法更有效?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!