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`

×

Problem Loading...

Note Loading...

Set Loading...