新年快到了，“猪头帮协会”准备搞一个聚会，已经知道现有会员N人，把会员从1到N编号，其中会长的号码是N号，凡是和会长是老朋友的，那么该会员的号码肯定和N有大于1的公约数，否则都是新朋友，现在会长想知道究竟有几个新朋友？请你编程序帮会长计算出来。


解题思路：这是一道裸的欧拉函数题目
        对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler's totient function、φ函数、欧拉商数等。
       

       欧拉函数通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1      （唯 一和1互质的数就是1本身）。 
       
      
代码：

 1#include <iostream>
 2#include <cstdio>
 3#include <cmath>
 4#include <cstring>
 5
 6using namespace std;
 7
 8int n,T;
 9
10int euler(int x)
11{  int i,res=x;
12   for (i=2; i<(int)sqrt(x*1)+1; i++)
13     {  if (x % i ==0)
14           {
15               res=res/i*(i-1);
16               while (x % i==0) x=x/i;
17           }
18     }
19    if (x>1) res=res/x*(x-1);
20    return res;
21
22}
23
24int main()
25{   cin >> T;
26    while (T--)
27    {  cin >> n;
28       cout << euler(n)<< endl;
29
30    }
31    return 0;
32}
33