1007 素数对猜想 (20 分)

1007 素数对猜想 (20 分)

让我们定义dn为：dn=p n+1−p n，其中p i是第i个素数。显然有d 1 =1，且对于n>1有d n是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。
现给定任意正整数N(<10 5)，请计算不超过N的满足猜想的素数对的个数。

输入格式:

输入在一行给出正整数N。

输出格式:

在一行中输出不超过N的满足猜想的素数对的个数。

输入样例:

20

输出样例:

4

思路：写一个素数判断函数，找出所用小于n的素数，统计有几对相邻的素数的差为2

代码：

#include
#include
#include
#include
#include
using namespace std;
int maxn = 100005;
int judge(int k){//素数判断函数
    for(int i = 2 ; i <= sqrt(k) ; i++)
        if(k % i == 0)
            return 0;
    return 1;
}
int main(){
    int t[maxn];
    int n , count1 = 0 , temp = 0;
    cin>>n;
    for(int i = 2 ; i <= n ; i++)//统计小于n的有多少素数
        if(judge(i))
           t[count1++] = i;
    for(int i = 0 ; i < count1 ; i++)//统计有几对相邻素数差为2
        if(t[i+1] - t[i] == 2)
           temp++;
    cout<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5703060.html