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

20

4

思路：可以先定义一个数组作用是记录从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);
}