Skip to content
Advertisement

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

I want to check if number, based on lower and upper bound, has prime divisors only 3 and 5 and number should be multiplication of power of 3 and power of 5. My current solution is this. I want to optimize it, since checking powers with for loops isn’t good way in my opinion. Thanks in advance.

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)

Based on comments I think this is the best way:

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

Advertisement

Answer

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

Over a range of random numbers, we improve its speed by doing:

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

Or we can use a nested loop and combine both divisions into one:

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
User contributions licensed under: CC BY-SA
7 People found this is helpful
Advertisement