# PBinfo #2325 – prim003 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

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.

## Cod sursă C++

```cpp
#include <iostream>
using namespace std;
int i,k,t,a,b,j,u,p[500011],pr[50000],v[1000001],c[1000001] ;
int main()
{
    p[1] = 1 ;
    p[2] = 0 ;
    k = 0 ;
    for ( i=2 ; i<=500010 ; i++ )
        if ( p[i]==0 )
        {
           k++ ;
           pr[k] = i ;
           j = i+i ;
           while( j<=500010 )
           {
               p[j] = 1 ;
               j = j+i ;
           }
        }
     for( i=1 ; i<=170 ; i++ )
     {
        j=i ;
        u=pr[i]*pr[j] ;
        while( u<=1000000)
        {
            v[u]=1 ;
            j++ ;
            u=pr[i]*pr[j] ;
        }
     };
     c[0]=0 ;
     v[2]=0 ;
     for( i=1 ; i<=1000000 ; i++ )
        if ( v[i]==1 )c[i] = c[i-1]+1 ;
        else c[i] = c[i-1] ;
     cin >> t ;
     for ( i=1 ; i<=t ; i++)
     {
         cin >> a >> b ;
         cout << c[b]-c[a-1] << " " ;
     }
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2325)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2325/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2325/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)