CIT 594 Assignment 8: Counting prime numbers

Spring 2013, David Matuszek

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

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.

- Turn in your program

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:

- Introduction to Multithreading and Fork-Join Parallelism pptx pdf
- Beginner's Introduction to Java's ForkJoin Framework
- My own (brief) ForkJoin PPT lecture

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; } }

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