PTA-1007 素数对猜想 (20分)

1007 素数对猜想 (20分)

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

输入格式:

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

输出格式:

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

输入样例:

20

输出样例:

4

#include <bits/stdc++.h>
using namespace std;

int main()
{
          
   
    int inum;
    while (cin >> inum)
    {
          
   
        int isize = 0;
        int ilist_su[inum];
        for (int i = 2; i <= inum; i++) //将所有的素数计算出来，只需要计算到sqrt（n）
        {
          
   
            int flag = 0;
            for (int j = 2; j <= sqrt(i); j++)
            {
          
   
                if (i % j == 0)
                {
          
   
                    flag = 1;
                    break;
                }
            }
            if (!flag)
            {
          
   
                ilist_su[isize++] = i; //素数数量
            }
        }
        int ifirst = ilist_su[0];
        int icnt = 0;
        for (int i = 1; i < isize; i++)
        {
          
   
            if ((ilist_su[i] - ifirst) == 2) //计算差值，差值为2则cnt+1
            {
          
   
                icnt++;
                ifirst = ilist_su[i];
            }
            ifirst = ilist_su[i];
        }
        cout << icnt << endl;
    }
}