Time limit: 0.5s
Memory limit: 256MB
Input: sprime.in
Output: sprime.out
Cerință
Un număr este special dacă respectă simultan următoarele condiții:
- este prim.
- Există două numere prime și astfel încât .
De exemplu este special, deoarece , iar , și sunt numere prime.
Se dau două numere și , iar apoi interogări de tipul:
l r
(): Câte numere speciale există astfel încât ?
Date de intrare
Pe prima linie a fișierului de intrare sprime.in
se vor afla două numere naturale și - valoarea maximă posibilă a numerelor, respectiv numărul de interogări.
Pe fiecare din următoarele linii se vor afla câte două numere și - capetele interogrărilor.
Date de ieșire
Fișierul de ieșire sprime.out
va conține numere, răspunsurile la cele interogări.
Restricții și precizări
- ;
- ;
- ;
- Un număr este prim dacă are exact doi divizori, și . Prin urmare, și nu sunt numere prime.
- Pentru puncte, ;
- Pentru încă puncte, ;
- Pentru încă puncte, ;
- Pentru încă puncte, ;
- Pentru încă puncte, , iar la toate interogările avem ;
- Pentru încă puncte, la toate interogările avem ;
- Pentru încă de puncte, ;
- Pentru restul de puncte, nu se impun restricții suplimentare.
Exemplul 1
sprime.in
10 5
5 5
7 7
1 10
1 4
6 10
sprime.out
1
1
2
0
1
Explicație
Singurele numere speciale de la la sunt și .
Exemplul 2
sprime.in
500 1
1 500
sprime.out
24
Explicație
Sunt 24 de numere speciale mai mici sau egale cu .