一、题目

If we define dn as: dn = pn+1-pn, where pi is the i-th prime. It is easy to see that d1 = 1 and dn=even for n>1. Twin Prime Conjecture states that “There are infinite consecutive primes differing by 2”.
Now given any positive integer N (< 10^5), you are supposed to count the number of twin primes which are no greater than N.
Input
Your program must read test cases from standard input.
The input file consists of several test cases. Each case occupies a line which contains one integer N. The input is finished by a negative N.
Output
For each test case, your program must output to standard output. Print in one line the number of twin primes which are no greater than N.
Sample
Inputcopy Outputcopy
1
5
20
-2
0
1
4

二、分析

预处理ans数组，最后输出只需要O(1)的复杂度
Twin Prime指的是相差为2 的素数
20以内的素数：
2 3 5 7 11 13 17 19
其中有以下4对Twin Prime：(2,5),(5,7),(11,13),(17,19)

#include
using namespace std;
const int N=1e5+5;
int a[N];
int ans[N];
int main()
{for(int i=2;i<=N/i;i++){for(int j=i*i;j<N;j+=i){a[j]=1;//表示不是素数}}int cnt=0;a[0]=1,a[1]=1;for(int i=2;i<=N;i++){if(a[i]==0&&a[i-2]==0) cnt++;ans[i]=cnt;}int n;while(cin>>n&&n>=0){cout<<ans[n]<<endl;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！