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
    

×

Problem Loading...

Note Loading...

Set Loading...