Clever Geek Handbook

Faster algorithm for counting the number of numbers 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 range of numbers, c

is the divisor, and it d

counts the multiplicity c

. For example, if a=5, b=15, c=3

, d

equals 4

, because "6, 9, 12, 15" are multiples between 5 and 15. I need to find a faster way to do this, can anyone help?

+3


source to share


3 answers


One way 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

would be 2, upper

would be 5, giving d

4.

+5


source


An untested algorithm is not at the top of my head to find all the correct divisors of a positive integer ...

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

.

  • Let be i = 2

  • If N % i == 0

    , then you have two divisors: i

    and N/i

    . Add them to the list (or count) of divisors
  • If i > sqrt(N)

    , finish, still install i = i + 1

    and go to (2)


For example, if N = 24, this will give you

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

(I know this algorithm is not strictly what you asked for, but it needs to be easily adapted.)

0


source


Instead of checking every number within a range, you could do something like this.

Find the number of divisors within the maximum number and then within the minimum number. After subtracting, you will get the desired result. For example for example: -

Let, for example, the range [5,15].

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

result = 5-1 = 4;

NOTE. - To get the correct result, you must take care of the bounds in the range.

0


source






More articles:


All Articles