Hide

Problem B
Frumtölutalning

Languages en is
/problems/frumtolutalning/file/statement/is/img-0001.jpg
Prime Numbers eftir geralt, Pixabay
Heiltala $p$ er frumtala ef hún er stærri en $1$ og það er aðeins hægt að deila henni með $1$ og $p$ án þess að fá afgang. Til dæmis er $10$ ekki frumtala þar sem það er hægt að deila henni með $1$, $2$, $5$ og $10$ án þess að fá afgang. Aftur á móti er $11$ frumtala þar sem það er bara hægt að deila henni með $1$ og $11$ án þess að fá afgang. Á sama hátt sjáum við að $2$, $3$ og $17$ eru frumtölur, en $4$, $9$ og $15$ eru ekki frumtölur.

Ef maður skoðar tölurnar á bilinu $1$ upp í $100$ þá getur maður séð að $25$ þeirra eru frumtölur. Með aðeins meiri handavinnu er hægt að komast að því að það eru hvorki meira né minna en $168$ frumtölur á bilinu $1$ upp í $1\, 000$.

Gefnar tvær heiltölur $a$ og $b$, reiknaðu hvað það eru margar frumtölur á bilinu $a$ upp í $b$.

Inntak

Inntak er ein lína með tveimur heiltölum $a$ og $b$ ($1 \leq a \leq b$).

Úttak

Skrifið út fjölda frumtala á bilinu $a$ upp í $b$.

Stigagjöf

Hópur

Stig

Takmarkanir

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