检查数字 3^x * 5^y 的有效方法

Question

我想检查基于下限和上限的数字是否只有 3 和 5 的质因数，并且数字应该是 3 的幂和 5 的幂的乘积。我目前的解决方案是这样的。我想对其进行优化，因为在我看来，使用 for 循环检查幂不是一个好方法。提前致谢。

def checkNum(x):
    for i in range(1,50):
        for j in range(1,50):
            return x == (3**i) * (5**j)


def printResult(l, r):
    for i in range(l,r):
        if checkNum(i):
            print(i)

根据评论，我认为这是最好的方法：

def checkNum(x):
    while x%3==0:
        x = x //3
    while x%5==0:
        x = x//5
    return x==1

Answer 1

I want to optimize it, since checking powers with for loops isn't good way in my opinion.

在随机数范围内，我们通过以下方式提高其速度：

def checkNum0(x):
    if x % 2 == 0:  # eliminate half the numbers in one test!
        return False

    while x % 15 == 0:  # speed up the process
        x = x // 15

    while x % 5 == 0:
        x = x // 5

    while x % 3 == 0:
        x = x // 3

    return x == 1

或者我们可以使用嵌套循环，将两个部分合二为一：

def checkNum(x):
    if x % 2 == 0:  # eliminate half the numbers in one test!
        return False

    for divisor in (15, 5, 3):
        while (quotient_remainder := divmod(x, divisor))[1] == 0:
            x = quotient_remainder[0]

    return x == 1

检查数字 3^x * 5^y 的有效方法

Efficient way for checking number 3^x * 5^y

python

for-loop

primes

exponent