Hàm phi

Bài học 12 trên 20 trong khóa học Câu đố toán học của Coddy.

Hàm phi Euler, φ(n) [đôi khi còn gọi là hàm phi], được dùng để xác định số lượng số nhỏ hơn n và nguyên tố cùng nhau với n. Ví dụ, 1, 2, 4, 5, 7 và 8 đều nhỏ hơn chín và nguyên tố cùng nhau với chín (nghĩa là ước chung lớn nhất của mỗi số này với 9 là 1),

vậy kết quả của hàm phi là φ(9)=6. Vì chúng ta đã học cách tính GCD, nên chúng ta có thể tính hàm phi (với sự trợ giúp của hàm GCD).

Thử thách

Khó

Viết một hàm (function) phi nhận một số n và trả về φ(n).

Tự làm thử

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