学步园

    水题，不解释。。。题目：

描述

For given integer N (1<=N<=10⁴) find amount of positive numbers not greater than N that coprime with N. Let us call two positive integers (say, A and B, for example)
coprime if (and only if) their greatest common divisor is 1. (i.e. A and B are coprime iff gcd(A,B) = 1).

输入

Input file contains integer N.（ 注意：程序以文件结束符“EOF”结束输入。）

输出

Write answer in output file. 每个数字占一行。

样例输入

9

样例输出

6

ac代码：

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int main(){
  int n;
  while(~scanf("%d",&n)){
    int ans=n;
	int m=sqrt(n+0.5);
	for(int i=2;i<=m;++i){
	  if(n%i==0)
		  ans=ans-ans/i;
	  while(n%i==0)
		  n/=i;
	}
	if(n>1)ans=ans-ans/n;
	printf("%d\n",ans);
  }
  return 0;
}