Question 1160025
<pre>
Since 105 written as a product of primes is 3∙5∙7, we want to subtract from the
1000 integers between 1 and 1000 (including 1 and 1000), all the multiples of
3,5, or 7, for that would remove all integers which have a common divisor with
105 other than 1.

Since the multiples of these three primes overlap, we must use the "sieve"
formula (the method of inclusion and exclusion):

{{{(matrix(1,5,
(matrix(5,1,Number,of,multiples,of,3))^"",""+"",
(matrix(5,1,Number,of,multiples,of,5)),""+"",(matrix(5,1,Number,of,multiples,of,7))
))}}}{{{matrix(6,1,"","","",""-"","","")}}}{{{(matrix(1,5,
(matrix(5,1,Number,of,multiples,of,3*5=15))^"",""+"",
(matrix(5,1,Number,of,multiples,of,3*7=21)),""+"",(matrix(5,1,Number,of,multiples,of,5*7=35))
))}}}{{{matrix(6,1,"","","",""+"","","")}}}{{{

(matrix(5,1,Number,of,multiples,of,3*5*7=105))}}}

To find the number of multiples of an integer between 1 and 1000 (including 1
and 1000), we divide 1000 by that integer and take only the whole part:

1000/3 = 333.3∙∙∙       so N(multiples of 3)         = 333
1000/5 = 200            so N(multiples of 5)         = 200
1000/7 = 142.8∙∙∙       so N(multiples of 7)         = 142
1000/(3×5) = 66.6∙∙∙    so N(multiples of 3×5=15)    = 66
1000/(3×7) = 47.6∙∙∙    so N(multiples of 3×7=21)    = 47
1000/(5×7) = 28.5∙∙∙    so N(multiples of 5×7=35)    = 28
1000/(3×5×7) = 9.5∙∙∙   so N(multiples of 3×5×7=105) = 9  

Substituting in the "sieve" formula:

(333+200+142)-(66+47+28)+(9) = 675-141+9 = 543

That's the number of multiples of 3,5 or 7

We subtract from the 1000 integers between 1 and 1000 (including 1 and 1000)

and get

1000 - 543 = 457  <---answer

Edwin</pre>