This is a prime number problem involving the determination of twin
primes. We
are told twin primes are pairs of primes of the form (p, p+2). For example, the first two twin prime pairs
are (3, 5) and (5,
7). The
problem description essentially asks the following: Given an integer S, the serial number of a twin prime
pair, output the Sth
twin
prime pair. The restrictions on S are given as follows. 1 <= S <=100000.
Input is given by 10,000 lines or less, each composed of an integer S that specifies the serial number of the target twin prime pair to be output for that case. Each input line described by integer Sth should have a corresponding output line of the form, (p1, p2), where (p1, p2) is the Sth twin prime pair and p1 = p2+2.
In order to solve this problem we need to use the Sieve of
Eratosthenes to precompute the primes we need, up to the upper bound specified by the problem. Since
each test case will
have an
integer less than or equal to 100,000, and we are allowed to assume primes in the 100,000th twin prime pair
are less than
20,000,000,
we need to precompute primes up to 20,000,000. One version of the Sieve I like to use is one that uses
std::bitset
.
The function is
written as
follows.
Pay close attention to the inner for-loop structure, and make sure you get it right. When under pressure,
this is a common place
to
make typographical errors that lead to frustrating debugging sessions. From main(), we are going to call our
sieve function,
passing M
as a parameter. This computes prime numbers up to M (M = 20,000,000), and stores them in ascending order in
our
std::vector
vp.