問(wèn)題描述：
讓我們定義d?n 為：dn =pn+1?pn傻唾，其中pi 是第i個(gè)素?cái)?shù)只酥。顯然有d1=1切揭，且對(duì)于n>1有dn是偶數(shù)哩罪∈诎裕“素?cái)?shù)對(duì)猜想”認(rèn)為“存在無(wú)窮多對(duì)相鄰且差為2的素?cái)?shù)”。

現(xiàn)給定任意正整數(shù)N(<10^5 )际插，請(qǐng)計(jì)算不超過(guò)N的滿足猜想的素?cái)?shù)對(duì)的個(gè)數(shù)碘耳。

輸入格式:
輸入在一行給出正整數(shù)N。

輸出格式:
在一行中輸出不超過(guò)N的滿足猜想的素?cái)?shù)對(duì)的個(gè)數(shù)框弛。

輸入樣例:
20
輸出樣例:
4

思路1：
1.求出給定正整數(shù)的所有素?cái)?shù)并存進(jìn)數(shù)組中
2.對(duì)滿足dn = pn+1 - pn 的dn計(jì)數(shù)

這題本來(lái)很簡(jiǎn)單的辛辨，但是時(shí)間限制是兩秒鐘，根據(jù)上面的思路讓我想了好多種方法,但還是超時(shí)錯(cuò)誤。
如下所示：

//求解素?cái)?shù)
    for (int i = 2 ; i <= number ; i++ )
    {
        int j = 2;
        while (j < i && i % j != 0) //沒(méi)有公共質(zhì)因子
        {
            j++;
        }
        if (i == j)                 
        {
            vec.push_back(i);
            if (vec.size() > 1)
            {
                if ((vec[1] - vec.front()) == 2)
                {
                    count++;
                }
                vec[0] = vec[1];
                vec.pop_back();
            }
            
        }
    }

思路二：從5到給定正整數(shù)的范圍區(qū)間[5,正整數(shù)]斗搞，判斷第i個(gè)正整數(shù)和第i+2個(gè)正整數(shù)是否為素?cái)?shù)绞蹦，并且差為2。但還是有一個(gè)測(cè)試time limited.

#include <iostream>

int main()
{
    int number;
    std::cin >> number;
    int count = 0;
    int prim = 3;
    for (int i = 5; i <= number; i += 2)
    {
        int j;
        for ( j = 2; j < i; j++)
        {
            if (i % j == 0)
            {
                break;
            }
        }
        if (j == i)
        {
            if ((i - prim) == 2)
            {
                count++;
            }
            prim = i;
        }
    }
    std::cout << count << std::endl;

    return 0;
}

然后呢想到下面那個(gè)：使用bool數(shù)組記錄已經(jīng)驗(yàn)證過(guò)的不是素?cái)?shù)的正整數(shù)榜旦。

#include <cstdio>

int main()
{
    const int maxN = 100000;
    bool p[maxN] = { 0 };
    //n為待驗(yàn)證的正整數(shù)幽七，primer為上一個(gè)素?cái)?shù)，k為素?cái)?shù)對(duì)計(jì)數(shù)
    int n, primer = 0, k = 0;

    scanf("%d", &n);
    for (int i = 2; i <= n; ++i)
    {
        //還沒(méi)驗(yàn)證是否為素?cái)?shù)的正整數(shù)才驗(yàn)證
        if (!p[i])
        {
            for (int j = i + i; j < n; j += i)
            {  
                p[j] = true;    //已經(jīng)確定不是素?cái)?shù)的正整數(shù)
            }
            if (primer != 0 && i - primer == 2)
            {
                ++k;
            }
            primer = i;
        }
    }

    printf("%d\n", k);
    
    return 0;
}