# PBinfo #3316 – Eratostene5 – Rezolvare C++

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

## Enunț

Cerința
Se dau n numere naturale nenule şi se notează cu P produsul acestora. Să se afle numerele prime din descompunerea lui P în factori primi, precum şi exponentul acestora.

Date de intrare
Fișierul de intrare eratostene5.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire
Fișierul de ieșire eratostene5.out va conține pe fiecare linie un număr prim din descompunerea lui P şi exponentul acestuia. Factorii primi se vor afişa în ordine crescătoare.

Restricții și precizări

1 ≤ n ≤ 500.000
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000

Exemplu:
eratostene5.in

4
6 10 21 56
eratostene5.out

2 5
3 2
5 1
7 2
Explicație
Numărul P este 6•10•21•56=25•32•51•72.

## Cod sursă C++

```cpp
#include <fstream>
#define N 1000000
using namespace std;
ifstream fi("eratostene5.in");
ofstream fo("eratostene5.out");
int i, j, n, x, k;
int p[N+1], a[N+1][8], e[N];
int main()
{
    //ciurul lui eratostene + numararea si memorarea factorilor primi din descompunere
    p[1] = 1;
    a[1][0] = 0;
    for(i = 2; i <= N; i++)
        if(p[i]==0)
    {
        a[i][0] = 1;
        a[i][1] = i;
        j = i+i;
        while(j <= N)
        {
            p[j] = 1;
            a[j][0]++;
            a[j][a[j][0]] = i;
            j = j + i;
        }
    }
    //prelucrare sir
    fi >> n;
    for(i = 1; i <= n; i++)
    {
        fi >> j;
        x = j;
        for(k = 1; k <= a[j][0]; k++)
            while(x % a[j][k] == 0)
            {
                e[a[j][k]]++;
                x = x / a[j][k];
            }
    }
    for(i = 2; i < N; i++)
        if(e[i] > 0) fo << i << " " << e[i] << "\n";
    return 0;
}
```

## Resurse

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