题目描述
让我们定义d[n]为:d[n] =p[n+1] − p[n] ,其中p[i] 是第i个素数。显然有d[1] =1,且对于n>1有d[n] 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。现给定任意正整数N(<100000 ),请计算不超过N的满足猜想的素数对的个数。
输入格式
输入在一行给出正整数N。
输出格式
在一行中输出不超过N的满足猜想的素数对的个数。
输入样例
20
输出样例
4
解题思路
(1)编写一个判断是否为素数的函数。
(2)对小于输入n的所有数字进行判断,若为素数,使用vector进行记录
(3)对相邻的素数进行判断,若满足素数对猜想,则结果加一,注意将结果初始化为0
程序源码
#include <iostream>
#include <vector>
using namespace std;
//判断是否为素数
int prime(int n){
int i;
if(n<2)
return 0;
for(i = 2; i*i <= n; i++)
if(n%i == 0)
return 0;
return 1;
}
int main()
{
vector<int> a; //存储小于输入n的素数
int n, count = 0;
cin>>n;
for(int i = 2; i <= n; i++)
if(prime(i))
a.push_back(i);
int len = a.size();
for(int i = 0; i < len-1; i++)
if(a[i+1] - a[i] == 2) //判断相邻两素数之差是否为2
count++;
cout<<count;
return 0;
}