# Joe's Sieve

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.

1. Initially,

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

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

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

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

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

×