5
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?

Useless
  • 64,155
  • 6
  • 88
  • 132
Konrad
  • 49
  • 1
  • 7
  • off-topic: something divisible by `c` is a _multiple_ of `c`, not a divisor. So, you're counting multiples rather than divisors. – Useless Nov 06 '14 at 11:04
  • My english skill lacks a lot, thanks for correction! – Konrad Nov 06 '14 at 11:08
  • Possible duplicate of [optimize code to get the number of integers within given range that are divisible by integer](http://stackoverflow.com/questions/11805004/optimize-code-to-get-the-number-of-integers-within-given-range-that-are-divisibl) – 200_success Mar 09 '16 at 00:58

3 Answers3

7

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.

Paul R
  • 208,748
  • 37
  • 389
  • 560
0

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.)

Tristan Brindle
  • 16,281
  • 4
  • 39
  • 82
  • Yup, not exactly what I wanted, but thanks! Gonna use it anyway. – Konrad Nov 06 '14 at 11:11
  • 1
    And if you were doing this, you wouldn't (shouldn't) calculate `sqrt()` of the upper-bound but check whether the square of `i` exceeds it (in this case, `4x4 <= 25`; `5x5 > 24` so stop). – TripeHound Nov 06 '14 at 11:53
0

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.

ravi
  • 10,994
  • 1
  • 18
  • 36