Twin Primes, SPOJ solution, prob no.10394
This is the problem I found at the SPOJ coding platform. If someone has given multiple attempts and still getting TLE (most probably), then this blog may be proven successful to you.
Here is the problem statement:-
Q.Twin primes are pairs of primes of the form (p, p + 2). The term “twin prime” was coined by Paul Stckel (1892–1919). The first few twin primes are (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43). In this problem, you are asked to find out the S-th twin prime pair where S is an integer that will be given in the input.
INPUT
The input will contain less than 10001 lines of input. Each line contains an integers S (1 ≤ S ≤ 100000), which is the serial number of a twin prime pair. The input file is terminated by the end of the file.
OUTPUT
For each line of input, you will have to produce one line of output which contains the S-th twin prime pair. The pair is printed in the form (p1,¡space¿p2). Here ¡space¿ means the space character (ASCII 32). You can safely assume that the primes in the 100000th twin prime pair are less than 20000000.
Sample Input
1
2
3
4
Sample Output
(3, 5)
(5, 7)
(11, 13)
(17, 19)
//I would recommend trying solving using the concept of the sieve of Erasthanose first.
Now, I won’t let you wait for any more to reach the right approach and solution, henceforth. So, here goes the approach and the solution how did I try to approach this problem got it accepted in the very first attempt.
Approach in brief
Using sieve of Erasthanose, I filled up the used array “prime” with the value of “true” whose index no are prime and remaining “false”, like the value of 2,3,4,5,6 are true, true, false, true, false respectively.
After that, I used the “map” data structure and started filling it with i-th twin prime pair(where i is 1,2,3……). Below are the screenshots of the solution.
Do leave your valuable comments, would be appreciated.
Leaving with a smile.Thanks.