PAT乙級1007

時間限制

400 ms

記憶體限制

65536 kB

代碼長度限制

8000 B

判題程式

Standard

作者

CHEN, Yue

讓我們定義 dn 為：dn = pn+1 - pn，其中 pi 是第i個素數。顯然有 d1=1 且對于n>1有 dn 是偶數。“素數對猜想”認為“存在無窮多對相鄰且差為2的素數”。

現給定任意正整數N (< 105)，請計算不超過N的滿足猜想的素數對的個數。

輸入格式：每個測試輸入包含1個測試用例，給出正整數N。

#include<cstdio>
#include<cmath>
bool isPrime(int n)
{
    if (n < 2)return false;
    int sq = sqrt(n);
    for (int i = 2; i <= sq; i++)
        if (n%i == 0)return false;
    return true;
}
int main()
{
    int N;
    scanf("%d", &N);
    int count=0;
    for (int i = 2; i <= N-2; i++)
    {
        if (isPrime(i) && isPrime(i + 2))count++;
    }
    printf("%d\n", count);
    return 0;
}