In this exercise, we will find prime numbers, using a method called the Sieve of Eratosthenes. Wikipedia has a good explanation of the method, including an intuitive video showing how the method works.

In this example, we set \( n = 20 \).

• We create an array, sieved_numbers, initialised as: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20].
• We initialise \( p = 2 \).
• We use a while loop to check that \( p \lt n \). The while loop should:
  1. Print out \( p \);
  2. set all values in sieved_numbers which are multiples of \( p \) to zero;
  3. find the next value to use for \( p \). This is the first number in sieved_numbers which is greater than the current value of \( p \). If there is no such number, then terminate the loop, by setting \( p=n+1 \).

So, our algorithm should loop as follows:

• Iteration 1: (Since \( 2 \lt 20 \))
  1. Print out \( p \) (i.e., 2).
  2. Set multiples of 2 to zero; so sieved_numbers = [0, 3, 0, 5, 0, 7, 0, 9, 0, 11, 0, 13, 0, 15, 0, 17, 0, 19, 0].
  3. Find the next value of \( p \), which will be 3.
• Iteration 2: (Since \( 3 \lt 20 \))
  1. Print out \( p \).
  2. Set multiples of 3 to zero; so sieved_numbers = [0, 0, 0, 5, 0, 7, 0, 0, 0, 11, 0, 13, 0, 0, 0, 17, 0, 19, 0].
  3. Find the next value of \( p \), which will be 5.
• Iteration 3: (Since \( 5 \lt 20 \))
  1. Print out \( p \).
  2. Set multiples of 5 to zero; so sieved_numbers = [0, 0, 0, 0, 0, 7, 0, 0, 0, 11, 0, 13, 0, 0, 0, 17, 0, 19, 0].
  3. Find the next value of \( p \), which will be 7.
• Iteration 4: (Since \( 7 \lt 20 \))
  1. Print out \( p \).
  2. Set multiples of 7 to zero; so sieved_numbers = [0, 0, 0, 0, 0, 0, 0, 0, 0, 11, 0, 13, 0, 0, 0, 17, 0, 19, 0].
  3. Find the next value of \( p \), which will be 11.
• Iteration 5 (p=11)
• Iteration 6 (p=13)
• Iteration 7 (p=17)
• Iteration 8 (p=19)
  1. Print out \( p \).
  2. Set multiples of 19 to zero, sieved_numbers = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].
  3. Find the next value of \( p \); but there are no numbers greater than \( p \). So instead set \( p=n+1 = 21 \).
• Since \( 21 \lt 20 \) is not true, we stop looping.

Write a program Sieve which finds all the prime numbers up to 20 using the Sieve of Eratosthenes and prints them to the terminal on a single line. Your program should produce the output in the following form:

: java Sieve
2 3 5 7 11 13 17 19
:

Here is Eratosthenes’ method of calculating the primes from 1 to \( n \):

1. Start with an array of numbers [2, 3, 4, 5, 6, 7,..., n], called, for example, sieved_numbers.
2. Let \( p = 2 \) (the first prime number).
3. Set equal to zero all entries in sieved_numbers which are multiples of \( p \).
4. Find the first non-zero number in sieved_numbers which is greater than \( p \). This number is prime, so print it out, and now set \( p \) to be this number.
5. Repeat step (4) until \( p \gt n \), or there are no more numbers left in sieved_numbers.