Funkcja phi

Lekcja 12 z 20 w kursie Zagadki matematyczne w Coddy.

Funkcja Eulera φ(n) [czasami nazywana funkcją phi] służy do określania liczby liczb mniejszych od n, które są względnie pierwsze z n. Na przykład liczby 1, 2, 4, 5, 7 i 8 są mniejsze od dziewięciu i względnie pierwsze z dziewięć (co oznacza, że największy wspólny dzielnik każdej z tych liczb i 9 wynosi 1),

wynikiem funkcji phi jest wtedy φ(9)=6. Skoro nauczyliśmy się obliczać NWD, możemy obliczyć funkcję phi (z pomocą funkcji NWD).

Wyzwanie

Trudny

Napisz funkcję phi, która otrzymuje liczbę n i zwraca φ(n).

Spróbuj swoich sił

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