让我们定义$d_n$为:$d_n=p_{n+1}−p_n$,其中$p_i$是第i个素数。显然有$d_1=1$,且对于n>1有$d_n$是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。
现给定任意正整数N
($<10^5$),请计算不超过N
的满足猜想的素数对的个数。
输入格式:
输入在一行给出正整数N
。
输出格式:
在一行中输出不超过N
的满足猜想的素数对的个数。
输入样例:
输出样例:
思路
定义i从2开始到遍历至n,每次判断i和i+2是否均为素数
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| #include <iostream>
using namespace std;
bool prime(int n) { if(n == 1) { return false; } for(int i = 2; i * i <= n; i++) { if(n % i == 0) { return false; } } return true; }
int main() { int n; scanf("%d", &n); int ret = 0; for(int i = 2; i + 2 <= n; i++) { if(prime(i) && prime(i + 2)) { ret++; } } printf("%d\n", ret); return 0; }
|
也可使用素数筛,题目中N最大为105。于是把1~105的素数先筛选出来,效率会很大提高
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| #include <iostream>
using namespace std;
bool book[(long)1e5 + 1]; void func(int n) { book[1] = true; for(int i = 2; i <= n; i++) { if(!book[i]) { for(int j = 2 * i; j <= n; j+=i) { book[j] = true; } } } }
int main() { int n; scanf("%d", &n); int ret = 0; func(n); for(int i = 1; i + 2 <= n; i++) { if(!book[i] && !book[i + 2]) { ret++; } } printf("%d\n", ret); return 0; }
|