Faster algorithm to count how many numbers are divisible by a specific integer in a range

Question

int a,b,c,d=0;
cin>>a>>b>>c;
for (int i=a;i<=b;i++)
 {
 if (i%c==0){d++;}
 }
cout<<d;

So this is the code, a..b is the number range, c is the divisor, and d counts the multiples of c. For example when a=5, b=15, c=3, d equals 4, because "6, 9, 12, 15" are the multiples between 5 and 15. I need to find faster way to do this, can anyone help?

Answer 1

One way is to do it like this (no loops required):

int lower = (a + c - 1) / c; // find lowest divisor (round up)
int upper = b / c;           // find higher divisor (round down)
d = upper - lower + 1;       // get no of divisors

For your example case, lower will be 2, upper will be 5, giving d equal to 4.