Phi function

Coddy의 수학 수수께끼 코스 레슨 — 20개 중 12번째.

오일러 피 함수(Euler's Totient function), φ(n) [때때로 피 함수라고도 불림]은 n보다 작으면서 n과 서로소인 수의 개수를 구하는 데 사용됩니다. 예를 들어, 1, 2, 4, 5, 7, 8은 모두 9보다 작고 9와 서로소이므로(즉, 이 모든 수와 9 사이의 최대공약수가 1이라는 의미입니다),

피 함수의 결과는 φ(9)=6이 됩니다. GCD를 계산하는 법을 배웠으므로, (GCD 함수의 도움을 받아) 피 함수를 계산할 수 있습니다.

챌린지

어려움

숫자 n을 입력받아 φ(n)을 반환하는 함수 phi를 작성하세요.

직접 해보기

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