1577 : 多少个互质数

时间限制:1 Sec 内存限制:128 MiB
提交:45 答案正确:32

提交 状态 讨论区

题目描述

给你一个整数N(1<=N<=10000), 求不超过N的并且和N互质的正整数数有多少个。(例如两个数A,B, 如果他们的最大公约数是1, 则这两个数互质, A可以等于B)

输入

一个正整数N,(测试数据有多组,使用EOF结束)

输出


			

样例输入

复制
9

样例输出

复制
6

提示


			

来源