Hide

# Problem BFrumtölutalning

Prime Numbers by geralt, Pixabay
An integer $p$ is a 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$ primes 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 smaller than $b$ and larger than $a$.

## 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