首页 > 代码库 > 1007. 素数对猜想 (20) （ZJUPAT 数学）
1007. 素数对猜想 (20) （ZJUPAT 数学）
题目链接：http://pat.zju.edu.cn/contests/pat-b-practise/1007
让我们定义 dn 为：dn = pn+1 - pn，其中 pi 是第i个素数。显然有 d1=1 且对于n>1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。
现给定任意正整数N (< 105)，请计算不超过N的满足猜想的素数对的个数。
输入格式：每个测试输入包含1个测试用例，给出正整数N。
输出格式：每个测试用例的输出占一行，不超过N的满足猜想的素数对的个数。
输入样例：20输出样例：
4
思路：
我们先打表出前10000的所有素数，然后在判断1到n相差为2的相邻素数个数即可！
代码如下：
#include <cstdio>
#include <cstring>
int a[100017];
void init()
{
memset(a,0,sizeof(a));
for(int i = 2; i <= 100000; i++)
{
if(a[i] == 0)
for(int j = i+i; j <= 100000; j+=i)
{
a[j] = 1;
}
}
}
void solve(int n)
{
int k = 0;
int tt = 2;
for(int i = 3; i <= n; i++)
{
if(a[i] == 0)
{
if(i-tt == 2)
k++;
tt = i;
}
}
printf("%d\n",k);
}
int main()
{
int n;
init();
while(~scanf("%d",&n))
{
solve(n);
}
return 0;
}
1007. 素数对猜想 (20) （ZJUPAT 数学）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。