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

Purposes of this assignment

General idea of the assignment

Count how many prime numbers there are below:

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.