让我们定义dn为:dn=pn+1−pn,其中pi是第i个素数。显然有d1=1,且对于n>1有dn
是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。
现给定任意正整数N(<10^5),请计算不超过N的满足猜想的素数对的个数。
输入格式:
输入在一行给出正整数N。
输出格式:
在一行中输出不超过N的满足猜想的素数对的个数。
#include <iostream>
#include <cmath>
using namespace std;
const int N = 100010;
int primes[N], cnt;
bool st[N];
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
//这个循环用于标记素数和它的倍数为非素数。循环变量j从0开始,循环条件是primes[j]小于等于n/i,即只需要考虑小于i的素数。对于每一个小于i的素数primes[j],将primes[j]*i标记为非素数(即将st[primes[j]i]设置为true)。如果i能够被primes[j]整除,说明iprimes[j+1]也一定能够被primes[j]整除,因此没有必要继续枚举primes[j]的倍数了,直接退出循环。
for (int j = 0; primes[j] <= n / i; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
int main()
{
int n;
cin >> n;
get_primes(n);
int res = 0;
for (int i = 0; i < cnt - 1; i ++ )
if (primes[i + 1] - primes[i] == 2)
res ++ ;
cout << res << endl;
return 0;
}