Below is the question I am confused on. I will provide my logic to my solution also.
In order to identify all the prime numbers less than 200, a person writes each number from 1 to 200, and eliminates all the multiples of 2, then all the multiples of 3. To complete this task, the person will have to eliminate the multiples of which additional numbers?
A. 5, 7, 9, 11
B. 7, 9, 11, 13
C. 5, 7, 11, 13
D. 7, 11, 13, 17
I eliminated answer choices A and B, since all multiples of 9, will ALSO be multiples of 3. So the person does not have to repeat the process over. I also eliminated answer choice C, since all multiples of 10, are also multiples of 5, which are also multiples of 2 (i.e. 10, 20, 30, 40, 50 etc.) Again, the person would not need to repeat the process over. So I chose answer D. However, the correct answer is C.
Best Answer
By always eliminating multiples of numbers you can guarantee that you only have to remove multiples of prime numbers (as you noted, you have already removed all multiples of 9 by removing all multiples of 3). So the remaining issue is how large a prime number you have to reach before you've eliminated all the possible composite numbers.
Any composite (non-prime) number must have at least two factors, neither of which is one, e.g. $169 = 13 \times 13$, and those factors must be either equal, or one is larger than the other. These numbers will always be eliminated when we remove the multiples of the smaller factor (e.g. $161 = 7 \times 23$ will be eliminated when we remove multiples of $7$ and so is gone when we reach multiples of $23$).
So, we can always stop when we reach the largest prime number smaller than the square root of the limit -- in this case, when we reach the largest prime number smaller than $\sqrt{200}$. (The square root, say $a$ has the property that $a\times a = 200$ so any other combination of factors must have one larger, one smaller).
$13\times 13 = 169 < 200$ and $17\times 17 = 289 > 200$, so we don't need to check as far as $17$ and D cannot be the answer, which leaves C.