欧拉函数
定义：
$1∼N$ 中与 $N$ 互质的数的个数被称为欧拉函数，记为 $\phi(N)$。
若在算数基本定理中，$N=p^{a_1}_1p^{a_2}_2…p^{a_m}_m$，则：
$\phi(N) = N×\frac {p_1−1}{p_1}×\frac {p_2−1}{p_2}×…×\frac {p_m−1}{p_m}$
求法：线性筛
phi[1]=1，若筛到当前数为素数，则phi[i]=i-1，
定义：
$1∼N$ 中与 $N$ 互质的数的个数被称为欧拉函数，记为 $\phi(N)$。
若在算数基本定理中，$N=p^{a_1}_1p^{a_2}_2…p^{a_m}_m$，则：
$\phi(N) = N×\frac {p_1−1}{p_1}×\frac {p_2−1}{p_2}×…×\frac {p_m−1}{p_m}$
求法：线性筛
phi[1]=1，若筛到当前数为素数，则phi[i]=i-1，