1. set

If there is a set {1,2,3,...,1000} How many numbers are left if all multiples of 2 3 5 7 are crossed out.

2. Originally Posted by Mac
If there is a set {1,2,3,...,1000} How many numbers are left if all multiples of 2 3 5 7 are crossed out.
Looks to me you can't avoid using a sieve algorithm .....

3. thanks i have done this by exclusion and inclusion principle.

4. I'd like to see the solution to this. I have a solution in my head, but it's much too messy and not very efficient. I'm not too familiar with the inclusion-exclusion principle, so if someone could "baby-talk" their way through it, that would be great

5. Originally Posted by Jhevon
I'd like to see the solution to this. I have a solution in my head, but it's much too messy and not very efficient. I'm not too familiar with the inclusion-exclusion principle, so if someone could "baby-talk" their way through it, that would be great
Notation: $a|b$ reads " $a$ divides $b$"

Let $S = \{1,2,...,1000\}$
Let $A = \{ x \in S : 2|x \}$
Let $B = \{ x \in S : 3| x\}$
Let $C = \{x \in S : 5|x\}$
Let $D = \{ x \in S : 7|x\}$.

Now,
$|A\cup B \cup C \cup D| = |A|+|B|+|C|+|D| - |A\cap B| - |A\cap C| - |A\cap D| - |B\cap C| - |B\cap D| - |C\cap D|$ $+|A\cap B\cap C|+|A\cap B\cap D|+|A\cap C \cap D|+|B\cap C\cap D| - |A\cap B\cap C\cap D|$

Now,
$|A| = 500$
$|B|= 333$
$|C| = 200$
$|D|=142$

When you reach the mixed ones it is easy. Because $\gcd$ between any two of $2,3,5,7$ is $=1$ it means that, for example, $A\cap B = \{ x\in S : 6 | x\}$ and $A\cap B\cap C = \{ x\in S : 30|x\}$. And so on.