# Problem L

Frumtölutalning

Languages
en
is
*prime number*if it is larger than $1$ and its only positive divisors are $1$ and $p$. For example, $10$ is not a prime because its positive divisors are $1$, $2$, $5$, and $10$. However, $11$ is a prime because its only positive divisors are $1$ and $11$. In the same vein you can see that $2$, $3$, and $17$ are primes, but $4$, $9$, and $15$ are not prime.

Counting all the primes between $1$ and $100$ shows that there are $25$ prime numbers smaller than $100$. With a little more work one can show that there are $168$ prime numbers smaller than $1\, 000$.

Given two integers, $a$ and $b$, count the number of primes smaller than or equal to $b$ and larger than or equal to $a$.

## Input

The input consists of two integers, $a$ and $b$ ($1 \leq a \leq b$).

## Output

The output should contain the number of primes in the range $a$ to $b$.

## Scoring

Group |
Points |
Constraints |

1 |
19 |
$b \leq 10^3$ |

2 |
23 |
$b \leq 10^9$, $b-a \leq 10^3$ |

3 |
14 |
$b \leq 10^{18}$, $b-a \leq 10^5$ |

4 |
13 |
$b \leq 10^7$ |

5 |
16 |
$b \leq 10^{15}$, $b-a \leq 10^7$ |

6 |
15 |
$b \leq 10^{11}$ |

Sample Input 1 | Sample Output 1 |
---|---|

1 100 |
25 |

Sample Input 2 | Sample Output 2 |
---|---|

3 5 |
2 |

Sample Input 3 | Sample Output 3 |
---|---|

42 1337 |
204 |