# PBinfo #3318 – Eratostene7 – Rezolvare C++

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

## Enunț

Cerința
Se dau n perechi de numere naturale, x şi k. Verificaţi pentru fiecare număr x dacă este produs de k numere prime distincte.

Date de intrare
Fișierul de intrare eratostene7.in conține pe prima linie numărul n, iar pe următoarele n linii câte o pereche de numere x şi k, separate prin spaţiu.

Date de ieșire
Fișierul de ieșire eratostene7.out va conține pe primele n linii cuvântul DA sau NU corespunzător celei de-a n-a perechi din fişierul de intrare.

Restricții și precizări

1 ≤ n ≤ 100.000
1 ≤ x ≤ 1.000.000
1 ≤ k ≤ 100

Exemplu:
eratostene7.in

3
20 3
30 3
49 2
eratostene7.out

NU
DA
NU
Explicație
Numărul 20 nu este produs de 3 numere prime distincte, 30=2•3•5 este produs de trei numere prime distincte, 49 nu este produs de 2 numere prime distincte.

## Cod sursă C++

```cpp
#include <fstream>
#define N 1000000
using namespace std;
ifstream f("eratostene7.in");
ofstream g("eratostene7.out");
int prod[N+1], p[N+1], fr[N+1];
int i, j, k, x, n;
int main()
{
    p[1] = 1;
    for(i = 1; i <= N; i++)
        prod[i] = 1;
    for(i = 2; i <= N; i++)
        if(p[i]==0){
            fr[i] = 1;
            prod[i] = i;
            j = i+i;
            while(j <= N){
                p[j] = 1;
                fr[j]++;
                prod[j] *= i;
                j = j + i;
            }
        }
    f >> n;
    for(i = 1; i <= n; i++){
        f >> x >> k;
        if(fr[x] != k) g << "NU\n";
        else if(prod[x]==x) g << "DA\n";
             else g << "NU\n";
    }
    return 0;
}
```

## Resurse

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