Counting Primes in a Range

Interview

Time limit1sMemory limit256 MB

Summary

Count the primes between m and n inclusive for each blank-line separated test case.

Level: Easy3 of 10
Topics: Number theory, Prefix sum
Solved: No attempts yet

Problem

You are given two integers $m$ and $n$ with $2 \le m < n \le 10\,000\,000$ .

Consider the following set.

$\mathrm{Prime}(m, n) = \{\, p \mid p \in \mathbb{P},\ m \le p \le n \,\}$

Here $\mathbb{P}$ is the set of all primes, so $\mathrm{Prime}(m, n)$ collects every prime that is at least $m$ and at most $n$ .

Compute the number of elements of $\mathrm{Prime}(m, n)$ .

Input

The input consists of several tests. Each test occupies one line and holds $m$ and $n$ separated by exactly one space. An empty line separates any two consecutive tests.

Output

For each test, print the number of elements of $\mathrm{Prime}(m, n)$ on its own line, in the same order as the input. Print an empty line between any two consecutive results.

Examples4

Example 1
Input
```
2 3
```
Expected output
```
2
```
Example 2
Input
```
114 126
```
Expected output
```
0
```
Example 3
Input
```
8 9

7 11

999983 1000003
```
Expected output
```
0

2

2
```
Example 4
Input
```
4 4999
```
Expected output
```
667
```