PAT 乙级 1007. 素数对猜想 (20) c++ 筛选法求素数

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

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

输入格式：每个测试输入包含1个测试用例，给出正整数N。

输出格式：每个测试用例的输出占一行，不超过N的满足猜想的素数对的个数。

输入样例：

20

输出样例：

4

思路分析： 首先这道题如果用普通的求素数的方法写可能会超时，毕竟10的五次方了 然后还要去循环判断每一个数，我也是在网上看了别人的代码才知道有筛选法求素数的。筛选法求素数的基本思想就是把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束。。 最根本的思想可以说是不难，但实现起来。。其实实现起来也不难。

代码实现：

#include<iostream>

using namespace std;

bool isprime [100001]; // bool数组标志1-100000的数据是否为素数

int count = 0,tmp =2;

void   getprime(int n){   //运用筛选法获得n以内的全部素数

    for(int i=2;i<=n;i++){  //初始化为true即默认都是素数

        isprime[i]=true;

    }

    for(int j=2;j<=n;j++){   //依次遍历后面的所有标志为true的数据

    if(isprime[j]==true){    //从第一个素数2开始判断 设置2的倍数（非素数）为false 因为素数的倍数肯定不是素数他至少有一个因子是该素数本身

        for(int m=2;j*m<=n;++m){//  m为倍数 j为素数 去掉j的m倍即为去掉非素数

            isprime[j*m]=false;

        }

    }

}

for(int k=2;k<=n;k++){

        if(isprime[k] == true){   //如果这个数据是素数

            if(k - tmp == 2){  //如果这个数减去上一个相邻的素数结果为2 即素数对数加1

                count ++;

                tmp = k;    //更新tmp为本次的素数

            }

            else{

                tmp = k;

            }

        }

    }

cout<<count;

}

int main(){

    int N;

    scanf("%d",&N);

    getprime(N);

    return 0;

}