CIT 594 Assignment 8: Counting prime numbers
Spring 2013, David Matuszek

# Purposes of this assignment

• To familiarize you with concurrency and Java's ForkJoin framework

# General idea of the assignment

Count how many prime numbers there are below:

• 1000
• 1000000 (one million)
• 10000000 (ten million)
• 100000000 (one hundred million)
• 1000000000 (American one billion, English one thousand million).
• Turn in your program without this last timing. The sequential version below takes 92 seconds on my computer, which is too long to wait for a program to finish when we are grading 40 of them.

Time each of these, and print out the time required along with the count of primes. Also tell us (print out) the number of cores your computer has.

Use ForkJoin as described in:

After getting your program to work, try to get it as fast as possible. We won't be grading on speed, but you should experiment a bit to get a feel for what helps and what doesn't. Pay special attention to the nine "Timing Issues" in the Beginner's Introduction linked to above.

Here's some sequential code you can use to get started. Feel free to use it, improve it, or ignore it.

package primes;

public class PrimeCounter {

/** Sequential program to count primes below some limits. */
public static void main(String[] args) {
for (int limit = 1000; limit < 1000000000; limit *= 10) {
long start = System.nanoTime();
int n = countPrimes(limit);
long finish = System.nanoTime();
System.out.println(n + " primes less than " + limit);
System.out.println("Time: " + ((finish - start) / 1e9) + " seconds.\n");
}
System.out.println("Done.");
}

/** Count the number of primes below n. */
private static int countPrimes(int n) {
int count = 0;
for (int i = 2; i <= n; i++) {
if (isPrime(i)) count += 1;
}
return count;
}

/** Return true iff n is a prime number. */
private static boolean isPrime(int n) {
if (n == 1) return false;
if (n == 2 || n == 3) return true;
if (n % 2 == 0) return false;
int limit = (int)(Math.sqrt(n)+ 0.5);
for (int i = 3; i <= limit; i += 2) {
if (n % i == 0) return false;
}
return true;
}
}

# Due date

Your program is due before 6am Thursday, April 11. Zip up the entire directory for this project, and submit via Canvas.