Question

#2642 pbinfo
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.

Answer 1

#include<bits/stdc++.h>

inline int Phi(int n)

{

   register int nr=1,d=2,p;

   while(n>1)

   {

       p=0;

       while(n%d==0)

           ++p,n/=d;

       if(p)

           nr*=(d-1)*pow(d,p-1);

       ++d;

       if(n>1 && d*d>n)

           d=n;

   }

   return nr;

}