Python中如何判断一个大整数是否是3的幂？

Question

我试图确定给定的正整数（ N ）是否是 3 的幂，即是否存在一个非负整数（ x ）使得（ 3^x = N ）。挑战在于 ( N ) 可能非常大，最多可达 ( 10^7 ) 位。

这是我要实现的逻辑：

1. 如果 ( N ) 小于或等于 0，则返回 -1。
2. 使用对数计算来确定 ( N ) 是否为 3 的幂。
3. 如果是3的幂，则打印(x)的值；否则，打印 -1。

我尝试了以下代码，但我担心大整数的精度问题：

import math

def is_power_of_three(N):
    if N <= 0:
        return -1
    log3_N = math.log10(N) / math.log10(3)
    if abs(log3_N - round(log3_N)) < 1e-10:
        return int(round(log3_N))
    else:
        return -1

# Example usage:
N = int(input("Enter a number: "))
print(is_power_of_three(N))

问题：

1. 是否有更有效的方法来检查 ( N ) 是否为 3 的幂，特别是对于非常大的值？
2. 计算如此大的整数的对数时，如何处理 Python 中的精度问题？
3. 是否有其他方法可以实现相同的目标？

Answer 1

你的函数应该返回一个布尔值。返回

-1

的“哨兵值”似乎很奇怪且不惯用。

使用对数的另一种方法是使用重复除法。因为我们除以基数，所以运行时复杂度是对数的。

def is_power_of(n, d):
    if n == 1: return True
    if n < d: return False
    while n >= d:
        if n % d: return False
        if n == d: return True
        n //= d
    return False