範囲内の余りを除いた数値で割り切れる数の効率的なアルゴリズム

Question

私は2つの数：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は私のために働くようです。私はそれが名前を持っていることを疑う。もう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

2で割り切れます0からnまでのすべての数字の数を見つけることができます。右シフトと呼ばれるビット単位の操作を使用できます。

c = a >> 1; 

10 >> 1は、次の2つの結果の数値を減算し、任意の範囲の間の番号を取得することができます（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