让我们定义dn为：dn=pn+1−pn，其中pi是第i个素数。显然有d1=1，且对于n>1有dn是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。
现给定任意正整数N(<105)，请计算不超过N的满足猜想的素数对的个数。
输入格式:
输入在一行给出正整数N。
输出格式:
在一行中输出不超过N的满足猜想的素数对的个数。
输入样例:
20
结尾无空行
输出样例:
4
结尾无空行
N = 100010
primes = [0] * N
cnt = 0
st = [0] * N
# 质数的倍数肯定不是质数，每一次都拿质数的倍数去筛掉合数, 存在一个合数被其本身多个质因子重复筛
def get_Primes_1():
global cnt
for i in range(2, N):
if not st[i]:
primes[cnt] = i
cnt += 1
for j in range(i + i, N, i):
st[j] = True
#每一次都拿最小的质因子去筛掉合数，保证了每一个合数都只会被筛一次
def get_Primes_2():
global cnt
for i in range(2, N):
if not st[i]:
primes[cnt] = i
cnt += 1
j = 0
while i * primes[j] < N:
# 最小质因子primes[j]去筛掉合数
st[i * primes[j]] = True
# 不是最小质因子，防止被多次筛，直接退出
if i % primes[j] == 0:
break
j += 1
get_Primes_2()
n = int(input())
res = 0
for i in range(1, cnt):
if primes[i] > n:
break
if primes[i] - primes[i - 1] == 2:
res += 1
print(res)
