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>To find the count of all numbers between 0 and n that are divisible by two. you can use the bitwise operation called right shift;</p>

<pre><code>c = a &gt;&gt; 1;
</code></pre>

<p>10 >> 1 is equivalent to floor(10/2)</p>

<p>You can subtract the two resultant numbers and get numbers between any range.</p>

<p>This will work in O(1). Hope this helps.</p>

python algorithm performance