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: $\displaystyle a|b$ reads "$\displaystyle a$ divides $\displaystyle b$"

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

Now,
$\displaystyle |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|$$\displaystyle +|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,
$\displaystyle |A| = 500$
$\displaystyle |B|= 333$
$\displaystyle |C| = 200$
$\displaystyle |D|=142$

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