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.

#include <bits/stdc++.h>
using namespace std;

ifstream cin("eratostene5.in");
ofstream cout("eratostene5.out");

int e[1000001], f[1000001], p[500001], P;

void eratostene(){
    e[0] = e[1] = 1;
    for(int i = 2; i * i <= 1000000; ++i)
        for(int j = i * i; j <= 1000000; j += i)
            e[j] = 1;
    for(int i = 1; i <= 1000000; ++i)
        if(!e[i])
            p[++P] = i;
}

void desc(int n){
    int d = 1;
    while(n > 1){
        int pi = 0;
        while(n % p[d] == 0)
            n/=p[d], pi++;
        f[p[d]] += pi;
        d++;
        if(n > 1 && p[d] * p[d] > n){
            f[n] ++;
            break;
        }
    }
}

int main(){
    int n;
    eratostene();
    cin >> n;
    for(int i = 1; i <= n; ++i){
        int x;
        cin >> x;
        desc(x);
    }
    for(int i = 1; i <= 1000000; ++i)
        if(f[i])
            cout << i << ' ' << f[i] << '\n';
    return 0;
}