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.
$\endgroup$ 05 Answers
$\begingroup$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$.
$\endgroup$ $\begingroup$That's right. A number is divisible by 3 and 5 if and only if it is divisible by 15.
$\endgroup$ 2 $\begingroup$divisibility by 3 or 5 or by both means: N(3 or 5)=N(3) + N(5) -N(3 and 5) N(3 and 5) bcoz remove all common from nos. divisible by 3 and 5
N(3)=1000/3=333 N(5)=1000/5=200 N(3 and 5)=66 so 333+200-66=467
$\endgroup$ 1 $\begingroup$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) $$
$\endgroup$ $\begingroup$1~1000, there are 333 numbers can be divided by 3; there are 200 numbers can be divided by 5; there are 142 numbers can be divided by 7; However there are 66 numbers can be divided by both 3 and 5 (e.g. 15); there are 47 numbers can be divided by both 3 and 7 (e.g. 21); there are 28 numbers can be divided by both 5 and 7 (e.g. 35); Thus: 333+200+142-66-47-28=534 However there are 9 multiples of 105, which have been included in all of above "333, 200, 142, 66, 47, and 28", thus after the subtraction, there is 0 multiple of 105, thus we have to add the number of multiples of 105 to the "534". Therefore, totally there should have 543 numbers between 1~1000 which can be divided by 3, 5, or 7.
$\endgroup$
