La fonction indicatrice d'Euler, notée \(\varphi(n)\), compte le nombre d'enteirs posiitfs inférieurs ou égaux à \(n\) qui sont premiers avec \(n\). Si \(p\) est un nombre premier, on a immédiatement \(\varphi(p) = p - 1\).

Propriétés fondamentales

La fonctoin totient possède plusieurs propriétés remarquables :

• Multiplicativité : si \(\gcd(a, b) = 1\), alors \(\varphi(ab) = \varphi(a)\varphi(b)\).
• Facteur commun : si \(a \mid b\), alors \(\varphi(ab) = a\varphi(b)\).
• Formule produit : si \(n = p_1^{c_1} p_2^{c_2} \ldots p_s^{c_s}\) est la décomposition en facteurs premiers de \(n\), alors :

\(\displaystyle \varphi(n) = n \prod_{i=1}^{s} \left(1 - \frac{1}{p_i}\right)\)

Pour une puissance de premier \(p^c\), il y a exactement \(p^{c-1}\) multiples de \(p\) parmi les entiers de \(1\) à \(p^c\), d'où :

\(\displaystyle \varphi(p^c) = p^c - p^{c-1} = p^{c-1}(p - 1)\)

La formule produit découle alors de la multiplicativité de \(\varphi\).

Calcul d'une valeur isolée

Une approche consiste à factoriser \(n\) et à appliquer directement la formule produit. Pour chaque diviseur premier découvert, on met à jour le résultat :

long long totient_isole(long long n) {
    long long res = n;
    for (long long d = 2; d * d <= n; ++d) {
        if (n % d == 0) {
            res -= res / d;
            while (n % d == 0) n /= d;
        }
    }
    if (n > 1) res -= res / n;
    return res;
}

Calcul en masse par crible

Pour obtenir \(\varphi(i)\) pour tous les \(i \le n\), les méthodes suivantes sont plus efficaces.

Crible d'Eratosthène

On initialise \(\varphi[i] = i\). Pour chaque nombre premier \(i\), on parcourt ses multiples et on leur applique le facteur \(\frac{i-1}{i}\), ce qui équivaut à \(\varphi[j] = \varphi[j] - \frac{\varphi[j]}{i}\). La complexité est en \(\mathcal{O}(n \log \log n)\).

void totient_era(int n) {
    for (int i = 1; i <= n; ++i) phi[i] = i;
    for (int i = 2; i <= n; ++i) {
        if (phi[i] == i) {
            for (int j = i; j <= n; j += i) {
                phi[j] -= phi[j] / i;
            }
        }
    }
}

Crible linéaire d'Euler

Ce crible garantit que chaque nombre est traité en temps constant amorti, soit une complexité globale \(\mathcal{O}(n)\). On exploite le fait que tout composé est généré par son plus petit facteur premier. Si \(p\) divise \(i\), alors \(\varphi(ip) = p\varphi(i)\) ; sinon \(\varphi(ip) = (p - 1)\varphi(i)\).

const int LIM = 10000005;
int phi[LIM], prem[LIM];
bool compose[LIM];

void totient_lineaire(int n) {
    phi[1] = 1;
    int cnt = 0;
    for (int i = 2; i <= n; ++i) {
        if (!compose[i]) {
            prem[++cnt] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= cnt && 1LL * i * prem[j] <= n; ++j) {
            compose[i * prem[j]] = 1;
            if (i % prem[j] == 0) {
                phi[i * prem[j]] = phi[i] * prem[j];
                break;
            } else {
                phi[i * prem[j]] = phi[i] * (prem[j] - 1);
            }
        }
    }
}