python - 如何确定某个数字的分子和幂？

您可以通过迭代幂并找到产生整数的最高第 n 个根来做到这一点。

from math import log
def findPower(N):
    if N == 0: return (0,1)  # support zero
    if N < 0:                # support negatives
        r,p = findPower(-N)
        return (-r,p) if p%2 else (N,1)

    for power in range(int(log(N,2)),1,-1): # int(log(N,2))=N.bit_length()-1
        root = int(N**(1/power))
        for r in range(root-1,root+2):
            if r**power == N: return (r,power)

    return (N,1)

print(findPower(81))               # (3,4)
print(findPower(8))                # (2,3)
print(findPower(371293))           # (13,5)
print(findPower(29**7))            # (29,7)
print(findPower(-232630513987207)) # (-7, 17)

请注意，对于 n = -1、0 或 1，这将返回 (n,1)，即使它们都有无限数量的解。它还仅返回偶数幂的正基数。

[编辑]上述功能受到浮点数表示能力的限制。它会阻塞非常大的整数。

这是一种替代方法，它支持 Python 的“无限大小”整数，使用二进制搜索计算第 n 个根，并使用结果指数的素数进行优化。

整数根计算

# integer nth root of number X, Returns None if no exact root
rootMod7 = { p:{d**p%7 for d in range(1,8)} for p in range(1,7) }
def intRoot(X,n):
    if n==1 or X==1: return X
    odd,bits  = X&1, X.bit_length()           # odd/even and bit magnitude
    if X%7 not in rootMod7[(n-1)%6+1]: return # mod 7 match possible roots
    lo,hi = 1<<(bits//n),1<<(bits//n+1)       # starting range on log(X,n)
    while lo<=hi:
        root = (lo+hi)//2                     # binary search
        if root&1 != odd: root += root < hi   # odd/even must match X's
        delta = X - root**n
        if delta == 0: return root
        if delta<0 : hi = root - 2  # adjust range
        else:        lo = root + 2  # on odd/even boundaries   
    return None

素数生成器

def quickPrimes(N):
    isPrime = [False,True]*(N//2+1)
    primes  = [2]
    for p in range(3,N+1,2):
        if not isPrime[p]: continue
        primes.append(p)
        isPrime[p*p:N+1:p] = (False for _ in range(p*p,N+1,p))
    return primes

大量数字的解决方案

# finds base and power where base**power == N    
def basePower(N):
    base,power = (N,1) if N>=0 else basePower(-N)
    if N<1: return (-base,power) if power%2 else (N,1)
    maxPower   = N.bit_length()
    for p in reversed(quickPrimes(maxPower)):
        if p>maxPower: continue
        root = intRoot(base,p)
        while root:  # prime factorisation of exponents
            maxPower = maxPower//p + 1
            base,power = root,power*p 
            root = intRoot(base,p)
    return base,power

此版本可以在合理的时间内处理大量数据。

例如：

basePower(1522756**5553) # (1234, 11106) in 46  seconds, 34,333 digits
basePower(12345**12345)  # (12345,12345) in 159 seconds, 50,510 digits

[EDIT2]使用素数分解的更好解决方案：

您可以找到素数并取素数的最大公分母 (gcd)。

例如 216000 的素数因数是 2^6、3^3、5^3，所以幂是 3。对于每个素数，保持 count/3 作为计算底数的幂：2^2 * 3^1 * 5 ^1 = 60。所以 216000 = 60^3

def primeFactors(N):   # returns dictionary of {prime:count}
    result = dict()
    p = 2              # p is a candidate prime factor   
    while p*p<=N:      # prime candidates up to √N (remaining N) 
        while N%p == 0:   # count prime factors
            result[p] = result.get(p,0)+1 
            N //= p       # by removing factors, only primes will match
        p += 1 + (p&1)    # next potential prime
    if N>1: result[N] = 1 # anything remaining after √N is a prime
    return result

def gcd(a,b=0,*c):                    # gcd using Euclid's algorithm
    if c: return gcd(gcd(a,b),*c)     # for multiple values
    return a if not b else gcd(b,a%b) # Euclidian division version

def findPower(N):
    counts = primeFactors(N)       # {prime factor: count}
    power  = gcd(*counts.values()) # power is gcd of prime counts
    base   = 1                  
    for f,c in counts.items():     # compute base
        base *= f**(c//power)      # from remaining prime powers
    return base,power

这比之前的大整数解决方案要快得多：

    findPower(12345**12345))     # (12345,12345) in 2.8 seconds

python - 如何确定某个数字的分子和幂？

问题描述

解决方案

推荐阅读