Lab 04: Primes!
generating primes quickly
DUE: Friday, April 16, 23:59 AoE
Background
Recall that a prime number is a an integer \(p > 1\) that is not divisible by any number \(d\) strictly between \(1\) and \(p\). For example, the first few prime numbers are \(2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29,\ldots\). A number \(n > 1\) that is not prime is said to be composite. Prime numbers have many applications in computer science, notably in the RSA encryption scheme—currently the most widely used public key encryption scheme.
The Sieve of Eratosthenes
The problem of computing prime numbers has fascinated mathematicians for millenia. One of the earliest recorded methods for producing prime numbers (and indeed, one of the earliest recorded algorithms for any problem) is the Sieve of Eratosthenes (SoE). For any value of \(N\), the SoE produces all of the primes between \(1\) and \(N\). The basic idea is as follows:
 Write all numbers from \(2\) to \(N\) consecutively, and start reading the numbers in order.
 Whenever a new number is read:
 if the number is marked as composite, continue
 otherwise, if the number is not marked, mark it as prime; then mark all multiples of the number as composite
For example, we can generate the prime numbers up to 20:
1
02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20
In the first iteration of step 2 above, we’ll mark 2 as prime, and mark all of the multiples of 2 to be composite:
1
2
02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20
PP cc cc cc cc cc cc cc cc cc
In the next iteration, we see the 03 is the next unmarked number, so we mark it as prime, and remove all of its multiples:
1
2
02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20
PP PP cc cc cc cc cc cc cc cc cc cc cc
Now 5 is the next unmarked number, so we mark it as prime, and mark its multiples as composite:
1
2
02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20
PP PP cc PP cc cc cc cc cc cc cc cc cc cc
Continuing in this way, we’ll reach the state
1
2
02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20
PP PP cc PP cc PP cc cc cc PP cc PP cc cc cc PP cc PP cc
from which we can infer that the primes up to \(20\) are
1
02 03 05 07 11 13 17 19
An Optimization
This process can be optimized somewhat. If a number \(n \leq N\) is composite, then it has a divisor that is at most \(\sqrt{N}\). (To see this, suppose \(n = a \cdot b\) with \(a, b > \sqrt{N}\). Then \(a \cdot b > \sqrt{N} \cdot \sqrt{N} = N\). Thus if \(n\) is composite—i.e., \(n = a \cdot b\) for some \(a, b\) satisfying \(1 < a, b < n\) and \(n \leq N\), then we must have either \(a \leq \sqrt{N}\) or \(b \leq \sqrt{N}\).) Therefore, if we have marked numbers with divisors at most \(\sqrt{N}\) as composite and some number \(n < N\) has not been marked as composite, then we can infer that \(n\) is prime.
Implementing the Sieve of Eratosthenes
To implement the SoE in Java, we can store which numbers are prime/composite as an array of Boolean values. Specifically, we can create an array boolean[] isPrime
, with the interpretation that isPrime[i]
should be true
if i
is prime, and false
if i
is composite. Using the optimization described above, we can implement the sieve as follows:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
boolean[] isPrime = new boolean[MAX];
// initialize isPrime[i] to true for i >= 2
for (int i = 2; i < MAX; ++i) {
isPrime[i] = true;
}
// apply the Sieve of Eratosthenes
for (int i = 0; i < MAX; ++i) {
if (isPrime[i]) {
if (i < ROOT_MAX) {
int j = 2 * i;
while (true) {
isPrime[j] = false;
if (j >= MAX  i) {
break;
}
j += i;
}
}
}
}
When the method above completes, isPrime
will have the property that isPrime[i]
is true
precisely when i
is prime. It is then straightforward to use the array isPrime
to list all of the primes up to MAX  1
: read through the array and print each index i
with isPrime[i] == true
.
Your Task
For this lab you will write a program ParallelPrimes.java
that computes as many primes as possible in one second. Specifically, your program must generate an array int[] primes
that contains as many consecutive primes as possible:
1
2
3
4
primes[0] = 2;
primes[1] = 3;
primes[2] = 5;
...
To this end, you should complete an implementation of ParallelPrimes.java
(linked below). The program will give you access to a thread pool for exactly 1 second before terminating all active and pending tasks in the pool. It then compares the generated int[] primes
to an array of known primes and prints the first index at which the two arrays differ.
To get started, download the following files:
You should modify ParallelPrimes.java
to perform your multithreaded implementation. You may use Primes.java
as well in your implementation.
Grading
Your program will be graded on a 6 point scale according to the following criteria:

Correctness (2 pts). The program correctly produces primes using multithreading. The individual tasks handle interrupts gracefully and the threads in the thread pool terminate within 50ms of termination (i.e., the entire runtime is at most 1050ms).

Performance (2 pts). The program produces a number of primes comparable to the benchmark program. (The results of sample benchmark runs will be provided soon.)

Style & Documentation (2 pts). Code is wellorganized and commented. Submission includes a
README
file that describes your program at a high level, and briefly discusses optimizations and tests performed.
Suggestions
Optimization of SoE and Parallelization
The optimization of the SoE described above suggests a way to parallelize (some of) our computation. Suppose we’ve already computed all primes up to, say 100, and stored these primes in an array int[] smallPrimes
. Since every composite integer up to 10,000 (= 100 x 100) has a prime factor that is at most 100, the SoE will find all primes up to 10,000 after we remove multiples of the primes in smallPrimes
. Moreover, the tasks of finding primes between 1,000 and 1,999 (say) and finding primes between 2,000 and 2,999 can be done indpendently (given shared access to smallPrimes
). This observation suggests a way of breaking down the problem into tasks: first find “sufficiently many” small primes using the sequential SoE, then use these small primes to find larger primes in parallel.
Coordination
Using the SoE to generate an array of primes (as implemented in Primes.java
) consists of two logically distinct steps:
 Compute the array
boolean[] isPrime
.  Use
isPrimes
to compute the actual arrayint[] primes
of prime numbers.
The first step more computationally intensive, but it can be parallelized as suggested above (at least once some small primes are found). The second step is relatively faster, but it should be done sequentially to ensure that the primes appear in sorted order. This suggests using two distinct types of tasks: one type of task that performs step 1 (which can be parallelized), and another type of task that performs step 2. You might invoke many type1 tasks, while a single type2 runs concurrently to write primes.
You may find it useful that Executor
s in Java assign tasks to threads in the order the tasks are added (using the execute
method). This does not guarantee that the first task submitted will be the first task completed. Thus you will need to ensure that the type2 task waits until it has the “next” block of primes to write. To this end, you may find it helpful to use a concurrent data structure in which completed type1 tasks can place their output while the type2 task waits for the appropriate task to be completed. You can find a complete list of builtin concurrent data structures in the Java API documentation here.