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 8 numere: 10,14,15,21,22,25,26. În intervalul [88,100] sunt 4 numere: 91,93,94,95.

#include <bits/stdc++.h>
using namespace std;
int n , a , b , p[1000000] , E[1000000] , s[1000000] , rez[1000000];
int main()
{
    p[0] = p[1] = 1;
    for(int i = 2 ; i <= 500000 ; ++i)
        for(int j = 2 ; i*j <= 1000000 ; ++j)
            p[i*j]=1;
    for(int i = 2 ; i <= 500000 ; ++i)
        for(int j = 2 ; i*j <= 1000000 ; ++j)
            if(p[i]==0 && p[j]==0)
                E[i*j]=1;
    for(int i = 1 ; i <= 1000000 ; ++i)
    {
        s[i] = s[i-1];
        if(E[i] == 1) s[i]++;
    }
    cin >> n;
    for(int i = 1; i <= n ; ++i)
    {
        cin >> a >> b;
        if(E[a] == 1) rez[i] = s[b]-s[a]+1;
        else rez[i] = s[b]-s[a];
    }
    for(int i = 1 ; i <= n ;i++)
        cout << rez[i] << " ";
    return 0;
}