There are 999 integers less than 1000. Immediately, we can eliminate all of the even numbers among those, since we know they share the factor 2 with 1000. This gets rid of 499 integers, leaving us with 500 odd integers. To make our next elimination, we'll have to take a look at 1000 again.
1000's prime factorization is 2³ · 5³, which means that our final filter on the remaining integers should be to eliminate every integer divisible by 5. Any whole number ending in a 0 or a 5 is divisible by 5, but since we've eliminated all even numbers from our list, we've split the amount of those divisible numbers in half. It may be a bit hard to visualize this elimination, so let's figure out how many integers would get eliminated in a bit of a simpler setting first:
Usually we'd be eliminating 4 numbers from this sequence, but in a sequence with all the even numbers eliminated:
1 3 5 7 9 11 13 15 19
We only eliminate <em>half that amoung</em>, or 2.
Here, we'd usually be eliminating 100 of the numbers from our list of 500 (or 1/5 of the list, since we eliminate a number every 5 integers), but here, we're only eliminating half of that amount, or 50. This leaves us with 500 - 50 = 450 integers with no factors in common with 1000.
Note: We also sometimes refer to numbers with this kind of relationship as <em>coprime</em> or <em>relatively prime</em>.
