Studio 3: Sieve of Eratosthenes

Warmup(s)

  • First, form a group.
  • All but one member of your group should have this web page open so you can follow along and see the instructions as you work.
  • Plan to have one computer at which your team does its work. Initially, one of you will be in charge of typing at that computer.
  • Throughout the studio, you should trade who is in charge of the keyboard. Before doing so, commit your work to make sure your work is saved.

Sieve of Eratosthenes

In this studio you will make a sieve of Eratosthenes on a one dimensional array. This simple, ancient algorithm finds all the prime numbers within a specified range by eliminating all multiples in the array.

Procedure

  1. Prompt the user for the size, n, of the array. The sieve will determine all the primes below n. For discussion purposes, let's say we're dealing with n = 50
  2. Let's consider the best type to make the array. Based on the gif on the linked Wikipedia page, we might initially think to choose int. If we make an int[], how should we fill it? Since 0 and 1 are not prime and don't have normal multiples, the first number we care about is 2. If we fill it with the range of values (2-50) we could start at the beginning, like this:

    array index 0 1 2 3 4 .. 49
    array contents 2 3 4 5 6 .. 51
  3. Write code that instantiates an int[] of size nand give it a name.
  4. Use iteration to fill your array with integers so that it matches the one above.
  5. If everything is initially assumed to be prime, we could mark numbers as not prime by setting them equal to zero.
  6. Start at the first number in the array (2) and iteratively mark all of its multiples (4, 6, 8, etc.) as not prime.
  7. Iterate to the next prime (non zero) element in the array and repeat this process.

    Why should we not bother finding multiples of numbers that we previously marked as not prime?

  8. Once you have gone through the whole array, anything remaining is a prime number. Print out these numbers. Ex: for n = 50 the expected output is Primes under 50 = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
  9. Try looking up a number to see if it's prime and print out the result. Show what you have so far to a TA.
  10. Another idea, for simplicity, is ignoring the first two indexes and start inserting the 2 at the 2 index so that the values and indexes match. Having clear code is much more important than wasting two spaces of memory. But then, filling the array with the values is redundant! The gif can be deceiving. All we really need to fill the array with is whether each index number is prime or not. Now, what type should we use to easily mark this?
  11. Create a new array (or modify your old one) with this new type choice.
  12. Fill your new array so that 0 and 1 are not prime, but every other number is initially prime.
  13. Repeat steps 6-8. This time, the last prime printed should be 47.
  14. Further food for thought: to make our program more efficient, we can stop looking for multiples early. For example, we know that 40 won't have any multiples in the array. What is the earliest we can stop looking?

Submitting your work:

To submit your work, contact the instructor or a TA. They will walk you through the submission process. Be prepared to show them the work that you have done and answer their questions about it!