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.

#include <bits/stdc++.h>
bool prim(int n)
{
    int cnt=0;
    for(int i = 1 ; i * i <= n ; ++i)
        if(n % i == 0 && i * i != n)
            cnt+=2;
        else if(i * i == n)
            cnt++;
    if(cnt == 2)
        return 1;
    return 0;
}

int Phi(int n)
{
    if(prim(n))
        return n-1;
    int d=2;
    int rez = 1;
    while(n>1)
    {
        int p = 0;
        while(n % d==0)
            n/=d , p++;
        if(p != 0)
            rez = rez * (d-1) * pow(d , p - 1);
        d++;
        if(d * d > n)
            d = n;
    }
    return rez;
}