Phi function

Coddyの「数学パズル」コースのレッスン 12/20。

オイラーのトーシェント関数 φ(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;
}