> The solution for this is to replace “product of n and m” bij “least common multiple of n and m”
Nice, and it works for my example, too:
Number of multiples of either 3 or 6
= Number of multiples of 3
+ Number of multiples of 6
- Number of multiples of lcm(3,6) = 6
= Number of multiples of 3
Cool. How to extend to more than 2 numbers?You could do it like in article, so for every nonempty element in powerset (combinations for each length) of those numbers calculate their lcm and add or subtract amount of multiplies of lcm according to length of element.
So for A, B, C you have (M-number of multipliers) M(lcm(A)) + M(lcm(B)) + M(lcm(C)) - M(lcm(B,C)) - M(lcm(A,C)) - M(lcm(A,B)) + M(lcm(A,B,C))
You’re right. The solution for this is to replace “product of n and m” bij “least common multiple of n and m”. So, you would get (using 4 and 6 as an example that’s slightly better than 3 and 6):
and yes, if M gets larger enough, the “naive” algorithm can get faster. It will help if you bail out once you have found _a_ divisor, and, if your numbers are ‘large enough’ (1), to do division testing in some specific order (2).(1) what is ‘large’ will be system dependent. In general, once you need bigint’s, but if your CPU doesn’t have a division instruction, it can come earlier.
(2) in general, smallest to largest, but if one of your test divisors is a power of 2, move those up front. Also, if you’re forced to use bigint’s, divisors of “2^register size +/- 1 and their factors may be easier (just as testing divisibility by 9 or 11 or 9’s factor 3 is easier in decimal written integers)