Phi function

Coddy'nin Matematiksel Bilmeceler kursunda ders 12 / 20.

Euler'in Totient fonksiyonu, φ(n) [bazen phi fonksiyonu olarak da adlandırılır], n'den küçük ve n ile aralarında asal olan sayıların miktarını belirlemek için kullanılır. Örneğin; 1, 2, 4, 5, 7 ve 8 sayılarının tamamı dokuzdan küçüktür ve dokuz ile aralarında asaldır (yani tüm bu sayılar ile 9 arasındaki en büyük ortak bölen 1'dir),

bu durumda phi fonksiyonunun sonucu φ(9)=6 olur. GCD (EBOB) hesaplamayı öğrendiğimiz için, (GCD fonksiyonunun yardımıyla) phi fonksiyonunu hesaplayabiliriz.

Görev

Zor

Bir n sayısı alan ve φ(n) değerini döndüren bir phi fonksiyonu yazın.

Kendin dene

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