Найдите все числа в диапазоне x, y, что 3 и 5 являются их единственными простыми делителями.Например, 3 ^ 4 * 5 ^ 1 = 405, так что это число соответствует. Условия: y> x> 1. Это мое решение, но сложность по времени невелика:
def soleDivisors(x, y):
cnt=0
for i in range(x,y+1):
n=i
while n%3==0 or n%5==0 or n==1:
if n==1:
cnt+=1
break
if n%3==0:
n=n/3
if n%5==0:
n=n/5
return cnt
Предложения по улучшению сложности времени?PS Я пытался добавить n% 2! = 0 к условию while, но это не помогло достаточно сложности.Я думаю об использовании идеи, что достаточно проверить до sqrt (n), но все еще не знаю, как это реализовать.