פונקציית פי

שיעור 12 מתוך 20 בקורס חידות מתמטיות של Coddy.

פונקציית הטוטיאנט של אוילר, φ(n) [שנקראת לפעמים פונקציית פי], משמשת לקביעת מספר המספרים הקטנים מ־n שזרים ל־n. לדוגמה, מכיוון ש־1, 2, 4, 5, 7 ו־8 כולם קטנים מתשע וזרים לתשע (כלומר, המחלק המשותף הגדול ביותר של כל אחד מהמספרים האלה ושל 9 הוא 1),

אז התוצאה של פונקציית פי היא φ(9)=6. מכיוון שלמדנו לחשב GCD, אנחנו יכולים לחשב את פונקציית פי (בעזרת פונקציית GCD).

אתגר

קשה

כתבו פונקציה phi שמקבלת מספר n ומחזירה את φ(n).

נסו בעצמכם

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