Phi function

Leçon 12 sur 20 du cours Énigmes mathématiques de Coddy.

L'indicatrice d'Euler, φ(n) [parfois appelée fonction phi], est utilisée pour déterminer le nombre d'entiers inférieurs à n qui sont premiers avec n. Par exemple, comme 1, 2, 4, 5, 7 et 8 sont tous inférieurs à neuf et premiers avec neuf (ce qui signifie que le plus grand commun diviseur entre tous ces nombres et 9 est le nombre 1),

alors le résultat de la fonction phi est φ(9)=6. Puisque nous avons appris à calculer le PGCD, nous pouvons calculer (à l'aide de la fonction PGCD) la fonction phi.

Défi

Difficile

Écrivez une fonction phi qui reçoit un nombre n et renvoie φ(n).

Essayez vous-même

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "solution.h"

int main() {
    int n;
    if (scanf("%d", &n) != 1) n = 0;
    int r = phi(n);
    printf("%d\n", r);
    return 0;
}