1
$\begingroup$

I am working on a programming problem and I have broken the problem down into finding the amount of common multiples less than $n$ ($n<10^{18}$) between two sets of numbers (where the size of the sets is no less than one and no greater than three). For example:
set1 $= \{a, b, c\}$
set2 $= \{d, e\}$
$n = 10000$ So the problem would be, how many numbers between $1$ and $10000$ are divisible by at least one number from each set. One solution would be to iterate $1$ through $n$ and test each number, however this is too time consuming when $n$ is very large so I am looking for a mathematical solution.
I have worked out, to calculate the number of unique multiples of just one set you would do something like;
$(n/a) + (n/b) + (n/c) - (n/\operatorname{lcm}(a,b)) - (n/\operatorname{lcm}(a,c)) - (n/\operatorname{lcm}(c,b)) + (n/\operatorname{lcm}(a,b,c))$ (this would be integer division)
I am just wondering if I could use this sort of logic to solve the whole problem or if I am barking up the wrong tree, thanks for any help.

1 Answers 1

2

Yes, you can use that sort of logic. Here's a hint: you can combine your set1 and set2 to get a single set3 so that a number that's divisible by a number from each of set1 and set2 must be divisible by a number from set3.

  • 0
    thanks for your help I will go and work on what you've said, I think i know what your getting at.2012-04-09