Hide

Problem B
Frumtölutalning

Languages en is

/problems/frumtolutalning/file/statement/en/img-0001.jpg

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

Problem BFrumtölutalning

Input

Output

Scoring

Problem B
Frumtölutalning