Project 1 — Sieve of Eratosthenes

Objectives

To establish your proficiency with:

1. Creating Java methods
2. Defining basic variables
3. Using operators, expressions
4. Using Java flow-control structures, especially the for-loop
5. Using Java arrays

Project Policy

This project is considered an OPEN project. Please review the open project policy before beginning your project.

Project Analysis

Code from this project will be reviewed in class as noted on the schedule as “Project 1 Analysis.” If you would like your code to be reviewed in class, please contact your instructor. Your name will be held in strict confidence. This practice has worked extremely well in the past. It is a wonderful way to compare and contrast the different designs that people have used.

Project Overview

The method is very simple. Described as a manual process (there were no computers when Eratosthenes supposedly invented the method), the steps are:

• Choose an upper limit on your prime number search--let's call it 'N'
• Write down all the consecutive integers from 2 through N
• Pick 2 as your current prime number--call it 'P'
• Now perform the following loop:
  • Cross off all multiples of P (except P itself) from your list (this is a loop in and of itself).
  • Look for the first number greater than P that has not been crossed off yet.
  • If you find one, set P to this new value, and continue; else, exit the loop.
• After finishing the above loop, all the numbers that have not been crossed off are prime.

Project Specification

1. You will be given a template java class source file, available here. Download that and look at it before even starting to think about your design. The template will drive/constrain how you program up this project.
2. You will be defining a class in the default package (don't worry if you don't know what this means: the template file takes care of this for you).
3. Your class will be named Prime. (Again, taken care of.)
4. The template java source contains stub definitions of two methods: findPrimes() and cancelMultiples(): your task is to flesh out the implementations of these two methods. Your implementation must do exactly what is specified in these methods' header comments.
5. findPrimes() will be the main entry point. Our test harnass will call findPrimes(), and will examine the return value for correctness. Specific requirements for findPrimes() are:
   • It must create a local array of booleans to keep track of what numbers have been crossed out. For simplicity's sake, size this array as "boolean[endNum + 1]", i.e., each array element "x[i]" represents whether the number 'i' has been crossed out. This means entries x[0] and x[1] are essentially wasted--don't sweat details like this.
   • It must return a fully-filled array of the correct size; in other words, if findPrimes() found 7 prime numbers in the requested range, the returned value must be an array of ints exactly 7 elements long, with every element a valid prime number.
   • findPrimes() must invoke cancelMultiples() (described below) to do the main work of cancelling out all the multiples for each prime that it finds.
6. cancelMultiples() is a helper method for findPrimes() that you must write, mostly to demonstrate that you know how to define and call other methods. cancelMultiples() takes a new prime number and an array of booleans as arguments, and cancels out all multiples of the prime number (except the prime itself) by setting the appropriate elements of the array to false. It changes the array in-place, and so does not need to return anything.
7. You must not change the method header for either of the methods you are required to implement. That means you cannot change the method name, parameter names or types, nor method return value type.
8. You must use a non-trivial for-loop (i.e., one that does something useful) at least once in your code.
9. Do not any other classes more complex than arrays and Strings. Specifically, this means no ArrayLists.
10. Your program will be called by a grading test program, and therefore, does not need to (and should not) do any input/output. (Obviously, you may temporarily insert print statements to debug your code.)
11. Even though there are several nice optimizations you can make to the basic algorithm outlined above, it is not worth spending extra time on. It is better to show that you can write good, clean code.
12. You are not to use any classes other than the array and String classes without first checking with me.
13. Important: I'm sure there are hundreds of existing PrimeSieve class implementations out on the web--not only will using one of those defeat the whole purpose of the project, but will also constitute cheating. Also, cribbing pieces of code from sources like the web or books is also obviously off-limits, and you will learn nothing in the process, so just don't do it.

Project Hints, Notes, Requirements, Restrictions

1. There are no hints necessary, I hope.

Grading

See the course website for a description of how your project will be graded.

Project Submission

Before submitting your project, be sure to compile and test your code on the GL system. See the Project Compilation section of the course Projects page for details on how to compile and execute your project on GL.

Assuming you’ve used the specified file names, submit your project by typing the command

submit cs202 Proj1 Prime.java

See the Project Submission page for detailed instructions.

You may resubmit your files as often as you like, but only the last submittal will be graded and will be used to determine if your project is late. For more information, see the Projects page on the course web site.

Remember — if you make any change to your program, no matter how insignificant it may seem, you should recompile and retest your program before submitting it. Even the smallest typo can cause errors and a reduction in your grade.