CS 121: Assignment 1

Review of CS 120

Due: Monday, January 14, 10:00 am

Write a program that calculates all prime numbers less than 10,000. The program works as follows:

1. Create a main method, and a method called ArrayList< Integer > sieve( int n ), which returns a list with all the prime numbers less than n. The main method calls sieve( 10,000 ), and prints out the results.
2. Inside of sieve(), do the following:
   1. Call method createTrueArray( n ) to create a boolean array of size n.
   2. Set cells 0 and 1 of the array to false. Each cell in the array represents a number, the boolean value represents whether it is prime or not. We start by assuming that all numbers greater or equal 2 are prime, and then we remove the ones that are not.
   3. Loop over the array, starting at index 2.
   4. First, remove all multiples of 2, by setting the values for 4, 6, 8, ... to false.
   5. Then, look for the next number still marked true (in this case 3), and set all its multiples to false.
   6. Repeat with all numbers that are marked true. When you are done, only prime numbers will be marked true.
   7. Call method booleanArrayToIntList() to return a list of integers that contains the primes.
3. Method boolean[] createTrueArray( int n ) creates a boolean array of size n and initializes all its values to true.
4. Method ArrayList< Integer > booleanArrayToIntList( boolean[] booleans ) loops through booleans, and for each true value, it adds the corresponding number to a list. Finally, it returns the list.

CS 121