Hide

Problem A
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 AFrumtölutalning

Input

Output

Scoring

Problem A
Frumtölutalning