UVA 10394 Twin Primes

Twin Primes
Input: standard input
Output: standard output
Time Limit: 30 seconds

Twin primes are pairs of primes of the form (p, p+2). The term "twin prime" was coined by Paul Stäckel (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)

题意：输入一个n，输出第n对孪生素数。孪生素数的定义：如果i和i+2都是素数，则称i和i+2是一对孪生素数。问题的重点就是判断素数和孪生素数。如果用普通的判断素数的方法，肯定会超时，因此需要用一种比较快速的判断素数的方法。这里用的是筛选法。筛选法是一种高效的判断素数的方法，能够一次性的筛选出某个区间的素数。其算法原理本质还是充分利用了素数的定义，即素数的约数只有1和它本身。如果某个数m是另一个数n的倍数，则说明m肯定不是素数。所以我们只要在某个范围内，将已知素数的所有倍数都筛去，剩下的肯定是素数。因为只有它不是其他数的倍数（1和本身除外）。

具体做法是：先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数

#include<stdio.h>
#include<math.h>
#define N 20000000+5
int a[100005],prime[N];
void deal() /*区分素数和合数*/
{
	int i,j;
	for(i=2;i<=N;i++)
		prime[i]=1;
	for(i=2;i<=sqrt(N);i++)
	{
		if(prime[i])
			for(j=i+i;j<=N;j+=i)
				prime[j]=0;
	}
}
void judge() /*判断孪生素数*/
{
	int i,j;
	for(i=3,j=1;;i+=2)
	{
		if(prime[i]==prime[i+2]&&prime[i]==1)
			a[j++]=i;
		if(j>100000)
			break;
	}
}
int main()
{
	int n;
	deal();
	judge();
	while(~scanf("%d",&n))
		printf("(%d, %d)\n",a[n],a[n]+2);
	return 0;
}

补充：软件开发 , C++ ,