#809. [包河区 ] 素数对猜想 (prime)

[包河区 ] 素数对猜想 (prime)

题目描述

素数是指在大于 11 的自然数中,除了 11 和该数自身外,无法被其他自然数整除的数,即只有 11 与该数本身两个正因数的数。素数对猜想认为存在无穷多对相邻且差为 22 的素数,如 557717171919 等,给定一个数 nn,请编程找出不超过 nn 的满足猜想的素数对的个数。

输入格式

输入数据只有一行一个正整数 nn

输出格式

一个正整数 kk,表示素数对的个数。

样例

20
4

解释#1

小于 2020 的素数对共有 44 对,分别是 (3,5),(5,7),(11,13),(17,19)(3,5),(5,7),(11,13),(17,19)

数据范围

1n1000001≤≤n≤100000