Phi function

Lição 12 de 20 do curso Enigmas Matemáticos da Coddy.

A função Totiente de Euler, φ(n) [às vezes chamada de função phi], é usada para determinar a quantidade de números menores que n que são relativamente primos a n. Por exemplo, como 1, 2, 4, 5, 7 e 8 são todos menores que nove e relativamente primos a nove (o que significa que o máximo divisor comum entre todos esses números e 9 é o número 1),

então o resultado da função phi φ(9)=6. Como aprendemos a calcular o MDC, podemos calcular (com a ajuda da função GCD) a função phi.

Desafio

Difícil

Escreva uma função phi que recebe um número n e retorna φ(n).

Experimente você mesmo

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