欧拉函数定义

1~n中与n互质的数个数称为欧拉函数，记为phi(n)。
例如：phi(1)=1,phi(2)=1,phi(3)=2,phi(4)=2;不懂自己模拟一下

欧拉函数的性质

1.若p是质数，则phi(p)=p-1;
2.若p是质数，则phi(p^k)=(p-1)phi(p^(k-1));
3.积性函数：若gcd(m,n)=1,则phi(mn)=phi(m)*phi(n);//当i%primes[j]!=0 时用到此性质

下面写不来，上图

以上内容来自B站-董晓算法
建议直接看原视频：【G09 筛法求欧拉函数】https://www.bilibili.com/video/BV1VP411p7Bs?vd_source=5b08a235ad6a90b6c35af25ededc9fd4