Funzione Phi

Lezione 12 di 20 del corso Indovinelli matematici di Coddy.

La funzione totiente di Eulero, φ(n) [a volte chiamata funzione phi], viene usata per determinare il numero di numeri minori di n che sono coprimi con n. Per esempio, poiché 1, 2, 4, 5, 7 e 8 sono tutti minori di nove e coprimi con nove (il che significa che il massimo comune divisore tra ciascuno di questi numeri e 9 è il numero 1),

il risultato della funzione phi è φ(9)=6. Poiché abbiamo imparato a calcolare il MCD, possiamo calcolare la funzione phi (con l'aiuto della funzione MCD).

Sfida

Difficile

Scrivi una funzione phi che riceve un numero n e restituisce φ(n).

Provalo tu

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