Как оптимизировать программу?

Question

[vladoss_096]

A, B, C, D = map(int, input().split())
k = 0
for count in range(A, B):
    if count % C != 0 and count % D != 0:
        k += 1
print(k)

Вот сама программа. Как сделать, чтобы программа работала быстрее?

Comments

[kurrbanov]

А можно условие задачи, пожалуйста?

Answer 1

[Vindicar]

Словесную формулировку задачи можно? Потому что тут мало что можно оптимизировать...
Разве что попытаться вычислить количество подходящих чисел без перебора.
Например, наименьшее число, большее или равное A, делящееся на C, будет
AC = (A // C + (1 if A % C else 0)) * C
Аналогично, наибольшее число, меньшее B, делящееся на C, будет
BC = ((B-1) // C) * C
Тогда число чисел, делящихся на C, в интервале A...B будет
XC = (BC - AC) // C + 1

По аналогии можно найти XD для D, после чего искомое количество чисел можно оценить как (B - A) - XC - XD.
Но трудность в том, что некоторые числа могут делиться и на C, и на D. Если так, то указанная оценка будет больше правильной, и нужно будет вычислить XCD = (BCD - ACD) // (CD) + 1, где BCD и ACD вычисляются аналогично вышеуказанным AC и BC, только для величины CD - наименьшего общего кратного C и D. В итоге получим ответ (B - A) - XC - XD + XCD.

Comments

[vladoss_096]

Задаются четыре целых числа A, B, C и D.
Найдите количество целых чисел между A и B(включительно), которые не делятся ни на C, ни на D

[Vindicar]

vladoss_096, ну тогда можно попробовать моё решение. Составлял в уме. так что мог накосячить, но идею передаёт, надеюсь.