#include <stdio.h>
 
/**
 * @brief オイラーのφ関数をint型のみで計算する
 * * @param n 計算対象の正の整数
 * @return int オイラーのφ関数の値 (φ(n))
 */
int euler_phi(int n) {
    // 負の数やゼロは扱わない
    if (n <= 0) {
        return 0;
    }
 
    // φ(1) = 1
    if (n == 1) {
        return 1;
    }
 
    int result = n;
    int temp_n = n; // 素因数分解用にコピー
 
    // 1. i=2 の処理
    // 2が因数であれば、φ(n) = φ(n) * (1 - 1/2) の計算を行う
    if (temp_n % 2 == 0) {
        // result = result / 2 * (2 - 1) = result / 2
        result = result / 2;
 
        // temp_n から素因数2を完全に取り除く
        while (temp_n % 2 == 0) {
            temp_n /= 2;
        }
    }
 
    // 2. i=3 以上の奇数の処理
    // i*i <= temp_n までループすることで、素数のみを効率的にチェック
    for (int i = 3; i * i <= temp_n; i += 2) {
        if (temp_n % i == 0) {
            // 素因数 i が見つかった場合、計算式を適用
            // result = result / i * (i - 1)
            result = result / i;
            result = result * (i - 1);
 
            // temp_n から素因数 i を完全に取り除く
            while (temp_n % i == 0) {
                temp_n /= i;
            }
        }
    }
 
    // 3. ループ終了後、temp_n が 1 より大きければ、残りが最大の素因数
    if (temp_n > 1) {
        // 残った素因数 temp_n に対して計算を適用
        // result = result / temp_n * (temp_n - 1)
        result = result / temp_n;
        result = result * (temp_n - 1);
    }
 
    return result;
}
 
int main(void) {
    int num;
 
    printf("正の整数を入力してください: ");
    // 入力が成功し、かつ正の数であることを確認
    if (scanf("%d", &num) != 1 || num <= 0) {
        printf("無効な入力です。\n");
        return 1;
    }
 
    int euler = euler_phi(num);
 
    printf("φ(%d) = %d\n", num, euler);
 
    return 0;
}

I2luY2x1ZGUgPHN0ZGlvLmg+CgovKioKICogQGJyaWVmIOOCquOCpOODqeODvOOBrs+G6Zai5pWw44KSaW505Z6L44Gu44G/44Gn6KiI566X44GZ44KLCiAqICogQHBhcmFtIG4g6KiI566X5a++6LGh44Gu5q2j44Gu5pW05pWwCiAqIEByZXR1cm4gaW50IOOCquOCpOODqeODvOOBrs+G6Zai5pWw44Gu5YCkICjPhihuKSkKICovCmludCBldWxlcl9waGkoaW50IG4pIHsKICAgIC8vIOiyoOOBruaVsOOChOOCvOODreOBr+aJseOCj+OBquOBhAogICAgaWYgKG4gPD0gMCkgewogICAgICAgIHJldHVybiAwOwogICAgfQogICAgCiAgICAvLyDPhigxKSA9IDEKICAgIGlmIChuID09IDEpIHsKICAgICAgICByZXR1cm4gMTsKICAgIH0KCiAgICBpbnQgcmVzdWx0ID0gbjsKICAgIGludCB0ZW1wX24gPSBuOyAvLyDntKDlm6DmlbDliIbop6PnlKjjgavjgrPjg5Tjg7wKCiAgICAvLyAxLiBpPTIg44Gu5Yem55CGCiAgICAvLyAy44GM5Zug5pWw44Gn44GC44KM44Gw44CBz4YobikgPSDPhihuKSAqICgxIC0gMS8yKSDjga7oqIjnrpfjgpLooYzjgYYKICAgIGlmICh0ZW1wX24gJSAyID09IDApIHsKICAgICAgICAvLyByZXN1bHQgPSByZXN1bHQgLyAyICogKDIgLSAxKSA9IHJlc3VsdCAvIDIKICAgICAgICByZXN1bHQgPSByZXN1bHQgLyAyOwogICAgICAgIAogICAgICAgIC8vIHRlbXBfbiDjgYvjgonntKDlm6DmlbAy44KS5a6M5YWo44Gr5Y+W44KK6Zmk44GPCiAgICAgICAgd2hpbGUgKHRlbXBfbiAlIDIgPT0gMCkgewogICAgICAgICAgICB0ZW1wX24gLz0gMjsKICAgICAgICB9CiAgICB9CgogICAgLy8gMi4gaT0zIOS7peS4iuOBruWlh+aVsOOBruWHpueQhgogICAgLy8gaSppIDw9IHRlbXBfbiDjgb7jgafjg6vjg7zjg5fjgZnjgovjgZPjgajjgafjgIHntKDmlbDjga7jgb/jgpLlirnnjofnmoTjgavjg4Hjgqfjg4Pjgq8KICAgIGZvciAoaW50IGkgPSAzOyBpICogaSA8PSB0ZW1wX247IGkgKz0gMikgewogICAgICAgIGlmICh0ZW1wX24gJSBpID09IDApIHsKICAgICAgICAgICAgLy8g57Sg5Zug5pWwIGkg44GM6KaL44Gk44GL44Gj44Gf5aC05ZCI44CB6KiI566X5byP44KS6YGp55SoCiAgICAgICAgICAgIC8vIHJlc3VsdCA9IHJlc3VsdCAvIGkgKiAoaSAtIDEpCiAgICAgICAgICAgIHJlc3VsdCA9IHJlc3VsdCAvIGk7CiAgICAgICAgICAgIHJlc3VsdCA9IHJlc3VsdCAqIChpIC0gMSk7CiAgICAgICAgICAgIAogICAgICAgICAgICAvLyB0ZW1wX24g44GL44KJ57Sg5Zug5pWwIGkg44KS5a6M5YWo44Gr5Y+W44KK6Zmk44GPCiAgICAgICAgICAgIHdoaWxlICh0ZW1wX24gJSBpID09IDApIHsKICAgICAgICAgICAgICAgIHRlbXBfbiAvPSBpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQoKICAgIC8vIDMuIOODq+ODvOODl+e1guS6huW+jOOAgXRlbXBfbiDjgYwgMSDjgojjgorlpKfjgY3jgZHjgozjgbDjgIHmrovjgorjgYzmnIDlpKfjga7ntKDlm6DmlbAKICAgIGlmICh0ZW1wX24gPiAxKSB7CiAgICAgICAgLy8g5q6L44Gj44Gf57Sg5Zug5pWwIHRlbXBfbiDjgavlr77jgZfjgaboqIjnrpfjgpLpgannlKgKICAgICAgICAvLyByZXN1bHQgPSByZXN1bHQgLyB0ZW1wX24gKiAodGVtcF9uIC0gMSkKICAgICAgICByZXN1bHQgPSByZXN1bHQgLyB0ZW1wX247CiAgICAgICAgcmVzdWx0ID0gcmVzdWx0ICogKHRlbXBfbiAtIDEpOwogICAgfQoKICAgIHJldHVybiByZXN1bHQ7Cn0KCmludCBtYWluKHZvaWQpIHsKICAgIGludCBudW07CiAgICAKICAgIHByaW50Zigi5q2j44Gu5pW05pWw44KS5YWl5Yqb44GX44Gm44GP44Gg44GV44GEOiAiKTsKICAgIC8vIOWFpeWKm+OBjOaIkOWKn+OBl+OAgeOBi+OBpOato+OBruaVsOOBp+OBguOCi+OBk+OBqOOCkueiuuiqjQogICAgaWYgKHNjYW5mKCIlZCIsICZudW0pICE9IDEgfHwgbnVtIDw9IDApIHsKICAgICAgICBwcmludGYoIueEoeWKueOBquWFpeWKm+OBp+OBmeOAglxuIik7CiAgICAgICAgcmV0dXJuIDE7CiAgICB9CgogICAgaW50IGV1bGVyID0gZXVsZXJfcGhpKG51bSk7CgogICAgcHJpbnRmKCLPhiglZCkgPSAlZFxuIiwgbnVtLCBldWxlcik7CgogICAgcmV0dXJuIDA7Cn0=

MzA=

30