#154. 「数论」欧拉函数(一)

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Menci

题目描述

欧拉函数 \varphi(n) 表示 [1, n] 中与 n 互质的正整数的个数。

给定 n ,求 \varphi(n)

输入格式

一行一个正整数 n

输出格式

一行一个正整数 \varphi(n)

样例

样例输入

15

样例输出

8

数据范围与提示

2 \leq n \leq 10 ^ {14}