Lab 3 pre-lab: Arrays

The goal of this lab is to practice creating and using basic arrays. This reading gives you a chance to think about the problem before you come to class. Note that you do need to indicate that you have done the reading by visiting the online version of this page at http://cs.wheaton.edu/~cgray/csci235/labs/prelab-arrays.php.

The Sieve of Eratosthenes

The Sieve of Eratosthenes is a method for finding prime numbers. The idea is first to write out all numbers (from 2 up to a certain highest number) in a list.

Then cross off all the multiples of 2.

The next uncrossed number (in this case 3) is also the next prime number. Cross off every 3rd number that's not already crossed off.

Repeat this process. Find the next uncrossed number (say, n) and cross off every nth number after that.

Your task will be to write a program that uses this technique to compute all the prime numbers less than 100.

Things to think about:

• How can you represent the list of numbers in Java, such that you can "cross them off"?
• How can you deal with the fact that your program needs the list to start at 2?
• Is there something you should do to make testing quicker than running all the way to 100?