PAT Basic 1007

#include<stdio.h>
#include<math.h>
int a[100000]={0};
int main()
{
	int n,i,j,flag,count=0;
	scanf("%d",&n);
	a[2]=a[3]=1;

	for(i=5;i<=n;i=i+2)
	{
		flag=1;
		for(j=3;j<=sqrt(i);j++)
		{
			if(a[j]==1)
				if(i%j==0)
					flag=0;
		}
		a[i]=flag;
	}
	i=3;
	/*遍历素数对*/
	while(i+2<=n)
	{
		if(a[i+2]==1 && a[i]==1 )
			count++;
		i=i+2;
	}
	printf("%d\n",count);
	return 0;
}