CODEWITHSUNDEEP
c++
Konrad
Konrad

Reputation: 49

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

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?

Upvotes: 5

Views: 4018

Answers (3)

Tristan Brindle
Tristan Brindle

Reputation: 16824

An untested off-the-top-of-my-head algorithm to find all the proper divisors of a positive integer...

Let the number you want to find the divisors for be N.

  1. Let i = 2
  2. If N % i == 0, then you have two divisors: i and N/i. Add these to the list (or count) of divisors
  3. If i > sqrt(N), finish, else set i = i + 1 and go to (2)

For example, if N = 24, then this would give you

i = 2 => 2, 12
i = 3 => 3, 8
i = 4 => 4, 6
sqrt(24) = 4.90, so finish

(I know this algorithm doesn't strictly match what you asked, but it should be easy enough to adapt.)

Upvotes: 0

ravi
ravi

Reputation: 10733

Rather than checking every number within the range you could something like this.

Find number of divisors within the maximum number and then within minimum number. After subtraction you would get desired result. For e.g:-

Let's say range is [5,15].

15/3 = 5;  //within max number.
5/3 = 1;   //within min number.

result = 5-1 = 4;

NOTE:- You have to take care of boundaries in the range to get correct result.

Upvotes: 0

Paul R
Paul R

Reputation: 212959

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.

Upvotes: 7

Related Questions