Indicatorul lui Euler

Intuiția

Indicatorul lui Euler phi(n) numără câte valori din 1, 2, ..., n sunt prime cu n, adică au cmmdc cu n egal cu 1. Pentru n = 12, numerele care împart un factor cu 12 sunt cele divizibile cu 2 sau cu 3 (factorii primi ai lui 12). Tot ce rămâne — 1, 5, 7, 11 — e prim cu 12, deci phi(12) = 4.

Cheia e că nu contează cât de des apare un factor prim, ci care sunt factorii primi distincți ai lui n. Un număr e „rudă" cu 12 fix când e divizibil cu 2 sau cu 3. De aceea phi se poate calcula direct din descompunerea în factori primi, fără să verifici fiecare număr în parte.

Vezi cum funcționează

Pasul-cheie din formula phi este descompunerea lui n în factori primi. Urmărește în vizualizare cum 12 se desface în 2 * 2 * 3: factorii primi distincți sunt 2 și 3, exact cei care decid valoarea lui phi.

Algoritmul pas cu pas

Calculăm phi(12). Mai întâi descompunem: 12 = 2^2 * 3, deci factorii primi distincți sunt 2 și 3. Pornim cu phi = 12 și aplicăm formula factor cu factor.

Forma sigură a fiecărui pas este phi = phi / p * (p - 1) — întâi împărțim (eliminăm multiplii lui p), apoi înmulțim cu p - 1 (păstrăm cei care nu se divid cu p):

Verificare prin numărare directă: trecem prin toate numerele din 1..12 și păstrăm doar pe cele care nu se divid nici cu 2, nici cu 3 (factorii primi ai lui 12). Cad: 2, 3, 4, 6, 8, 9, 10, 12 (divizibile cu 2 sau cu 3). Rămân exact patru:

Implementare C++

Descompunem n testând divizori d de la 2 cât timp d * d <= n. Când d divide n, e factor prim (l-am scos pe toți cei mai mici înainte), așa că aplicăm formula și eliminăm toate aparițiile lui d. Dacă la final mai rămâne n > 1, acela e un ultim factor prim mare:

#include <iostream>
using namespace std;

long long phi(long long n) {
    long long rezultat = n;          // pornim de la n
    for (long long d = 2; d * d <= n; d++) {
        if (n % d == 0) {            // d este factor prim
            rezultat = rezultat / d * (d - 1);  // intai impart, apoi inmultesc
            while (n % d == 0) {     // scot TOATE aparitiile lui d
                n = n / d;
            }
        }
    }
    if (n > 1) {                     // a ramas un factor prim mare
        rezultat = rezultat / n * (n - 1);
    }
    return rezultat;
}

int main() {
    cout << phi(12) << endl;   // 4   (1, 5, 7, 11)
    cout << phi(10) << endl;   // 4   (1, 3, 7, 9)
    cout << phi(7) << endl;    // 6   (prim: 1..6 toate)
    return 0;
}

Complexitate

Bucla testează divizori doar până la sqrt(n), fiindcă un număr are cel mult un factor prim mai mare decât rădăcina lui (tratat de verificarea finală n > 1). Față de numărarea naivă O(n log n), e o accelerare uriașă pentru n mare.