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

Problem BFrumtölutalning

Inntak

Úttak

Stigagjöf

Problem B
Frumtölutalning