PAT（乙级）1007.素数对猜想（20）
PAT 1007.素数对猜想（20）
让我们定义dn为：dn=pn+1−pn，其中pi是第i个素数。显然有d1=1，且对于n>1有dn是偶数。"素数对猜想"认为 “存在无穷多对相邻且差为2的素数”。现给定任意正整数N(<10^5 )，请计算不超过N的满足猜想的素数对的个数。
输入格式：
输入在一行给出正整数N。
输出格式： 在一行中输出不超过N的满足猜想的素数对的个数。
输入样例：
20输出样例：
4题目分析：素数筛选法，O(n^2)求解素数会超时。
AC代码：
#include<cstdio>
#include<cmath>
const int max_n = 100010;
bool p[max_n];
int prime[max_n];
int num = 0;
int main(){
int n;
scanf("%d",&n);
for(int i=2;i<=n;++i){
if(p[i]==false){
prime[num++] = i;
}
for(int j=i+i;j<=n;j+=i){
p[j] = true;
}
}
int cnt = 0;
for(int i=0;i<num-1;++i){
if(prime[i+1]-prime[i]==2){
cnt++;
}
}
printf("%d",cnt);
return 0;
} 本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
