hdu 3792 Twin Prime Conjecture n之内的孪生素数个数

Twin Prime Conjecture

Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1425Accepted Submission(s): 432

Problem Description

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 Input

1
5
20
-2

Sample Output

0
1
4

Source

浙大计算机研究生保研复试上机考试-2011年

孪生素数即 两个素数之差为2

问n之内的孪生素数对数

思路： 首先打印素数表 不用记录素数 而是用vis标记这个数是不是素数 之后如果vis[i]以及vis[i-2]都没标记 那么对数加1即可

#include<stdio.h>
#include<math.h>
#include<string.h>
int vis[100000+100];
int prime[80000],c;
int a[100000+10];
void get_prime()
{
	int i,j,n,m;
	c=0;
	n=100000;
	m=(int)sqrt(n+0.5);
	memset(vis,0,sizeof(vis));
	for(i=2;i<=m;i++) if(!vis[i])
	{
		for(j=i*i;j<=n;j+=i) vis[j]=1;//vis的不是素数
	}
//	for(j=2;j<=n;j++) if(!vis[j])
	//	prime[c++]=j;
}
int main()
{
	int  i,j,n,max;
	get_prime();
	n=0;
	a[1]=0;a[0]=0;a[2]=0;a[3]=0;a[4]=0;
	for(i=4;i<=100000;i++)
	{
	//	printf("%d %d\n",!vis[i],!vis[i-2]);
         if(!vis[i]&&!vis[i-2])
		 {
			 n++;
		 }
		 a[i]=n;
	}
	while(i<=100000)
	{
		a[i++]=n;
	}
	while(scanf("%d",&n)!=EOF)
	{
		if(n<0) break;
		printf("%d\n",a[n]);
	}
	return 0;
}