Rezolvare PBinfo #2325

Cerința

Anul 2017 tocmai s-a încheiat, suntem trişti deoarece era număr prim, însă avem şi o veste bună, anul 2018 este produs de două numere prime, 2 şi 1009. Dorel, un adevărat colecţionar de numere prime, şi-a pus întrebarea: “Câte numere dintr-un interval [a,b] se pot scrie ca produs de două numere prime? “.

Date de intrare

Programul citește de la tastatură numărul natural t, iar apoi t perechi de numere naturale a,b cu a≤b, separate prin spații.

Date de ieșire

Programul va afișa pe ecran, pentru fiecare pereche a,b, numărul numerelor din intervalul [a,b] care se pot scrie ca produs de două numere prime.

Restricții și precizări

• 1 ≤ t ≤ 100.000
• 1 ≤ a ≤ b ≤ 1.000.000

Exemplu:

Intrare

3
1 7
10 30
88 100

Ieșire

2 7 4

Explicație

În intervalul [1,7] sunt 2 numere ce se pot scrie ca produs de două numere prime: 4 şi 6. În intervalul [10,30] sunt 7 numere: 10,14,15,21,22,25,26. În intervalul [88,100] sunt 4 numere: 91,93,94,95.