Moisil++ 2023 Clasa a 6a Mirror | Sprime

Cerință

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

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

De exemplu $5$ este special, deoarece $5=2+3$, iar $2$, $3$ și $5$ sunt numere prime.

Se dau două numere $n$ și $q$, iar apoi $q$ interogări de tipul:

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

Date de intrare

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

Pe fiecare din următoarele $q$ linii se vor afla câte două numere $l$ și $r$ - capetele interogrărilor.

Date de ieșire

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

Restricții și precizări

• $1 \le n \le 5 \cdot 10^6$;
• $1 \le q \le 2 \cdot 10^5$;
• $1 \le l \le r \le n$;
• Un număr $x$ este prim dacă are exact doi divizori, $1$ și $x$. Prin urmare, $0$ și $1$ nu sunt numere prime.
• Pentru $10$ puncte, $n,q \le 50$;
• Pentru încă $10$ puncte, $n,q \le 500$;
• Pentru încă $15$ puncte, $n,q \le 5 \ 000$;
• Pentru încă $10$ puncte, $n \le 5 \ 000$;
• Pentru încă $10$ puncte, $n,q \le 10^5$, iar la toate interogările avem $l=r$;
• Pentru încă $10$ puncte, la toate interogările avem $l=r$;
• Pentru încă $20$ de puncte, $n,q \le 10^5$;
• Pentru restul de $15$ 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 $1$ la $10$ sunt $5=2+3$ și $7=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 $500$.