Identifying all prime numbers less than 200

Question

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.

Answer 1

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.

Answer 2

Your reasoning is a bit "in reverse" when you are thinking about the 10. When you employed 2, the 10 & all of its multiples 20, 30, 40, et. al. were indeed eliminated. Note here that 25 was skipped. The fact that 5 is a factor of 10 makes no difference as that 5 never gets used. When actually using this method, its no problem at all to determine what number to use next: it's simply the next higher number not already marked out.

Answer 3

Doing the sieve with the primes in order, the first nontrivial multiple of $p$ to eliminate is $p^2$.

If $p$ is an odd prime, then $2p$ should have already been eliminated when you were crossing off the multiples of $2$. But $p^2$ is odd, not even, so it shouldn't have been eliminated at a prior step. Likewise, if $p$ is a prime greater than $3$, then you don't need to cross $2p$ and $3p$ off again because they should have already been crossed off.

Let's see what happens with D. You might forget to cross off $35$ if you skip ahead to $49$. And then at the end of the process you might come to the absurd conclusion that both $5$ and $25$, and possibly $35$ and $105$, are also prime, which is of course incorrect.

Answer 4

If $n>1$ and $n$ is not prime then $n=ab$ with $a>1$ and $b>1$ and it cannot be true that both $a$ and $b$ are $>\sqrt n.$ So one of $a,b$ is $\leq \sqrt n$, and will have a prime divisor that is also $\leq \sqrt n.$

So if $1<n\leq 200$ and $n$ is not prime then $n$ is divisible by a prime $p\leq \sqrt n\leq \sqrt {200}\;.$ The largest prime not exceeding $\sqrt {200}\;$ is $13.$

You might also notice that the prime $5$ is not in choice D. Using D would not eliminate $25$ or $125$ from the list of primes.

This method of finding primes is called the Sieve of Erastosthenes.