欧拉函数：
\(1.\varphi(p)=p-1\)
证明：显然
\(2.\varphi(i*p)=p*\varphi(i)\) , \(if\space i \bmod p = 0\)
引理1：\(\varphi(p^a)=(p-1)*p^{a-1}\)
证明：比 \(p^a\) 小的数一共有 \(p^a-1\) 个，其中与 \(p^a\) 不互质的且小于 \(p^a\) 的
，即 \(p\) 的倍数 \(p*t\) 一共有 \(p^{a-1}-1\) 个，则 \(\varphi(p^a)=p^a-1-(p^{a-1}-1)=(p-1)*p^{a-1}\)引理2：\(\varphi(n)=n*(1-\frac{1}{p_1})*(1-\frac{1}{p_2})*···*(1-\frac{1}{p_k})\)
证明：
\(\varphi(n)\)
\(=\varphi(p_1^{a_1})*\varphi(p_2^{a_2})*···*\varphi(p_k^{a_k})\)
\(=(p_1-1)*p_1^{a_1-1}*(p_2-1)*p_2^{a_2-1}*···*(p_k-1)*p_k^{a_k-1}\)
\(=(p_1^{a_1}-p_1^{a_1-1})*···*(p_k^{a_k}-p_k^{a_k-1})\)
\(=p_1^{a_1}*(1-\frac{1}{p_1})*···*p_k^{a_k}*(1-\frac{1}{p_k})\)
\(=(p_1^{a_1}*p_2^{a_2}*···*p_k^{a_k})*(1-\frac{1}{p_1})*(1-\frac{1}{p_2})*···*(1-\frac{1}{p_k})\)
\(=n*(1-\frac{1}{p_1})*(1-\frac{1}{p_2})*···*(1-\frac{1}{p_k})\)
证明：
设 \(i\) 为正整数，且 \(i=p_1^{k_1}*p_2^{k_2}*···*p_n^{k_n}\)
\(\varphi(i)=i*(1-\frac{1}{p_1})*···*(1-\frac{1}{p_n})\)
\(\because i\bmod p=0\)
\(\therefore p为i的质因子\)
\(\therefore \varphi(i*p)=i*p*\prod_{i=1}^{n} (1-\frac{1}{p_i})=\varphi(i)*p\)
\(3.\varphi(i*p)=\varphi(i)*(p-1)\) , \(if\space i \bmod p \ne 0\)
证明：
\(\because i \bmod p \ne 0\)
\(\therefore p不为i的质因子\)
\(\therefore \varphi(i*p)=i*p*(1-\frac{1}{p})*\prod_{i=1}^n (1-\frac{1}{p_i})=i*(p-1)*\prod_{i=1}^n (1-\frac{1}{p_i})=\varphi(i)*(p-1)\)
于是可以通过这三个性质再配合上线性筛预处理处欧拉函数。
Code：
void Get(int listsize){ memset(isprime,1,sizeof(isprime)); isprime[1]=false; for(int i=2;i<=listsize;i++) { if(isprime[i]) { prime[++primesize]=i; phi[i]=i-1; } for(int j=1;j<=primesize&&i*prime[j]<=listsize;j++) { isprime[i*prime[j]]=false; if(i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break; } phi[i*prime[j]]=phi[i]*(prime[j]-1); } }}