素数对

题目描述

60秒，1亿以内的素数对有几个？

输入格式

无

输出格式

素数对个数

输入输出样例

输入样例#1

无

输出样例#1

不告诉

代码

#include<bits/stdc++.h>
using namespace std;
int a[100000000]; 
void init()//初始化，素数筛 
{
   
    memset(a,0,sizeof(a));
    double m = sqrt(100000000);
    for(int i=2;i<=m;i++)
    {
   
        for(int j=i*i;j<=100000000;j+=i)
        {
   
            if(!a[j])
            {
   
                a[j]=1;
            }
        }
    }
}
int main()
{
   
	init();
	int n,jsq=0;
	cin>>n;
	for(int i=3;i<n;i++)
	{
   
	    if(!a[i]&&!a[i+2])
	    {
   
	        jsq++;
	    }
	}
	cout<<jsq;
}