欧拉函数：https://blog.csdn.net/liuzibujian/article/details/81086324
小于 $x$ 的整数中与 $x$ 互质的数的个数
例如： $φ(1)=1$
$φ(24)=8$,因为1, 5, 7, 11, 13, 17, 19, 23均和 24 互质
题目表述：
给定n个正整数ai，请你求出每个数的欧拉函数。
输入格式
第一行包含整数n。
接下来n行，每行包含一个正整数aiai。
输出格式
输出共n行，每行输出一个正整数aiai的欧拉函数。
数据范围
1≤n≤1001≤n≤100,
1≤ai≤2∗1091≤ai≤2∗109
输入样例：
3
3
6
8
输出样例：
2
2
4
模板参考：
int phi(int x)
{
int res = x;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
if (x > 1) res = res / x * (x - 1);
return res;
}
筛法求欧拉函数
以12为例。12的因子有1,2,3,4,6,12。把与这些数互质的数列出来：
1:1
2:1
3:1 2
4:1 3
6:1 5
12 1 5 7 11
不妨把这些数作为分母，把与这些数互质的数作为分子，写成分数形式：
1/1
1/2
1/3 2/3
1/4 3/4
1/6 5/6
1/12 5/12 7/12 11/12
显然，每一行的数的个数就是该行的分母的欧拉函数值。倘若把这些数都改成以12为分母的数：
12/12
6/12
4/12 8/12
3/12 9/12
2/12 10/12
1/12 5/12 7/12 11/12
可以发现，这些数是以12为分母，1~12为分子的所有数，所以个数为12个。所以与12互质的数的欧拉函数值之和就是12。这样，命题大概就被证明了吧。
题目表述：
给定一个正整数n，求1~n中每个数的欧拉函数之和。
输入格式
共一行，包含一个整数n。
输出格式
共一行，包含一个整数，表示1~n中每个数的欧拉函数之和。
数据范围
1≤n≤1061≤n≤106
输入样例：
6
输出样例：
12
模板参考：
int primes[N], cnt; // primes[]存储所有素数
int euler[N]; // 存储每个数的欧拉函数
bool st[N]; // st[x]存储x是否被筛掉
void get_eulers(int n)
{
euler[1] = 1;
for (int i = 2; i <= n; i ++ )
{
if (!st[i])
{
primes[cnt ++ ] = i;
euler[i] = i - 1;
}
for (int j = 0; primes[j] <= n / i; j ++ )
{
int t = primes[j] * i;
st[t] = true;
if (i % primes[j] == 0)
{
euler[t] = euler[i] * primes[j];
break;
}
euler[t] = euler[i] * (primes[j] - 1);
}
}
}
