JAVA Program (using basic for-loops, arrays...): For this program, you are first

Question

JAVA Program (using basic for-loops, arrays...):

For this program, you are first going to calculate the prime numbers between 1 and 50000 using an algorithm known as the Sieve of Eratosthenes and then display the sexy prime pairs within a range specified by the user.

In addition to the main() method (which is given), write 4 supporting methods (see below) to complete the program.

public class_Sieve {

public static void main ( String args[] ) {

final int HOWMANY = 50000; // The range of numbers

boolean[] sieve = new boolean[HOWMANY+1]; // Boolean array of true/false

int lower = 1, upper = HOWMANY; // Setting initial boundaries

processSieve( sieve );

showPrimes( sieve, lower, upper );

lower = getLower( HOWMANY );

upper = getUpper( lower, HOWMANY );

showPrimes( sieve, lower, upper );

}

// implement method processSieve here

// implement method showPrimes here

// implement method getLower here

// implement method getUpper here

}

1st Method: processSieve()

Here is an overview of the algorithm for implementing the Sieve of Eratosthenes in method processSieve():

1. Work through the entire array, from beginning to end, and set all elements to true.

2. Then set elements 0 and 1 to false, since those positions are not prime numbers.

3. Set up a loop starting at position 2 through the end of the array, incrementing by 1 each time.

a. Set up an inner loop that starts at twice the value of the outer loops variable, incrementing by the value of the outer loops value each time.

i. Set the element at the position of the innermost loop to false, as this element is a multiple of the outer loops value and cannot be a prime number. For example, since element 2 has a value of true stored in it, your nested loop will identify (set to false) all elements from 3 through 50000 that are multiples of 2 (including 4, 6, 8, 10, 12, etc). Then, when you move to element 3 in the outer loop, all elements beyond 3 in the array that are multiples of 3 (6, 9, 12, 15, 18, 21) will be identified (changed to false), and so on as the outer loop runs from 2 through the end of the array. When you are done, the subscripts of all elements with true as values will be prime numbers.

2nd Method: getLower()

This method simply continuously prompts the user for a lower boundary between 1 and the value sent in as a parameter. So, with the example main() method provided, it will end up prompting the user for a valid value between 1 and 50000. It should not allow the user to proceed until a number within the appropriate range has been entered. Then, the method will return the value read from the user.

3rd Method: getUpper()

This method simply continuously prompts the user for an upper boundary between the first parameters value (the minimum value allowed) and the second parameters value (the maximum value allowed). It should not allow the user to proceed until a number within the appropriate range has been entered. Then, the method will return the value read from the user.

4th Method: showPrimes()

This methods job is to display all of the sexy prime pairs starting at the lower boundary and running all the way up through the upper boundary, one pair of numbers per line. It should also display a count after all pairs have been displayed about how many prime pairs were displayed in that range. This method assumes that the boolean array that it receives has already been processed. This method should not determine the prime numbers, nor should it call the processSieve() method.

Notes:

The processSieve() method doesnt need to do any input or output. The getLower() and getUpper() methods, by their nature, will need to do both input and output. You will need to create Scanner objects in each method. The showPrimes() method should only display the sexy prime pairs between the lower and upper boundaries.

Sample Output:

NOTE: The first display of 1419 pairs are not displayed here for brevity.

Please enter the lower boundary (between 1 and 50000):
0
Please enter the lower boundary (between 1 and 50000):
50001
Please enter the lower boundary (between 1 and 50000):
150

Please enter the upper boundary (between 150 and 50000):
0
Please enter the upper boundary (between 150 and 50000):
50001
Please enter the upper boundary (between 150 and 50000):
100
Please enter the upper boundary (between 150 and 50000):
200

Here are all of the sexy prime pairs in the range 150 to 200, one pair per line:
151 and 157
157 and 163
167 and 173
173 and 179
191 and 197
193 and 199

There were 6 sexy prime pairs displayed.

Explanation / Answer

package check4prime;

// check4PrimeTest.java

//Imports
import junit.framework.Test;
import junit.framework.TestCase;
import junit.framework.TestSuite;

public class check4PrimeTest extends TestCase {

// Initialize a class to work with.
private check4Prime check4prime = new check4Prime();

// constructor
public check4PrimeTest(String name) {
super(name);
}

// Main entry point
public static void main(String[] args) {
System.out.println("Starting test...");
junit.textui.TestRunner.run(suite());
System.out.println("Test finished...");
} // end main()

// Test case 1
public void testCheckPrime_true() {
assertTrue(check4prime.primeCheck(3));
}

// Test cases 2,3
public void testCheckPrime_false() {
assertFalse(check4prime.primeCheck(0));
assertFalse(check4prime.primeCheck(1000));
}

// Test case 7
public void testCheck4Prime_checkArgs_char_input() {
try {
String[] args = new String[1];
args[0] = "r";
check4prime.checkArgs(args);
fail("Should raise an Exception.");
} catch (Exception success) {
// successful test
}
} // end testCheck4Prime_checkArgs_char_input()

// Test case 5
public void testCheck4Prime_checkArgs_above_upper_bound() {
try {
String[] args = new String[1];
args[0] = "10001";
check4prime.checkArgs(args);
fail("Should raise an Exception.");
} catch (Exception success) {
// successful test
}
} // end testCheck4Prime_checkArgs_upper_bound()

// Test case 4
public void testCheck4Prime_checkArgs_neg_input() {
try {
String[] args = new String[1];
args[0] = "-1";
check4prime.checkArgs(args);
fail("Should raise an Exception.");
} catch (Exception success) {
// successful test
}
} // end testCheck4Prime_checkArgs_neg_input()

// Test case 6
public void testCheck4Prime_checkArgs_2_inputs() {
try {
String[] args = new String[2];
args[0] = "5";
args[1] = "99";
check4prime.checkArgs(args);
fail("Should raise an Exception.");
} catch (Exception success) {
// successful test
}
} // end testCheck4Prime_checkArgs_2_inputs

// Test case 8
public void testCheck4Prime_checkArgs_0_inputs() {
try {
String[] args = new String[0];
check4prime.checkArgs(args);
fail("Should raise an Exception.");
} catch (Exception success) {
// successful test
}
} // end testCheck4Prime_checkArgs_0_inputs

// JUnit required method.
public static Test suite() {
TestSuite suite = new TestSuite(check4PrimeTest.class);
return suite;
} // end suite()

// Test case 9
public void testCheck4Prime_primeCheck_for_value_0() {
boolean isPrime = check4prime.primeCheck(0);
if (isPrime) {
fail("Should return false 0 is not a prime number");
} else {
// successful test
}
}// end testCheck4Prime_primeCheck_for_value_0

// Test case 10
public void testCheck4Prime_primeCheck_for_value_1() {
boolean isPrime = check4prime.primeCheck(1);
if (isPrime) {
fail("Should return false 1 is not a prime number");
} else {
// successful test
}
}// end testCheck4Prime_primeCheck_for_value_1

// Test case 11
public void testCheck4Prime_primeCheck_for_value_2() {
boolean isPrime = check4prime.primeCheck(2);
if (isPrime) {
// successful test
} else {
fail("Should return false 2 is a prime number");
}
}// end testCheck4Prime_primeCheck_for_value_2

// Test case 12
public void testCheck4Prime_primeCheck_for_value_5() {
boolean isPrime = check4prime.primeCheck(2);
if (isPrime) {
// successful test
} else {
fail("Should return false 5 is a prime number");
}
}// end testCheck4Prime_primeCheck_for_value_5

// Test case 13
public void testCheck4Prime_primeCheck_for_negative_values() {
for (int i = -10; i >= 0; i++) {
if (check4prime.primeCheck(i)) {
fail("Should return false -ve numbers are not prime numbers");
} else {
// successful test
}
}
}// end testCheck4Prime_primeCheck_for_negative_values

} // end check4PrimeTest

package primea2;

import java.util.ArrayList;

import junit.framework.Test;
import junit.framework.TestCase;
import junit.framework.TestSuite;

public class PrimeRaceTest extends TestCase {
// constructor
public PrimeRaceTest(String name) {
super(name);
}

// Main entry point
public static void main(String[] args) {
System.out.println("Starting test...");
junit.textui.TestRunner.run(suite());
System.out.println("Test finished...");
} // end main()

// JUnit required method.
public static Test suite() {
TestSuite suite = new TestSuite(PrimeRaceTest.class);
return suite;
} // end suite()

// Test case 1
public void testPrimeRace_main_with_correct_args() {
try {
PrimeRace.main(new String[] { "1000", "1", "10" });
// successful test
} catch (Throwable e) {
fail("should not throw any exceptions");
}
}// end of testPrimeRace_main_with_correct_args

// Test case 2
public void testPrimeRace_checkArgs_with_0_args() {
try {
PrimeRace.checkArgs(new String[] { "" });
fail("should throw any exceptions");
} catch (Exception e) {
// successful test
}
}// end of testPrimeRace_checkArgs_with_0_args

// Test case 3
public void testPrimeRace_checkArgs_with_1_args() {
try {
PrimeRace.checkArgs(new String[] { "1000" });
fail("should throw any exceptions");
} catch (Exception e) {
// successful test
}
}// end of testPrimeRace_checkArgs_with_1_args

// Test case 4
public void testPrimeRace_checkArgs_with_correct_args() {
try {
ArrayList checkArgs = PrimeRace.checkArgs(new String[] {
"1000", "1", "10" });
if (checkArgs.size() == 3) {
// successful test
} else {
fail("checkArgs size of checkArgs arraylist should be 3");
}

checkArgs = PrimeRace.checkArgs(new String[] {
"1000", "1", "10" , "2", "10" });
if (checkArgs.size() == 5) {
// successful test
} else {
fail("checkArgs size of checkArgs arraylist should be 3");
}
} catch (Exception e) {
fail("should not throw any exceptions");
}
}// end of testPrimeRace_checkArgs_with_correct_args

// Test case 5
public void testPrimeRace_checkArgs_with_negative_args() {
try {
PrimeRace.checkArgs(new String[] { "-1000", "-1", "-10" });
fail("should throw exceptions");
} catch (Exception e) {
// successful test
}
}// end of testPrimeRace_checkArgs_with_negative_args

// Test case 6
public void testPrimeRace_checkArgs_with_4_number_of_args() {
try {
PrimeRace.checkArgs(new String[] { "-1000", "1", "10", "1" });
fail("should throw exceptions");
} catch (Exception e) {
// successful test
}
}// end of testPrimeRace_checkArgs_with_4_number_of_args

}

package modifed;

import java.util.ArrayList;
import java.util.Iterator;

import primea2.EratosthenesGen;
import primea2.JavaMathGen;
import primea2.NaiveGen;
import primea2.PROutputs;
import primea2.PrimeGeneratorInterface;

public class PrimeRace extends Thread {
// This code is adapted from A. Turner, "AtomicInteger, Volatile, Synchronized and Raw:
// Performance and Safety", NerdsCentral blogspot, 24 November 2011. Available:
// Nerds Central: AtomicInteger, Volatile, Synchronized and Raw: Performance and safety

private static int timeLimit = 0; // how long the "race" will run, in milliseconds
private static PROutputs pROutput = new PROutputs(); // all outputs from all primeRacer worker threads
private volatile static boolean finished = false; // the finish flag -- polled by primeRacer worker threads
private static boolean initialised = false; // to check whether all the threads are initialised before actual run codes execute

// instance variables for primeRacers
// Note: primeRacers are worker threads which execute the run() method of the PrimeRace class
private int blocksize;
private String pName;
private int pLane;
private PrimeGeneratorInterface pg;
private ArrayList pList; // the list of primes generated by this primeRacer

public PrimeRace( ) {
// Note: the instance variables of primeRacers are initialized by main().
}

public void run() {
while (!initialised) {
// waiting till all threads are initialised
System.out.println("Waitings till all threads are initialised");
}
while( !finished ) {
pList = pg.generateAnotherBlockOfPrimes( blocksize ); // generate primes as fast as possible
}
pROutput.postResults( pLane, pList ); // report a list of primes, then terminate.
}

public static void main( String[] args ) {

// references to our PrimeRacers
ArrayList primeRacerThreads = new ArrayList();
ArrayList primeRacerNames = new ArrayList();

//Check arguments, entering them into argvec
ArrayList argvec = null;
try{
argvec = checkArgs( args );
} catch (Exception e) {
System.out.println("Usage: PrimeRace t n1 b1 n2 b2 ... ni bi");
System.out.println(" -- where t is the time limit, in milliseconds, for this computation;");
System.out.println(" -- ni is the prime number generation method used by the i-th worker thread,");
System.out.println(" ---- ni = 1, for a Sieve of Eratosthenes");
System.out.println(" ---- ni = 2, for a naive algorithm in Goetz's Introduction to Java threads");
System.out.println(" ---- ni = 3, for a probabilistic prime finder in Java.math.BigInteger");
System.out.println(" -- bi is the blocksize: the number of ints to be checked for primality");
System.out.println(" by ni, between its polls of the time-limit flag");
System.out.println(" -- Note that a large bi value makes it more likely that the i-th thread");
System.out.println(" will win the race to generate the most primes, because it will finish");
System.out.println(" checking its current block of ints for primality before terminating.");
System.exit(1);
}

// construct the primeRacers by interpreting the argvec
Iterator i = argvec.iterator();

// the first arg is the timeLimit (a class variable)
timeLimit = i.next();

// the remaining args are method# and blocksize parameters for each primeRacer
int lane = 0;
while( i.hasNext() ) {

lane++; // add a new lane
pROutput.addLane();

// instantiate and initialize a new primeRacer
PrimeRace t = new PrimeRace( );
t.pLane = lane;
switch( i.next() ) {
case 1:
t.pName = "Eratosthenes" + lane;
t.pg = new EratosthenesGen();
break;
case 2:
t.pName = "Naive" + lane;
t.pg = new NaiveGen();
break;
case 3:
t.pName = "JavaMath" + lane;
t.pg = new JavaMathGen();
break;
}
t.blocksize = i.next();

// main() needs to have a list of all racer threads, for the join().
// All racers will be terminated by the time main() prints the results,
// so main() also keeps a list of names
primeRacerThreads.add( t );
primeRacerNames.add( t.pName );

// t is now ready to run -- it's on the "starting block" of our racecourse

// There's no "starting gun"!! primeRacers start as soon as they're ready.
// Nobody said this would be a fair race ;-)
t.start();
}

// initialised is set to true after all threads are initialised
initialised = true;

// All primeRacers have been started. The main thread sleeps until the end of the race.
try {
Thread.sleep( timeLimit );
}
catch (InterruptedException e) {
System.out.println("Interrupted Exception to sleep() was ignored in main()!");
// If the println() above produces any console output, then this fall-through is unsafe.
// But, most likely, the exception was raised by a ^c console input that is terminating the
// entire JVM -- in which case, the println() above will not produce any console output and main()
// will be abnormally terminated very soon.
}

// Time's up! All primeRacers will stop generating primes after they finish their current block
finished = true;

System.out.println("The race is over. Waiting for primeRunners to finish & report..." );
long tFinish = System.currentTimeMillis();

// The main thread waits (patiently and trustingly ;-) for all racers to terminate.
Iterator j = primeRacerThreads.iterator();
int pc = 1;
while( j.hasNext() ) {
try {
j.next().join(); // blocks main() until racer #j has stopped running
System.out.println( "The primeRunner in lane " + pc + " joined main() "
+ (System.currentTimeMillis()-tFinish)
+ " msec after the race was over." );
} catch (InterruptedException e){
System.out.println("Interrupted Exception to join() was ignored in main()!");
// If the println() above produces any console output, then this fall-through is unsafe.
// However it's most likely that the exception was raised by a ^c console input which is terminating the
// entire JVM -- in which case, the println() above will not produce any console output and main()
// will be abnormally terminated very soon.
}
}

// Who won? Was there any disagreement on which numbers are prime?
Iterator kn = primeRacerNames.iterator();
Iterator> kp = pROutput.get().iterator();
while( kp.hasNext() ) {
ArrayList kl = kp.next();
if( kl.size() <= 5 ) {
System.out.println( kn.next() + ":" + kl.toString() + ". Found "
+ kl.size() + " primes." );
} else {
Iterator kpp = kl.iterator();
System.out.println( kn.next() + ": " + kpp.next() + ", " + kpp.next() + ", " + kpp.next() +
" ... " + kl.get( kl.size() - 2 ) + ", " + kl.get( kl.size() - 1 ) + ". Found "
+ kl.size() + " primes." );
}
}

System.out.println("The fastest primeRunner was in lane " + pROutput.lanesOfLongestLists().toString() );
System.out.println("Most primes found: " + pROutput.longest() );
System.out.println("Least primes found: " + pROutput.shortest() );
} // end main

public static ArrayList checkArgs( String [] args ) throws Exception {
// Validate input, copying it into argvec
// Note: this is a static method, so main() can access it easily. (Worker threads
// don't use this routine.)
ArrayList argvec = new ArrayList();
// There must be an odd number of args >= 3: at least one worker thread
if( (args.length %2 != 1) || (args.length < 3) ) {
throw new Exception();
} else {
// read args into argvec, checking bounds
for( int i=0; i Integer a = Integer.valueOf(args[i]); // todo: an exception is possible here, is it handled correctly?
if( a <= 0 ) { // all inputs must be greater than zero
throw new Exception();
} else if ( (i%2 == 1) && (( a < 1) || ( a > 3)) ) { // 1 <= ni <= 3, for all i
throw new Exception();
} else {
argvec.add( a );
}
}
}
return argvec;
} //end checkArgs
}

package atomicboolean;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.concurrent.atomic.AtomicBoolean;

import primea2.EratosthenesGen;
import primea2.JavaMathGen;
import primea2.NaiveGen;
import primea2.PROutputs;
import primea2.PrimeGeneratorInterface;

public class PrimeRace extends Thread {
// This code is adapted from A. Turner, "AtomicInteger, Volatile, Synchronized and Raw:
// Performance and Safety", NerdsCentral blogspot, 24 November 2011. Available:
// Nerds Central: AtomicInteger, Volatile, Synchronized and Raw: Performance and safety

private static int timeLimit = 0; // how long the "race" will run, in milliseconds
private static PROutputs pROutput = new PROutputs(); // all outputs from all primeRacer worker threads
private static AtomicBoolean finished = new AtomicBoolean(); // the finish flag -- polled by primeRacer worker threads

// instance variables for primeRacers
// Note: primeRacers are worker threads which execute the run() method of the PrimeRace class
private int blocksize;
private String pName;
private int pLane;
private PrimeGeneratorInterface pg;
private ArrayList pList; // the list of primes generated by this primeRacer

public PrimeRace( ) {
// Note: the instance variables of primeRacers are initialized by main().
}

public void run() {
while( !finished.get() ) {
pList = pg.generateAnotherBlockOfPrimes( blocksize ); // generate primes as fast as possible
}
pROutput.postResults( pLane, pList ); // report a list of primes, then terminate.
}

public static void main( String[] args ) {

// references to our PrimeRacers
ArrayList primeRacerThreads = new ArrayList();
ArrayList primeRacerNames = new ArrayList();

//Check arguments, entering them into argvec
ArrayList argvec = null;
try{
argvec = checkArgs( args );
} catch (Exception e) {
System.out.println("Usage: PrimeRace t n1 b1 n2 b2 ... ni bi");
System.out.println(" -- where t is the time limit, in milliseconds, for this computation;");
System.out.println(" -- ni is the prime number generation method used by the i-th worker thread,");
System.out.println(" ---- ni = 1, for a Sieve of Eratosthenes");
System.out.println(" ---- ni = 2, for a naive algorithm in Goetz's Introduction to Java threads");
System.out.println(" ---- ni = 3, for a probabilistic prime finder in Java.math.BigInteger");
System.out.println(" -- bi is the blocksize: the number of ints to be checked for primality");
System.out.println(" by ni, between its polls of the time-limit flag");
System.out.println(" -- Note that a large bi value makes it more likely that the i-th thread");
System.out.println(" will win the race to generate the most primes, because it will finish");
System.out.println(" checking its current block of ints for primality before terminating.");
System.exit(1);
}

// construct the primeRacers by interpreting the argvec
Iterator i = argvec.iterator();

// the first arg is the timeLimit (a class variable)
timeLimit = i.next();

// the remaining args are method# and blocksize parameters for each primeRacer
int lane = 0;
while( i.hasNext() ) {

lane++; // add a new lane
pROutput.addLane();

// instantiate and initialize a new primeRacer
PrimeRace t = new PrimeRace( );
t.pLane = lane;
switch( i.next() ) {
case 1:
t.pName = "Eratosthenes" + lane;
t.pg = new EratosthenesGen();
break;
case 2:
t.pName = "Naive" + lane;
t.pg = new NaiveGen();
break;
case 3:
t.pName = "JavaMath" + lane;
t.pg = new JavaMathGen();
break;
}
t.blocksize = i.next();

// main() needs to have a list of all racer threads, for the join().
// All racers will be terminated by the time main() prints the results,
// so main() also keeps a list of names
primeRacerThreads.add( t );
primeRacerNames.add( t.pName );

// t is now ready to run -- it's on the "starting block" of our racecourse

// There's no "starting gun"!! primeRacers start as soon as they're ready.
// Nobody said this would be a fair race ;-)
t.start();
}

// All primeRacers have been started. The main thread sleeps until the end of the race.
try {
Thread.sleep( timeLimit );
}
catch (InterruptedException e) {
System.out.println("Interrupted Exception to sleep() was ignored in main()!");
// If the println() above produces any console output, then this fall-through is unsafe.
// But, most likely, the exception was raised by a ^c console input that is terminating the
// entire JVM -- in which case, the println() above will not produce any console output and main()
// will be abnormally terminated very soon.
}

// Time's up! All primeRacers will stop generating primes after they finish their current block
finished.set(true);

System.out.println("The race is over. Waiting for primeRunners to finish & report..." );
long tFinish = System.currentTimeMillis();

// The main thread waits (patiently and trustingly ;-) for all racers to terminate.
Iterator j = primeRacerThreads.iterator();
int pc = 1;
while( j.hasNext() ) {
try {
j.next().join(); // blocks main() until racer #j has stopped running
System.out.println( "The primeRunner in lane " + pc + " joined main() "
+ (System.currentTimeMillis()-tFinish)
+ " msec after the race was over." );
} catch (InterruptedException e){
System.out.println("Interrupted Exception to join() was ignored in main()!");
// If the println() above produces any console output, then this fall-through is unsafe.
// However it's most likely that the exception was raised by a ^c console input which is terminating the
// entire JVM -- in which case, the println() above will not produce any console output and main()
// will be abnormally terminated very soon.
}
}

// Who won? Was there any disagreement on which numbers are prime?
Iterator kn = primeRacerNames.iterator();
Iterator> kp = pROutput.get().iterator();
while( kp.hasNext() ) {
ArrayList kl = kp.next();
if( kl.size() <= 5 ) {
System.out.println( kn.next() + ":" + kl.toString() + ". Found "
+ kl.size() + " primes." );
} else {
Iterator kpp = kl.iterator();
System.out.println( kn.next() + ": " + kpp.next() + ", " + kpp.next() + ", " + kpp.next() +
" ... " + kl.get( kl.size() - 2 ) + ", " + kl.get( kl.size() - 1 ) + ". Found "
+ kl.size() + " primes." );
}
}

System.out.println("The fastest primeRunner was in lane " + pROutput.lanesOfLongestLists().toString() );
System.out.println("Most primes found: " + pROutput.longest() );
System.out.println("Least primes found: " + pROutput.shortest() );
} // end main

public static ArrayList checkArgs( String [] args ) throws Exception {
// Validate input, copying it into argvec
// Note: this is a static method, so main() can access it easily. (Worker threads
// don't use this routine.)
ArrayList argvec = new ArrayList();
// There must be an odd number of args >= 3: at least one worker thread
if( (args.length %2 != 1) || (args.length < 3) ) {
throw new Exception();
} else {
// read args into argvec, checking bounds
for( int i=0; i Integer a = Integer.valueOf(args[i]); // todo: an exception is possible here, is it handled correctly?
if( a <= 0 ) { // all inputs must be greater than zero
throw new Exception();
} else if ( (i%2 == 1) && (( a < 1) || ( a > 3)) ) { // 1 <= ni <= 3, for all i
throw new Exception();
} else {
argvec.add( a );
}
}
}
return argvec;
} //end checkArgs
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.