PAT 1007 素数对猜想 (20分)

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

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

输入样例:
20
输出样例:
4

题意简化:
找素数对，若两个素数之和相差为2，则这两个数为一对素数对。

菜鸡版本：
思路：先将给定数以内的所有素数求出，分别放在数组中，再判断是否存在素数对。

#include <iostream>
using namespace std;
int main()
{
    int num;int k=1;cin>> num;int arr[10000];arr[0]=1;int flag = 1;for(int i=2;i<=num;i++){
    flag = 1;for(int j =2;j*j<=i;j++){
    if((i%j == 0)&& (i != j)){
    flag = 0;break;}}if(flag == 1){
    arr[k++] = i;}}int count=0;for(int i=1;i<k-1;i++){
    if(arr[i]+2 == arr[i+1])count++;}cout<<count<<"\n";
}

大神版本：
本题没叫求出素数，所以只需要写一个判断是否为素数的函数即可！

#include <iostream>
using namespace std;
bool IsPrime(int a)
{
    for(int i=2;i*i<=a;i++)if( a%i == 0) return false;return true;
}
int main()
{
    int n;cin >> n;int count=0;for(int i=5;i<=n;i++) //从5开始才有素数对if(IsPrime(i)&&IsPrime(i-2)) //要用减，不能用加，count++;cout<<count;return 0;
}