CSE 131 Module 3: Arrays
review studio procedures before
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 (%).
- 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
- 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 |
- Write code that instantiates an int of size n and give it a name.
- Use iteration to fill the array with integers so that it matches the one above.
- Everything is initially assumed to be prime, so we could mark numbers as not prime by setting them equal to zero.
- 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.
- 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?
- 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
- 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.
- 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?
- Create a new array (or modify your old one) with this new type choice.
- Fill your new array so that 0 and 1 are not prime, but every other number is initially prime.
- Repeat steps 6-8.
- 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)
- 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.
- Follow the instructions in the green box below to receive credit for your work.
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.
- Commit and push all your work to your repository
- 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 his or her 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