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