Counting divisibility from 1 to 1000

Question

Of the integers $1, 2, 3, ..., 1000$, how many are not divisible by $3$, $5$, or $7$?

The way I went about this was

$$\text{floor}(1000/3) + \text{floor}(1000/5) + \text{floor}(1000/7)-\text{floor}(1000/(3\cdot5)) - \text{floor}(1000/(3\cdot7))-\text{floor}(1000/(5\cdot7))+\text{floor}(1000/(3\cdot5\cdot7))$$

which resulted in $543$ and then I subtracted that from $1000$ to get $457$.

I do not have an answer key so I was wondering if that was the right approach to the question. Any help or insight would be appreciated!

Answer 1

Your result of 457 is correct.

The different sets of numbers as table:

And as diagram:

Answer 2

The idea is to use the Inclusion/Exclusion principle. Let us first count how many numbers are divisible by $3$, $5$, or $7$. Let set $X$ be the set of all such numbers.

Let $A$ = {Numbers divisible by $3$} Let $B$ = {Numbers divisible by $5$} Let $C$ = {Numbers divisible by $7$}

By the inclusion/exclusion principle:

$|X| = |A| + |B| + |C| - |A\cap B| - |A\cap C| - |B\cap C| + |A \cap B \cap C|$. Then, of course, the answer you're looking for will be $1000-|X|$.

I'll leave the implementation of this up to you. :)

http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle