Objectives
To establish your proficiency with:
- Creating Java methods
- Defining basic variables
- Using operators, expressions
- Using Java flow-control structures, especially the for-loop
- Using Java arrays
Description
The Sieve or Eratosthenes is a simple, relatively efficient algorithm for
computing the complete set of prime numbers between 2 and whatever
upper limit the user chooses.
The limitation of this method is that it must always start from 2:
you cannot efficiently just start from an arbitrarily high number.
It obviously follows from this that the method also cannot be used
to simply test the "primeness" of an arbitrary number, which is a much
more useful problem.
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 Requirements and Specification
The purpose of this warm-up project is to make sure that you have a
working knowledge of Java at least at the procedural level.
This goal of establishing your proficiency with basic Java constructs
drives many of the following, possibly arbitrary-sounding
requirements:
- 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.
- 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).
- Your class will be named Prime.
(Again, taken care of.)
- 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.
- 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.
- 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.
- 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.
- You must use a non-trivial for-loop (i.e., one that does something useful)
at least once in your code.
-
Do not any other classes more complex than arrays and Strings.
Specifically, this means no ArrayLists.
- 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.)
-
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.
- You are not to use any classes other than the array and String
classes without first checking with me.
- 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 and Notes
- 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 Compiling section of the course projects page
for details on how to run and execute your project on GL.
Assuming you've used the recommended file name, then to submit your project, type the command
<![CDATA[
submit cs202 Proj1a 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.
More complete documentation for submit and related commands can be found
here.
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.
