Joe's Sieve

Computer Science Level 2

Joe wanted to find out the primes from 1 to 100 and has come up with the following, sieve-like algorithm:

Step 1: Write down the numbers from 2 to 100. (Not 1, because 1 is not prime anyway.)
Step 2: If the first number remaining in the list is $i$ , then remove the numbers at every $i^\text{th}$ position, starting from that first number.
Step 3: Record $i$ as a prime.
Step 4: Iterate steps 2 and 3 until all elements from the list are removed.

Will this actually yield all the primes?

Here is a trial run of the first few steps of the algorithm for the purpose of demonstration.

Initially,

1 2	`list = 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ... primes = _`

Remove everything at every 2 $^\text{nd}$ position, starting from 2:

1 2	`list = 3, 5, 7, 9, 11, 13, ... primes = 2`

Remove everything at every 3 $^\text{rd}$ position, starting from 3:

1 2	`list = 5, 7, 11, 13, ... primes = 2, 3`

Yes, this method works No, this method does not work

1 solution

Michael Huang
Sep 17, 2017

It suffices to prove this by showing that the algorithm misses at least a prime number.

From the trial run,

Step $2$ indicates that we remove all even integers from $2$ to $100$ , so we have odd numbers from $3$ to $99$ .
Step $3$ indicates that we remove all integers of the form $3 + 6k$ , where $k$ is a non-negative integer. All integers for $k \geq 1$ are composite integers, so we do not miss the prime number. The resulting list consists of all integers not divisible by $3$
If we run the next step, then we remove integers at every $5$ th position, starting from $5$ . This is equivalent to removing all integers of the form $5 + 14\ell$ , where $\ell$ is a non-negative integer. But a prime number $19$ is removed from the list, which disproves that not all primes are found.