Efficient algorithm to find the count of numbers that are divisible by a number without a remainder in a range
<p>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).</p>

<p>I have this simple code right now:</p>

<pre><code>def get_count(a, b, m):
    count = 0

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

    return count
</code></pre>

<p>Its order of growth is linear, O(N), I believe. </p>

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

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

<p>Thank you. </p>

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

<p>Sample python3 program:</p>

<pre><code>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()
</code></pre>

python algorithm performance