The goal of this lab is to write a class Eratosthenes to execute the
algorithm called Eratosthenes Sieve to find all prime numbers less than
an integer specified by the user and then save the thus-obtained prime
numbers in a file, which is also specified by the user. These two
parameters, the limite and the file name, should be given as the arguments
to the program:
In the main method of the program, limit can be obtained by executing
Integer.parseInt( args[ 0 ] ) and is args[ 1 ].
The Eratosthenes algorithm can be explained as follows:
Write on a piece of paper the numbers 2 through limit-1
For p = 2, ..., limit-1, if p is not crossed out, then cross
out all the multiples of p that are greater than p.
For example, if the limit is 16, we start with the numbers
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
For p = 2, we cross out all the even numbers other than 2, and so the list
of remaining numbers becomes:
2, 3, 5, 7, 9, 11, 13, 15
The next we do p = 3. We cross out 6, 9, 12, and 15. The list
becomes:
2, 3, 5, 7, 11, 13
We skip p = 4 because p is already crossed out.
The next comes p = 5. We cross out 10 and 15, but since they are already
crossed out, the list does not change. The same deal for the remaining
values of p.
The final list is thus 2, 3, 5, 7, 11, 13. The numbers on this last list
are the prime numbers below 16.
This process can be carried out using a boolean array as follows:
Given limit, declare a boolean array of length
limit. For each p = 2, ..., limit-1, the array
has true at position p if and only if p has not been crossed out.
Fill the array with true. This is the initial status of the list.
For each p between 2 and limit-1, at each position that is
a multiple of p, excluding p, set the value of the array at the
position to false (corssing out).
For each p between 2 and limit-1, if the array holds
true at the position, print p to the output file with a newline.
Write your code in such a way that it prints out the value of p and
each number that is crossed out for the first time.