densitate

Densitate

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

Poveste şi cerinţă...

Oaia Dubota a invatat de la oaia profesoara despre numerele prime. Profesoara a mai mentionat si ca densitatea numerelor prime este ridicata, aproximativ 1 / ln(N), unde densitatea se masoara intre 1 si N. Asta inseamna ca aproximativ unul din 13 numere sunt prime intre 1 si 500000. Lui Dubota nu ii vine sa creada ca sunt atat de multe numere prime si s-a decis sa investigheze problema. El va roaga sa il ajutati sa raspunda 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$
* $0 < 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.

|31 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
 
...
 

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