Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | densitate.in, densitate.out | Sursă | Algoritmiada 2009, Runda 1 |
| Autor | Stefan Alexandru Filip | Adăugată de |  Stefan-Alexandru Filip •Prostu |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Densitate
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.
Date de intrare
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.
Date de ieşire
În fişierul de ieşire densitate.out se scrie Q linii, pe care sunt afisate, in ordine, raspunsurile intrebarilor lui Dubota.
Restricţii
- N < 500000
- Q < 100000
- 0 < a ≤ b ≤ N
- ... ≤ ... ≤ ...
Exemplu
| densitate.in | densitate.out |
|---|---|
| 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 |
