Part 1: The Sieve of Eratosthenes

A prime number is an integer that is greater than 1 that is evenly divisible only by itself

and 1. For example, 2, 3, 5, and 11 are prime numbers, but 4, 9, and 22 are not.

The Sieve of Eratosthenes is an ancient and extremely simple way to identify all the

prime numbers less than a given value n. The sieve works as follows:

1.Start by listing all the integers from 2 through n.

2.Begin with 2 and cross out (eliminate, or mark) all integers that are greater than 2 that

are multiples of 2 (for example, eliminate 4, 6, 8, 10, etc.).

3. Find the next unmarked integer and remove all of its multiples from the list (except for

the number itself). For example, the ?rst unmarked integer after 2 is 3, so we remove

or mark the unmarked multiples of 3 that are greater than 3 (6, 9, 12, etc.).

4. Repeat this multiple-marking process for each next unmarked number in turn, until we

reach the end of the list.

5.At the end of this process, all the remaining unmarked numbers are prime; the

marked numbers are composite (non-prime) values.

For example, here is an example using the sieve algorithm to ?nd all prime integers less

than 30 (marked numbers are replaced by an X):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

2 3 X 5 X 7 X 9 X 11 X 13 X 15 X 17 X 19 X 21 X 23 X 25 X 27 X 29 X (mark 2s)

2 3 X 5 X 7 X X X 11 X 13 X X X 17 X 19 X X X 23 X 25 X X X 29 X (mark 3s)

2 3 X 5 X 7 X X X 11 X 13 X X X 17 X 19 X X X 23 X X X X X 29 X (mark 5s)

2 3 X 5 X 7 X X X 11 X 13 X X X 17 X 19 X X X 23 X X X X X 29 X (mark 7s)

2 3 X 5 X 7 X X X 11 X 13 X X X 17 X 19 X X X 23 X X X X X 29 X (mark 11s)

2 3 X 5 X 7 X X X 11 X 13 X X X 17 X 19 X X X 23 X X X X X 29 X (mark 13s)

etc.

(Note that, as a shortcut, you can stop marking once you have passed n/2)

Complete the sieve() method. This method takes an integer value n as its argument,

where 2 ? n ? 1500), and returns an ArrayList of integers containing all the prime

numbers between 2 and n, inclusive, in ascending order. Assume that unmarked

positions in your working array have a value of 0; marked positions contain a 1.

ISE 208: Intermediate Programming! Spring 2014

Part 2: Twin Primes

A twin prime is a prime number that differs from another prime number by exactly 2. For

example, 3 and 5 are twin primes, since 3 and 5 are each prime and differ by 2

(likewise, 5 and 7 are also twin primes).

Complete the twins() method, which takes an integer argument n and prints all the

sets of twin primes that are less than n, one pair per line. The method does not return

any value. For example, twins(15) would print

(3, 5)

(5, 7)

(11, 13)

Use the sieve() method from Part 1 to generate the initial list of prime numbers.