Fungsi phi

Pelajaran 12 dari 20 dalam kursus Teka-teki Matematika di Coddy.

Fungsi Totient Euler, φ(n) [terkadang disebut fungsi phi], digunakan untuk menentukan jumlah bilangan yang kurang dari n dan relatif prima terhadap n. Sebagai contoh, 1, 2, 4, 5, 7, dan 8 semuanya kurang dari sembilan dan relatif prima terhadap sembilan (artinya, pembagi persekutuan terbesar antara masing-masing bilangan tersebut dan 9 adalah 1),

maka hasil fungsi phi adalah φ(9)=6. Karena kita telah belajar menghitung FPB, kita dapat menghitung fungsi phi (dengan bantuan fungsi FPB).

Tantangan

Sulit

Tulis fungsi phi yang menerima angka n dan mengembalikan φ(n).

Coba sendiri

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