Jahongir Rahmonov Jahongir Rahmonov - 1 year ago 45
Python Question

Efficient algorithm to find the count of numbers that are divisible by a number without a remainder in a range

Let's say I have two numbers: 6 and 11 and I am trying to find how many numbers between this range are divisible by 2 (3, in this case).

I have this simple code right now:

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

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

return count

Its order of growth is linear, O(N), I believe.

I was wondering if there is a faster algorithm with a constant O(1) performance, or a mathematical formula.

I don't expect a direct answer. The name of such an algorithm would be awesome.

Thank you.

Answer Source

((b - b%m) - a)//m+1 seems to work for me. I doubt it has a name. Another formula that seems to work is (b//m) - ((a-1)//m).

Sample python3 program:

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=" ")