#YS240102. 互质数个数

互质数个数

2、互质数个数

Tom猫这天抓到了Jerry鼠并把Jerry关在一个透明玻璃盒子里面,Jerry被关了一天,很饿了,求Tom放它出来吃东西。Tom表示如果Jerry能帮它解答一道数学题,就放它出来,并且送牛奶给Jerry喝,这道数学题是这样的:

有一个正整数n,求1--n内,有多少个数与n互质。

Jerry的数学很差,饿急了的它向你求助,请你帮它计算下。

输入格式:

输入一行包含一个整数n。

输出格式:

输出一行一个整数,即有多少个数与n互质。

输入数据:
10000
输出数据:
4000
数据范围:

20%数据:1<=n<=1031<=n<=10^3

100%数据:1<=n<=51061<=n<=5*10^6