Как ускорить работу кода?

Question

Как ускорить работу кода?

Иван Васильев Ученик (95), открыт 10 часов назад

#1<=a<=10¹⁸
#1<=b<=10
a=int(input())
b=int(input())
c=[]
for x in range(b+1,a+1):
if a%x==0 and ((a/x)*b)%(x-b)==0:
c.append(x)
print(c)

Answer 1

 import math 
 
a = int(input()) 
b = int(input()) 
c = [] 
 
# Найдем делители числа a 
for x in range(1, int(math.sqrt(a)) + 1): 
    if a % x == 0: 
        # Проверяем оба делителя: x и a // x 
        for divisor in {x, a // x}: 
            if divisor > b and ((a // divisor) * b) % (divisor - b) == 0: 
                c.append(divisor) 
 
print(sorted(c))

Answer 2

Тут самое затратное - деление.
Как минимум, хочется a/x вынести в отдельную переменную цикла, и уже от неё проверять есть ли вещественная часть у неё (так выясним был ли остаток от деления), так хотя бы будет только одна операция деления, вместо двух, что уже забустит обход.

Ну и второй мерой ((a/x)*b) заранее сравнить с (x-b). Если первое выражение меньше второго, то там тоже будет остаток от деления не нулевой. Но тут буст будет только когда x будет подходить к a.

Больше оптимизаций тут особо не сделать, кроме переписывания кода на Java или C, т.к. здесь еще питон будет узким горлышком.

Answer 3

 import math
a, b = int(input()), int(input())

# сначала ищем делители числа a - за √a итераций цикла
d = set()
for i in range(1, math.isqrt(a) + 1):
  if a % i == 0: d |= {i, a // i}

# а потом проверяем только найденные делители и выводим результат
print(sorted([x for x in d if x > b and a // x * b % (x - b) == 0]))