Pracsiu Dan (dnprx) Pentru un număr natural N considerăm șirul: 0, 1, 2, …, N.
Cerințe
1) Se dau Q perechi de numere naturale de forma (a,b). Pentru fiecare pereche se cere să se determine numărul de numere prime care află în secvența de numere consecutive: a, a+1, a+2, ..., b.
2) Se dau Q numere naturale p1, p2, …, pQ. Pentru fiecare număr pi se cere să se determine numărul secvențelor a, a+1, a+2, ..., b din șirul 0, 1, ..., N care conțin câte pi numere prime (1 ≤ i ≤ Q).
Date de intrare
Fișierul de intrare prime.in conține pe prima linie trei numere naturale C N Q, separate prin câte un spațiu, unde C este cerința care trebuie rezolvată (1 sau 2), N și Q au semnificația de mai sus. Dacă C=1, atunci pe fiecare dintre următoarele Q linii se află câte două numere naturale a b, separate prin spațiu, reprezentând extremitățile unei secvențe de numere naturale consecutive. Dacă C=2, atunci pe următoarele Q linii se află câte un număr natural pi (1 ≤ i ≤ Q), cu semnificația din enunț.
Date de ieșire
Fișierul de ieșire prime.out conține Q numere, fiecare pe câte un rând, în conformitate cu cerința C.
Restricții și precizări
C ∈ {1, 2}1 ≤ N, Q ≤ 50.0000 ≤ a ≤ b ≤ N0 ≤ pi≤ N,1 ≤ i ≤ Q- Pentru 40 de puncte,
C = 1,1 ≤ N, Q ≤ 10.000 - Pentru 10 puncte,
C = 1,10.000 < N, Q ≤ 50.000 - Pentru 30 de puncte,
C = 2,1 ≤ N, Q ≤ 10.000 - Pentru 20 de puncte,
C = 2,10.000 < N, Q ≤ 50.000
Exemplul 1:
prime.in
1 10 3 0 10 3 3 8 10
prime.out
4 1 0
Explicație
C=1, N=10, Q=3. Se rezolvă cerința 1. În secvența 0…10 există 4 numere prime: 2, 3, 5, 7. În secvența 3…3 există un singur număr prim, numărul 3. În secvența 8…10 nu există numere prime.
Exemplul 2:
prime.in
2 10 2 4 1
prime.out
12 17
Explicație
C=2, N=10, Q=2. Se rezolvă cerința 2. Există câte 4 numere prime în fiecare dintre următoarele 12 secvențe: 0…10, 1…10, 2…10, 0…9, 1…9, 2…9, 0…8, 1…8, 2…8, 0…7, 1…7, 2…7. Există câte un singur număr prim în fiecare dintre următoarele 17 secvențe: 0…2, 1…2, 2…2, 3…3, 3…4, 4…5, 5…5, 4…6, 5…6, 6…7, 6…8, 6…9, 6…10, 7…7, 7…8, 7…9, 7…10.