Fişierul intrare/ieşire:densitate.in, densitate.outSursăAlgoritmiada 2009, Runda 1
AutorStefan Alexandru FilipAdăugată deProstuStefan-Alexandru Filip Prostu
Timp execuţie pe test0.3 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Densitate

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

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 ai, bi 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
  • 1 ≤ a ≤ b ≤ N

Exemplu

densitate.indensitate.out
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

Explicatii

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content