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 need to find the number of natural numbers between 1 and 1000 that are divisible by 3, 5 or 7.

I know that given a set of numbers, 1 ... n, the number of numbers divisible by d is given by $\lfloor \frac{n}{d} \rfloor$

So if we let $A$ be the set of numbers divisible by 3, $B$ be the set of numbers divisible by 5 and $C$ be the set of numbers divisible by 7, then the size of the union of those sets is going to be the number required.

However, to work out $A \cup B \cup C$, I need to know $A \cap B$ (and $A \cap C$ etc).

My only thought was that to work out $A \cap B$, I could use $\lfloor \frac{1000}{3 \times 5} \rfloor$, but I am unsure if this misses out some numbers. Is that the correct way to do it or not? If no, can anyone suggest the correct way.

share|improve this question

3 Answers 3

up vote 5 down vote accepted

In general, you have to use $\left\lfloor\frac{1000}{[a,b]}\right\rfloor$, where $[a,b]$ is the least common multiple of $a$ and $b$.

share|improve this answer

That's right. A number is divisible by 3 and 5 if and only if it is divisible by 15.

share|improve this answer

You can be sure that it does not miss any number. It comes out as an multiplication because you are looking for the common multiple of 2 prime numbers.

It would be the same for the other intersections that you need. $$(A\cap B), (A \cap B \cap C) $$

share|improve this answer

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.