👤
a fost răspuns

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

Răspuns :

#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;

}


Vă mulțumim pentru vizita pe site-ul nostru dedicat Informatică. Sperăm că informațiile prezentate v-au fost utile. Dacă aveți întrebări suplimentare sau nevoie de ajutor, vă rugăm să ne contactați cu încredere. Așteptăm cu drag să reveniți și nu uitați să ne salvați în lista dumneavoastră de favorite!


En Studentsy: Alte intrebari