Funcția Euler phi prin factori primi în C++

Funcția Euler φ(n) numără întregii din intervalul 1..n care sunt coprimi cu n. Două numere sunt coprime atunci când cel mai mare divizor comun al lor este 1. Pentru n=1 adoptăm convenția φ(1)=1.

Cerință și convenții

Citim 1≤n≤10^9 și afișăm φ(n). Nu afișăm lista numerelor coprime. Păstrăm n separat de restul pe care îl descompunem, deoarece rezultatul pornește de la numărul inițial.

Exemplu explicat

Pentru 12, factorii primi distincți sunt 2 și 3. Pornim cu 12, eliminăm jumătate și rămân 6 candidați; apoi eliminăm o treime din cei rămași și obținem 4. Numerele coprime sunt 1, 5, 7 și 11.

Pentru 12, factorii primi distincți sunt 2 și 3.Mărește schema ↗

Cum construim rezultatul

Pentru fiecare factor prim p aplicăm rezultat -= rezultat/p. Împărțirea este exactă în această formulă. Eliminăm apoi toate aparițiile lui p din rest; factorul 2 din 12 trebuie folosit o singură dată, chiar dacă apare la puterea a doua. După încercările până la radical, un rest mai mare decât 1 reprezintă încă un factor prim distinct.

Program complet C++17

#include <iostream>

using namespace std;
int main() {
    long long n;
    cin>>n;
    long long r=n,ans=n;
    for(long long p=2;p<=r/p;++p)if(r%p==0) {
        ans-=ans/p;
        while(r%p==0)r/=p;
    }
    if(r>1)ans-=ans/r;
    cout<<ans<<'\n';
}

De ce funcționează și cât costă

Formula φ(n)=n·∏(1−1/p) decurge din eliminarea multiplilor fiecărui factor prim; includerea și excluderea intersecțiilor produce acest produs. Procesarea unui factor actualizează exact proporția de candidați acceptați. Bucla de factorizare are timp O(√n), iar memoria auxiliară este O(1). Condiția p≤rest/p evită un pătrat intermediar inutil.

Greșeala de evitat

Nu scădea n/p din rezultatul curent pentru fiecare factor: termenul folosește rezultatul deja actualizat. Pentru 12, expresia greșită 12−6−4 dă 2, nu 4. Nici numărul 1 nu trebuie exclus automat: el este coprim cu orice număr pozitiv.

Exersează

Calculează φ(9), φ(13) și φ(1). Răspunsurile sunt 6, 12 și 1. Pentru 9, scrie numerele 1,2,4,5,7,8 și observă că excluderea multiplilor lui 3 este suficientă. Pentru un prim p, toate valorile 1..p−1 sunt acceptate.

Reia divizibilitatea, descompunerea în factori primi și tipurile numerice pentru a verifica operațiile folosite aici.

Întrebări frecvente

Ce numără funcția Euler phi?

Numără întregii pozitivi cel mult egali cu n care au cel mai mare divizor comun 1 cu n. Ea descrie o proprietate de coprimalitate, nu numărul divizorilor sau numărul factorilor primi.

De ce folosim fiecare factor prim o singură dată?

Multiplii lui p sunt deja eliminați la prima aplicare a factorului 1−1/p. Repetarea operației pentru fiecare putere a aceluiași prim ar elimina incorect și alte numere.

Care este valoarea phi pentru un număr prim?

Pentru un prim p, valoarea este p−1. Singurul număr exclus din intervalul 1..p este p însuși; toate celelalte au divizor comun maxim 1 cu p.