일반화된 쌍둥이 소수

시간 제한2초메모리 제한1024 MB

요약

n과 k가 주어질 때, q - p = k이고 q가 n 이하인 소수 쌍 (p, q)의 개수를 구합니다. 두 값 모두 10^4 이하라서 에라토스테네스의 체로 풀 수 있습니다.

난이도: 쉬움10점 중 2점
유형: 정수론, 수학
정답자: 아직 제출이 없습니다

문제

수론에서 $q - p = 2$ 를 만족하는 소수 쌍 $(p, q)$ 를 쌍둥이 소수 쌍이라고 한다. 예를 들어 $(3, 5)$ 와 $(11, 13)$ 은 쌍둥이 소수 쌍이다. 양의 정수 $k$ 에 대해 $q - p = k$ 를 만족하는 소수 쌍 $(p, q)$ 를 일반화된 쌍둥이 소수 쌍이라고 부른다. 예를 들어 $k = 4$ 일 때 $(3, 7)$ 은 일반화된 쌍둥이 소수 쌍이다.

쌍둥이 소수 쌍이 무한히 많다는 추측이 있지만 아직 증명되지 않았다. 주어진 $k$ 에 대해 모든 자연수 중 일반화된 쌍둥이 쌍의 개수를 구하는 문제는 쌍둥이 소수의 경우만큼 어렵다.

이 문제는 그보다 간단하다. 주어진 $k$ 에 대해 1부터 $n$ 까지의 자연수 중 일반화된 쌍둥이 쌍의 개수를 구하라.

입력

첫 줄에 공백으로 구분된 두 자연수 $n$ 과 $k$ 가 주어진다 ( $1 \le n, k \le 10^4$ ).

출력

$1 \le p < q \le n$ 이고 $q - p = k$ 를 만족하는 소수 쌍 $(p, q)$ 의 개수를 출력한다.

예제3

예제 1
입력
```
17 2
```
예상 출력
```
3
```
예제 2
입력
```
10000 1
```
예상 출력
```
1
```
예제 3
입력
```
20 7
```
예상 출력
```
0
```