# PBinfo #2642 – phi – Rezolvare C++

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

## Enunț

Cerința
Să se scrie funcția cu următorul antet:

int Phi(int n)
Funcția primește ca parametru un număr natural n și trebuie să returneze numărul de numere naturale nenule prime cu n și strict mai mici decât n.

Restricții și precizări

2 ≤ n ≤ 2.000.000.000
Numele funcției este Phi.
Spunem că un număr natural x este prim cu n dacă cmmdc(x, n) = 1.

Exemplu:
Phi(12) = 4, deoarece 12 este prim cu numerele 1, 5, 7, 11.

## Cod sursă C++

```cpp
int Phi(int n) {
    int rez;
    rez = n;
    for (int i = 2; i * i <= n && n != 1; ++i)
        if (n % i == 0) {
        	rez = rez / i * (i-1);
            while (n % i == 0)
                n = n /  i;
    } if (n != 1)
        rez = rez / n * (n - 1);
    return rez;
}
```

## Resurse

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