Problem2774--数论基础之欧拉函数

2774: 数论基础之欧拉函数

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 68  Solved: 35
[Submit] [Status] [Web Board] [Creator:]

Description

给定n,一个正整数,小于n的多少个正整数相对n是素数?

Input

测试数据为多组,对于每组测试数据输入一个正整数N(N<=1000000000)

Output

对于每组测试数据输出一个正整数Phi,表示答案。

Sample Input Copy

30

Sample Output Copy

8

Source/Category