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

2

3

4

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;
}