/*

1007. 素数对猜想 (20)

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

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

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

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

输入样例：

20

输出样例：

4

*/

/*

    思路：

        1.输入正整数n；

        2.创建素数标记整型数组prime_array[n+1]，同时初始化元素为0;

        3.从2，即prime_array[2]开始，依次(+1)遍历数组prime_array的元素到n，判断每一个元素是否为素数，若当前元素为素数，标记prime_array[i]为1；

        4.判断prime_array[i-2]是否被标记为素数，若是则统计之，反之，执行下一位。

    复杂度：

        O(n^2);

*/

#include<stdio.h>

#include<math.h>

bool isPrime(int n){

    int k;

    k = sqrt(n);

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

        if(n%j==0)

            return false;

    }

    return true;

}

int main(){

    int n,prime_count = 0;

    int *prime_array;//带有记忆功能的标记数组。

    scanf("%d", &n);

    prime_array = new int [n+1];

    if(n>1){

        prime_array[0]=0;

        prime_array[1]=0;

    }

    for(int i=2;i<=n;i++){//注意：等于符号，细节！

        prime_array[i]=0;//初始化素数标记元素

        if(isPrime(i) == true){

            prime_array[i] = 1;

            if(prime_array[i-2] == 1)

                prime_count++;

        }

    }

    //test

//    for(int i=0;i<n;i++){

//        printf("%d ", prime_array[i]);

//    }

//    printf("\n");

    printf("%d", prime_count);

}