# PBinfo #4343 – prietene1 – Rezolvare C++

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

## Enunț

Numerele naturale nenule x și y se numesc prietene dacă au același număr de divizori primi.

Cerința
Fiind date două șiruri de numere naturale, primul cu n numere, iar al doilea cu m numere, scrieți un program care rezolvă următoarele cerințe:
1) Determină cel mai mare dintre cele n + m numere date ce are număr maxim de divizori primi.
2) Determină câte perechi de numere prietene de forma (x, y) se pot forma, x fiind din primul șir, iar y din al doilea șir.

Date de intrare
Fișierul de intrare prietene.in conţine pe prima linie numărul C reprezentând cerința (1 sau 2), pe a doua linie numerele n și m, pe a treia linie un șir de n numere, iar pe a patra linie un șir de m numere, numerele de pe fiecare linie fiind separate prin câte un spațiu.

Date de ieșire
Dacă C = 1, atunci pe prima linie a fişierului de ieşire prietene.out se va scrie numărul ce reprezintă răspunsul la cerința 1.
Dacă C = 2, atunci pe prima linie a fişierului de ieşire prietene.out se va scrie numărul ce reprezintă răspunsul la cerința 2.

Restricții și precizări

1 ≤ n,m ≤ 10.000
Cele două șiruri conțin numere naturale din intervalul [2, 1.000.000.000].
Pentru 30% din teste cerinţa va fi C = 1.
10 puncte se acordă pentru exemplele din enunț.

Exemplul 1:
prietene.in

1
3 4
36 30 5
12 60 13 77
prietene.out

60
Explicație
Pentru fiecare număr din șirurile date scriem numărul de divizori primi: 36 → 2, 30 → 3, 5 → 1, 12 → 2, 60 → 3, 13 → 1, 77 → 2. Numărul maxim de divizori primi este 3. Cel mai mare număr din șirurile date care are 3 divizori primi este 60.

Exemplul 2:
prietene.in

2
4 5
36 30 5 10
12 60 15 77 105
prietene.out

8
Explicație
Sunt 8 perechi de numere prietene: (36, 12), (36, 15), (36, 77), (10, 12), (10, 15), (10, 77), (30, 60), (30, 105).

## Cod sursă C++

```cpp
#include <bits/stdtr1c++.h>
#define NM 31624
using namespace std;
ifstream fin("prietene.in");
ofstream fout("prietene.out");
int nrp;
int p[3500],fr1[13],fr2[13];
bool c[NM];
void ciur()
{
    int i,j;
    c[0] = c[1] = 1;
    for(i = 2; i * i <NM; i++)
        if(c[i]==0)
            for(int j = i * i; j <NM; j += i)
                c[j] = 1;
    nrp=0;
    for(i = 1; i <NM; ++i)
        if(c[i]==0)
        {
            nrp++;
            p[nrp] = i;
        }
}
int nr_factori_primi(long long x)
{
    int i = 1,nr=0,e;
    while(i<=nrp && p[i]*p[i]<=x)
    {
        e = 0;
        while(x % p[i] == 0)
        {
            x=x/p[i];
            e++;
        }
        if(e>0)
            nr++;
        i++;
    }
    if(x > 1)
        nr++;
    return nr;
}
int main()
{
    int n,m,i,nr,y,cer,nrm;
    long long x,rez,xm;
    ciur();
    nrm=0;
    fin>>cer>>n>>m;
    for(i=1; i<=n; i++)
    {
        fin>>x;
        nr=nr_factori_primi(x);
        fr1[nr]++;
        if(nr>nrm || nr==nrm && x>xm)
        {
            nrm=nr;
            xm=x;
        }
    }
    for(i=1; i<=m; i++)
    {
        fin>>x;
        nr=nr_factori_primi(x);
        fr2[nr]++;
        if(nr>nrm || nr==nrm && x>xm)
        {
            nrm=nr;
            xm=x;
        }
    }
    if(cer==1)
        fout<<xm<<'\n';
    else
    {
        rez=0;
        for(i=1; i<=12; i++)
            rez=rez+fr1[i]*fr2[i];
        fout<<rez<<'\n';
    }
    return 0;
}
```

## Resurse

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