Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
thanks for your help I will go and work on what you've said, I think i know what your getting at. –  ricola86 Apr 9 '12 at 19:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.