Tag Discussion Solution Statistics Submit
 

時間制限 : sec, メモリ制限 : KB
English / Japanese  

オイラーのφ関数

正の整数 n について、1 から n までの自然数のうち n と互いに素なものの個数を求めよ。

入力

n

１つの整数 n (1 ≤ n ≤ 1000000000).

出力

n と互いに素なものの個数。

入力例 1

6

出力例 1

2

入力例 2

1000000

出力例 2

400000
Source: https://onlinejudge.u-aizu.ac.jp/problems/NTL_1_D