Sprime

Time limit: 0.5s Memory limit: 256MB Input: sprime.in Output: sprime.out

Cerință

Un număr xx este special dacă respectă simultan următoarele condiții:

  • xx este prim.
  • Există două numere prime yy și zz astfel încât x=y+zx=y+z.

De exemplu 55 este special, deoarece 5=2+35=2+3, iar 22, 33 și 55 sunt numere prime.

Se dau două numere nn și qq, iar apoi qq interogări de tipul:

  • l r (1lrn1 \le l \le r \le n): Câte numere speciale xx există astfel încât lxrl \le x \le r?

Date de intrare

Pe prima linie a fișierului de intrare sprime.in se vor afla două numere naturale nn și qq - valoarea maximă posibilă a numerelor, respectiv numărul de interogări.

Pe fiecare din următoarele qq linii se vor afla câte două numere ll și rr - capetele interogrărilor.

Date de ieșire

Fișierul de ieșire sprime.out va conține qq numere, răspunsurile la cele qq interogări.

Restricții și precizări

  • 1n51061 \le n \le 5 \cdot 10^6;
  • 1q21051 \le q \le 2 \cdot 10^5;
  • 1lrn1 \le l \le r \le n;
  • Un număr xx este prim dacă are exact doi divizori, 11 și xx. Prin urmare, 00 și 11 nu sunt numere prime.
  • Pentru 1010 puncte, n,q50n,q \le 50;
  • Pentru încă 1010 puncte, n,q500n,q \le 500;
  • Pentru încă 1515 puncte, n,q5 000n,q \le 5 \ 000;
  • Pentru încă 1010 puncte, n5 000n \le 5 \ 000;
  • Pentru încă 1010 puncte, n,q105n,q \le 10^5, iar la toate interogările avem l=rl=r;
  • Pentru încă 1010 puncte, la toate interogările avem l=rl=r;
  • Pentru încă 2020 de puncte, n,q105n,q \le 10^5;
  • Pentru restul de 1515 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 11 la 1010 sunt 5=2+35=2+3 și 7=2+57=2+5.

Exemplul 2

sprime.in

500 1
1 500

sprime.out

24

Explicație

Sunt 24 de numere speciale mai mici sau egale cu 500500.

Log in or sign up to be able to send submissions!