Phi function

Lección 12 de 20 del curso Acertijos matemáticos de Coddy.

La función Totiente de Euler, φ(n) [a veces llamada función phi], se utiliza para determinar la cantidad de números menores que n que son primos relativos con n. Por ejemplo, como 1, 2, 4, 5, 7 y 8 son todos menores que nueve y primos relativos con nueve (lo que significa que el máximo común divisor entre todos estos números y 9 es el número 1),

entonces el resultado de la función phi φ(9)=6. Dado que aprendimos a calcular el GCD, podemos calcular (con la ayuda de la función GCD) la función phi.

Desafío

Difícil

Escribe una función phi que reciba un número n y devuelva φ(n).

Pruébalo tú mismo

#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;
}