让我们定义 dn 为:dn = pn+1 - pn ,其中 pi 是第i个素数。显然有 d1 =1 且对于n>1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。 现给定任意正整数N (< 105 ),请计算不超过N的满足猜想的素数对的个数。 输入描述: 每个测试输入包含1个测试用例,给出正整数N。 输出描述: 每个测试用例的输出占一行,不超过N的满足猜想的素数对的个数。 输入例子: 20 输出例子: 4
#include
#include
#include
#include
using namespace std;
int main()
{
vector
int k = 0;
int count = 0;
int i = 0, j = 0;
int n = 0;
num.push_back(2);
num.push_back(3);
for (i = 4; i < 100000;i++)
{
if (1 == i%2)
{
count = 0;
k = sqrt(i);
for (j = 2; j <= k;j++)
{
if (0 != i%j)
{
count++;
}
else
{
break;
}
}
if (count == k-1)
{
num.push_back(i);
}
}
}
while (scanf("%d",&n)!=EOF)
{
i = 1;
count = 0;
while (num[i] { if (2 == num[i]-num[i-1]) { count++; } i++; } cout << count << endl; } //copy(num.begin(), num.end(), ostream_iterator return 0; }