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>You are counting even numbers. Let's write <code>o</code> for odd, <code>E</code> for even.</p>

<p>If the sequence has an even count of numbers, it is either <code>oEoE...oE</code> or <code>EoEo...Eo</code>, i.e. one half of numbers is always even. If there is odd count of numbers, you can check the first number (or last one) separately and the rest is the known case discussed first.</p>

<pre><code>def count_even(start, end):
    # assert start &lt;= end
    len = end - start
    len2, r = divmod(len, 2)
    if r and start % 2 == 0:
        len2 += 1
    return len2
</code></pre>

python algorithm performance