Phi function

Lektion 12 von 20 im Kurs Mathematische Rätsel von Coddy.

Die Eulersche Phi-Funktion, φ(n) [manchmal auch Totient-Funktion genannt], wird verwendet, um die Anzahl der Zahlen kleiner als n zu bestimmen, die zu n teilerfremd sind. Da zum Beispiel 1, 2, 4, 5, 7 und 8 alle kleiner als neun und teilerfremd zu neun sind (was bedeutet, dass der größte gemeinsame Teiler zwischen all diesen Zahlen und 9 die Zahl 1 ist),

ist das Ergebnis der Phi-Funktion φ(9)=6. Da wir gelernt haben, den GCD (ggT) zu berechnen, können wir (mit Hilfe der GCD-Funktion) die Phi-Funktion berechnen.

Aufgabe

Schwer

Schreiben Sie eine Funktion phi, die eine Zahl n erhält und φ(n) zurückgibt.

Probier es selbst

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