自测-2 素数对猜想（20 分）

清疚 2022-05-21 07:43 177阅读 0赞

让我们定义*d**n*为：*d**n*=*p**n*\+1−*p**n*，其中*p**i*是第*i*个素数。显然有*d*1=1，且对于*n*>1有*d**n*是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。

现给定任意正整数`N`(<105)，请计算不超过`N`的满足猜想的素数对的个数。

### 输入格式: ###

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

### 输出格式: ###

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

### 输入样例: ###

### 输出样例： ###

思路：可以先定义一个数组作用是记录从1到n的所有素数，然后再看a\[i+1\]-a\[i\]的值是不是满条件即可。但需要注意的是n最大为100000，所以要选取适合的判断一个数是不是素数的方法：

1、首先我们知道1不是素数可以不用考虑，2是素数也先不管，所以这样来判断一个数n是不是素数：

for(i=2;i<n;i++)
    {
        if(n%i==0)
        {
            printf("这不是一个素数")；
            break;
        }
    }

2、通过一个数的sqrt（n）来判断，即：

for(j=2; j<=sqrt(n); j++)
            {
    
                if(i%j==0)
                {
    
                    printf("这不是一个素数")；
                    break;
                }
    
            }

很显然第二种判别方法是最快的，而选用第一种方法的时候就会tle了。

AC代码如下：

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int n,i,j,flag,k,sum=0,w=0;
        int a[112345];
        a[0]=2;
        scanf("%d",&n);
        for(i=3; i<=n; i++)
        {
            flag=1;
            k=sqrt(i);
            for(j=2; j<=k; j++)
            {
    
                if(i%j==0)
                {
    
                    flag=0;
                    break;
                }
    
            }
            if(flag)
            {
                a[++w]=i;
            }
    
        }
        for(i=0; i<=w; i++)
        {
            if(a[i+1]-a[i]==2)
            {
                sum++;
            }
        }
        printf("%d",sum);
    }