## CSE 131 Module 3: Arrays

Important!

Before beginning any work, do a Team...Pull in your repository.

### Studio

If necessary, review studio procedures before starting.

### Warmup

• First, form a group of two people, possibly three if there is an odd number in the room.
• 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.
• All members of the group should update their repositories:
• Open your repository in eclipse
• Right-click (control-click on a mac) on your repository name
• Drag down to Team...
• Choose Pull
• Supply your bitbucket credentials as needed
• 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.

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 array contents 0 1 2 3 4 ... 49 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?

• If your studio contains a feedback.txt file, respond to the questions and supply any requested information.
• You must commit all of your work to your repository. It's best to do this from the top-most level of your repository, which bears your name and student ID.

When you are done with this studio, you must be cleared by the TA to receive credit.
• Do a Team…Pull to update your repository. You must do this or the commit/push below may fail.
Make certain this has worked by logging into bitbucket. There you will see the commit(s) in your news feed if it was successful. You can also check the Source page to locate and ensure your code was received.

It is your responsibility to make certain the code has been pushed. Some of your work receives credit through testing of your pushed code. You will receive no credit for such work if you failed to push. We generally reserve the right to revoke credit for any of your work that has not been pushed on-time.

• Fill in the form below with the relevant information
• Have a TA check your work
• The TA should check your work and then fill in the TA's name
• Click OK while the TA watches
• If you request propagation, it does not happen immediately, but should be posted in the next day or so

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