CSE 131 Module 3: Arrays

Studio


If necessary, review studio procedures before starting.

Warmup


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.

Note: this assignment should be completed without the use of the modulus operator (%).

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 n and give it a name.
  4. Use iteration to fill the array with integers so that it matches the one above.
  5. Everything is initially assumed to be prime, so 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. Note that we are not checking every element in the array to see if it is divisible by two, rather we are iterating straight to all the numbers that we know are divisible by 2, i.e. its multiples.
  7. Iterate to the next prime (non zero) element in the array and repeat this process. Remember to leave the original number as is and only mark the multiples as not prime.
    Why should we not bother finding multiples of numbers that we previously marked as not prime?
  8. Once we have gone through the whole array, anything remaining is a prime number. Print out just 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.
  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 (read carefully)



Last modified 12:48:21 CDT 30 August 2017
When you done with this studio, you must be cleared by the TA to receive credit.

This demo box is for studio 3
Last name WUSTL Key Propagate?
(NOT your numeric ID) Do not propagate
lower case only
e.g. Smith j.smith
1 Copy from 1 to all others
2 Copy from 2 to all others
3 Copy from 3 to all others
4 Copy from 4 to all others

Acknowledgements and assertion of integrity

You must select one of the options below
The work submitted here was performed in accordance with this course's policy on collaboration.
On your honor, you have neither given nor received any unauthorized aid on this assignment.

However, the following TAs, students, or professors were supportive in completing this assignment.
Their help was also in accordance with course policies.

Thanks to (leave blank if appropriate):

In spite of seeking help as allowable by this course's policy on collaboration, you were unable to complete this assignment. No credit will be received for this assignment.

You would like to be contacted by an instructor to facilitate staying on track in this course.

Comments about this:

You have NOT abided by this course's policy on collaboration. No credit will be received for this assignment, but by checking this box, no academic integrity violation will be filed for this assignment.

You would like to be contacted by an intructor to faciliate staying on track in this course.

Comments about this:


TA: Password: