Problem A
Frumtölutalning
Languages
en
is
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 |