Эффективный алгоритм для нахождения числа чисел, делящихся на число без остатка в диапазоне

Question

Предположим, у меня есть два числа: 6 и 11, и я пытаюсь найти, сколько чисел между этим диапазоном делится на 2 (3, в этом случае).

У меня есть этот простой код прямо сейчас:

def get_count(a, b, m): 
    count = 0 

    for i in range(a, b + 1): 
     if i % m == 0: 
      count += 1 

    return count 

Ее порядок роста является линейным, O (N), я считаю.

Мне было интересно, существует ли более быстрый алгоритм с постоянной производительностью O (1) или математической формулой.

Я не ожидаю прямого ответа. Название такого алгоритма было бы удивительным.

спасибо.

Answer 1

((b - b%m) - a)//m+1, похоже, работает на меня. Я сомневаюсь, что у него есть имя. Другая формула, которая, похоже, работает (b//m) - ((a-1)//m).

Пример программы python3:

def get_count(a, b, m): 
    return (((b - (b % m)) - a) // m) + 1 

for i in range(5, 8): 
    for j in range(10, 13): 
     print(get_count(i, j, 2), end=" ") 
    print() 

Answer 2

Чтобы найти количество всех чисел от 0 до п, которые делятся на две части. вы можете использовать побитовое действие, называемое правым сдвигом;

c = a >> 1; 

10 >> 1 эквивалентен полу (10/2)

Вы можете вычесть два результирующих цифры и получить номера между любым диапазоном.

Это будет работать в O (1). Надеюсь это поможет.

Answer 3

Вы считаете даже цифры. Давайте напишем o для нечетных, E для четного.

Если последовательность имеет четное количество чисел, то она равна oEoE...oE или EoEo...Eo, то есть одна половина номеров всегда четная. Если есть нечетное количество чисел, вы можете проверить первое число (или последнее) отдельно, а остальное - это известный случай, обсуждаемый первым.

def count_even(start, end): 
    # assert start <= end 
    len = end - start 
    len2, r = divmod(len, 2) 
    if r and start % 2 == 0: 
     len2 += 1 
    return len2