densitate

Densitate

== include(page="template/taskheader" task_id="densitate") ==

Poveste şi cerinţă...

Oaia Dubota a invatat de la oaia profesoara de matematica despre numerele prime. Pe langa definitia numerelor prime (un numar prim se divide numai cu $1$ si cu el insusi), profesoara le-a spus si doua cuvinte despre 'teorema numerelor prime':http://en.wikipedia.org/wiki/Prime_number_theorem. Un rezultat al acestei teoreme este ca aproximativ unul din $13$ numere intre $1$ si $500000$ sunt prime. Lui Dubota nu ii vine sa creada ca sunt atat de multe numere prime si nici nu are inceredere in profesoara si a decis sa investigheze problema prin metode normale, folosind calculatorul (pentru ca nu stie matematica). Dubota este insa un programator incepator si va roaga sa il ajutati sa raspunda repede la $Q$ intrebari de tipul: Cate numere prime sunt intre $a$ si $b$, unde $a, b ≤ N$.

h2. Date de intrare

Fişierul de intrare $densitate.in$ ...

Fişierul de intrare $densitate.in$ va contine pe prima linie $N$ si $Q$. Pe urmatoarele $Q$ linii se afla cate 2 numere $a{~i~}$, $b{~i~}$ cu semnificatia din enunt.

h2. Date de ieşire

În fişierul de ieşire $densitate.out$ ...

În fişierul de ieşire $densitate.out$ se scrie $Q$ linii, pe care sunt afisate, in ordine, raspunsurile intrebarilor lui Dubota.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $N < 500000$
* $Q < 100000$
* $1 &le; a &le; b &le; N$

h2. Exemplu
table(example). |_. densitate.in |_. densitate.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|30 10
1 4
1 10
1 11
1 12
1 13
1 30
7 19
8 18
7 20
8 29
| 2
4
5
5
6
10
5
3
5
6

|

h3. Explicaţie

h3. Explicatii

...

Numerele prime intre $1$ si $30$ sunt: $2, 3, 5, 7, 11, 13, 17, 19, 23$ si $29$.

== include(page="template/taskfooter" task_id="densitate") ==

3481