PAT-B1007 素数对猜想
程序员文章站
2024-03-15 16:36:42
...
PAT-B1007 素数对猜想
题目描述:
让我们定义dn为:dn = pn+1 − pn,其中pi是第i个素数。显然有d1=1,且对于n>1有*dn*是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。
现给定任意正整数N
(<105),请计算不超过N
的满足猜想的素数对的个数。
输入格式:
输入在一行给出正整数N
。
输出格式:
在一行中输出不超过N
的满足猜想的素数对的个数。
输入样例:
20
输出样例:
4
代码:
#include <cstdio>
#include <cmath>
bool isPrime(int n) { //判断n是否为素数
if(n <= 1) return false;
int sqr = (int)sqrt(1.0 * n);
for(int i = 2; i <= sqr; i++) {
if(n % i == 0) return false;
}
return true;
}
int main() {
int n, count = 0;
scanf("%d", &n);
for(int i = 3; i + 2 <= n; i += 2) { //i每次加2
if(isPrime(i) == true && isPrime(i + 2) == true) {
count++; //如果i和i + 2都是素数,那么count加1
}
}
printf("%d\n", count);
return 0;
}
上一篇: PAT_B_1007 素数对猜想