Twin Primes
Twin primes are pairs of primes of the form (p; p + 2). The term \twin prime" was coined by Paul
Stckel (1892-1919). The rst few twin primes are (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43).
In this problem you are asked to nd 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 le is terminated by end of le.
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)Twin primes are pairs of primes of the form (p; p + 2). The term \twin prime" was coined by Paul
Stckel (1892-1919). The rst few twin primes are (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43).
In this problem you are asked to nd 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 le is terminated by end of le.
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)
题意:
定义双素数(p,p+2),p,p+2都为素数。
先输入若干个n,输出第n对双素数。
分析:
时间限制为3000ms,数据量为2e7,可以直接暴力求解。
首先用欧拉筛筛出所有素数,然后暴力枚举所有素数,判断是否是双素数即可。
AC code:
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> P; P p[20000005]; bool u[20000005]; int su[20000005]; int num; void olas() { num=1; memset(u,true,sizeof(u)); for(int i=2;i<=20000000;i++) { if(u[i]) su[num++]=i; for(int j=1;j<num;j++) { if(i*su[j]>20000000) break; u[i*su[j]]=false; if(i%su[j]==0) break; } } } int main() { //freopen("input.txt","r",stdin); int n; olas(); int num=0; for(int i=2;i<=20000000-2;i++) { if(u[i]&&u[i+2]) { p[num++]=P(i,i+2); } } while(~scanf("%d",&n)) { printf("(%d, %d)\n",p[n-1].first,p[n-1].second); } return 0; }View Code