UVa 10394 Twin Primes （孪生素数）

UVa 10394 Twin Primes （孪生素数）2014-07-24

10394 - Twin Primes

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1335

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. Input file is terminated by end of 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 100000-th twin prime pair are less than 20000000.

Sample Input
1

Sample Output
（3, 5）

（5, 7）

（11, 13）

（17, 19）

水题。

完整代码：

/*0.342s*/#include <cstdio>const int maxn = 20000000;bool vis[maxn];int prime[maxn / 10], c, TwinPrime[100005];/*以i为基准筛合数*//*O（maxn）时间复杂度*/void cal_prime（）{for （int i = 2; i < maxn; ++i）{if （！vis[i]） prime[c++] = i;for （int j = 0; j < c && i * prime[j] < maxn; ++j）{vis[i * prime[j]] = true;if （i % prime[j] == 0） break;}}}/*判断孪生素数*/inline void judge（）{int i, j;for （i = 3, j = 1; j <= 100000; i += 2）if （！vis[i] && ！vis[i + 2]）TwinPrime[j++] = i;}int main（）{cal_prime（）;judge（）;int n;while （~scanf（"%d", &n））printf（"（%d, %d）
", TwinPrime[n], TwinPrime[n] + 2）;return 0;}

作者署名：csdn博客 synapse7