Programming Praxis

Pairs of prime numbers that differ by two are known as twin primes: (3,5), (5,7), (11,13), (17,19), (29,31), (41,43), (59,61), (71,73), …. Sometimes the list is given by the lowest number in the pair (A001359: 3, 5, 11, 17, 29, 41, 59, 71, …), sometimes by the highest number in the pair (A006512: 5, 7, 13, 19, 31, 43, 61, 73, …), sometimes by the number in between (A014574: 4, 6, 12, 18, 30, 42, 60, 72, …), and sometimes just as a list of primes (A001097: 3, 5, 7, 11, 13, 17, 19, 29, 31, 41, 43, 59, 61, 71, 73, …). All twin primes have the form 6k±1.

It is simple and fast to compute the twin primes less than n by a variant of the Sieve of Eratosthenes. The sieving primes are the primes less than the square root of n, excluding 2 and 3 which are not of the form 6k±1. In the first step, the primes of the form 6k−1 are sieved; first make a bitarray for the numbers 5, 11, 17, 23, 29, …, then, for each sieving prime p, find the smallest multiple of the prime in the list, strike it off the list, and strike each pth number off the list as well. In the second step, the primes of the form 6k+1 are sieved; first make a bitarray for the numbers 7, 13, 19, 25, 31, …, then, for each sieving prime p, find the smallest multiple of the prime in the list, strike it off the list, and strike each pth number off the list as well. In the third step, sweep through the pair of bitarrays and collect twin primes for each remaining pair of corresponding bitarray elements.

The smallest multiple of a prime p of the form 6k−1 is the modular inverse of 6 mod p; the smallest multiple of a prime p of the form 6k+1 is the modular inverse of −6 mod p. Be sure not to strike the prime p. We discussed the modular inverse in a previous exercise.

An alternative method to compute twin primes is to use the normal Sieve of Eratosthenes to compute the primes less than n, then sweep through the list comparing each prime to its successor. But the algorithm given above is faster, about twice as fast, because the two bitarrays are shorter than the single bitarray of the normal Sieve of Eratosthenes.

Your task is to write a function that finds the twin primes less than a given input n. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2