Question

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.
Acesta este programul meu de 30p:
int cmmdc(int x,int y)
{
while(x!=y)
{
if(x>y)
x=x-y;
if(y>x)
y=y-x;
}
return x;
}
int Phi(int n)
{
int i,k,m;
k=1;
for(i=2;i<=n;i++)
{
m=n;
if(cmmdc(i,m)==1)
k++;
}
return k;
}

Answer 1

Răspuns:

#include<bits/stdc++.h>

///este exact alg. de descompunere in factori primi

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;

}

Explicație: