Hide

Problem L
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

Please log in to submit a solution to this problem

Log in