What is the best algorithm for finding the number of integers divisible by X...?

[woojungkyu]

What is the best algorithm for finding the number of integers divisible by X?

I can easily do a:

for(num=1;num<maxRange;num++) {
int result = 0;
if(num%Y==0) {
result++;
}
}

but what if the maxRange is a really huge number (say a 9 or 10 digit number)?
I need something which is faster than the algorithm above.

[JamesCherrill]

Isn't it just maxRange/X?

[woojungkyu]

Isn't it just maxRange/X?

I'm a bit confused? What if the minimum range changes?
like instead of starting from 1 it starts with 200... etc?

And how accurate is it when lets say
max=1000, X=6? >_<

[JamesCherrill]

Then isn't it just max/X - (min-1)/x ??? (ie subtract the ones below the min)
(I'm not certain about this, but if you have working code now you could try this and see if it gives the same answers)

[woojungkyu]

Then isn't it just max/X - (min-1)/x ??? (ie subtract the ones below the min)
(I'm not certain about this, but if you have working code now you could try this and see if it gives the same answers)

oohh.. that might work.. >_<
Because what I did at first was to subtract the min from the max then divide. :D
Sorry. :<

Also tried doing this:

for (i = min; i <= max; i += X)
    {
        result++;
    }

just in case.. >_<

[hfx642]

Instead of incrementing your test number by 1, you can increment your test number by X,
But only once you find the first test number that works.

int Min = 10;
int Max = 100;
int Divisor = 27;
int Test = Min;
int Jump = 1;
int Count = 0;

while (Test <= Max)
{
   if (Test % Divisor == 0)
   {
      Count++;
      Jump = Divisor;
   }
   Test = Test + Jump;
}

[Taywin]

What you need to do will be separated into 2 parts - find the first divisible number and a loop which is increment by X up to the max. The second part is easy and you should be able to do it. Now we need to talk about the first part.

hfx642 algorithm is OK but it is a brute-force which could be costly. If let say min is 1234, max is 987654321, and X is 999999, How many times do you have to go through the loop to find the first divisible number?

What you could actually do is a simple arithmetic. Think about it. If the X value is already a divisible value of the min, the min itself is already the first divisible number, correct? Now, if it is not, then the modulo value could be used to find the first divisible number! *hint hint*

PS: You also need to check whether X is less than max before you attempt to find the first divisible number.

[hfx642]

Ooooooo... Modulo!!
Yes... Use THAT to get your first number, THEN increment by your divisor.
Good idea!