Generalized Twin Primes

Time limit2sMemory limit1024 MB

Summary

Given n and k, count the prime pairs (p, q) with q - p = k and q at most n. The bounds are at most 10^4, so a sieve suffices.

Level: Easy2 of 10
Topics: Number theory, Math
Solved: No attempts yet

Problem

In number theory, a pair of primes $(p, q)$ with $q - p = 2$ is called a twin prime pair. For example, $(3, 5)$ and $(11, 13)$ are twin prime pairs. A pair of primes $(p, q)$ with $q - p = k$ , where $k$ is a positive integer, is called a generalized twin prime pair. For example, for $k = 4$ , the pair $(3, 7)$ is a generalized twin prime pair.

It is conjectured that there are infinitely many twin prime pairs, but this has not been proven. Counting the generalized twin prime pairs among all natural numbers for a given $k$ is at least as hard as the same question for twin primes.

This problem is simpler. Given $k$ , count the generalized twin prime pairs among the natural numbers from 1 to $n$ .

Input

The first line contains two natural numbers $n$ and $k$ , separated by a space ( $1 \le n, k \le 10^4$ ).

Output

Print the number of pairs of primes $(p, q)$ such that $1 \le p < q \le n$ and $q - p = k$ .

Examples3

Example 1
Input
```
17 2
```
Expected output
```
3
```
Example 2
Input
```
10000 1
```
Expected output
```
1
```
Example 3
Input
```
20 7
```
Expected output
```
0
```