Indicatorul lui Euler

De ce contează?

La un ceas cu n poziții, te întrebi din câte „pași" diferiți poți porni ca să atingi toate pozițiile înainte să revii la start. Răspunsul ține de câte numere până la n nu au „nimic în comun" cu n. Acel număr are un nume: indicatorul lui Euler.

Ce este φ(n)

Indicatorul lui Euler φ(n) numără câte numere din [1, n] sunt prime cu n (cmmdc = 1).

n	numere prime cu n	φ(n)
6	1, 5	2
12	1, 5, 7, 11	4
7 (prim)	1, 2, 3, 4, 5, 6	6

Observația-cheie

Pentru un număr prim p, toate numerele de la 1 la p−1 sunt prime cu el, deci φ(p) = p − 1. Asta îl face util în teorema lui Euler și la inversul modular.

Formula prin factori primi

φ se calculează din factorii primi distincți ai lui n:

φ(n) = n · ∏ (1 − 1/p), pentru fiecare factor prim distinct p al lui n

Exemplu, n = 12 = 2²·3: φ(12) = 12 · (1 − 1/2) · (1 − 1/3) = 12 · 1/2 · 2/3 = 4.

Trucul pe întregi: scădere în loc de fracție

În aritmetica întreagă 1/p e 0. Rescrii rez · (1 − 1/p) ca rez − rez/p — rămâi pe întregi, exact, fiindcă în acel moment p divide rez.

Implementare C++

#include <iostream>
using namespace std;

long long euler(long long n) {
    long long rez = n;
    for (long long p = 2; p * p <= n; p++) {
        if (n % p == 0) {               // p e factor prim
            while (n % p == 0) n /= p;  // scoatem tot factorul
            rez -= rez / p;             // rez = rez * (1 - 1/p)
        }
    }
    if (n > 1) rez -= rez / n;          // factorul prim mare ramas
    return rez;
}

int main() {
    cout << euler(12) << "\n";   // 4
    cout << euler(7) << "\n";    // 6
    return 0;
}

Observația-cheie

Aplici rez -= rez / p o singură dată per factor prim distinct (de aceea scoți tot factorul cu while). Iar if (n > 1) la final prinde factorul prim mai mare decât √n — exact ca la descompunerea în factori primi.

Complexitate

Caz	Timp	Spațiu
oricare	O(√n)	O(1)

Costul vine din găsirea factorilor primi (până la √n). Pentru φ a tuturor numerelor până la N, există o variantă cu ciur, O(N log log N).

Greșeli frecvente

Capcane reale la indicatorul lui Euler:

Aplici (1 − 1/p) direct pe întregi: 1/p e 0 → rezultat egal cu n. Folosește rez -= rez/p.
Numeri factorul de mai multe ori: aplici reducerea pentru fiecare apariție a lui p, nu o dată per factor distinct. Scoate tot factorul cu while.
Uiți if (n > 1): ratezi factorul prim mare → φ greșit (ex. pentru n = 14 ai pierde 7).
Overflow la p * p: pentru n mare, scrie pe long long.

De reținut

φ(n) = câte numere din [1, n] sunt prime cu n; φ(p) = p − 1 pentru p prim.
Formula: n · ∏(1 − 1/p) pe factori primi distincți; pe întregi folosește rez -= rez/p.
O(√n); if (n > 1) la final pentru factorul prim mare.