【数学知识】三种方法求 [1,n] 中所有数欧拉函数（线性筛欧拉函数优化至 O(n) ）

整理的算法模板合集： ACM模板

①直接求小于或等于n,且与n互质的数个数（求[1,n]中所有数的欧拉函数时间复杂度： O ( n n ) O(n\sqrt{n}) O(nn ​)）

②求[1,n]之间每个数的质因数的个数（求[1,n]中所有数的欧拉函数时间复杂度： O ( n l o g n ) O(nlogn) O(nlogn)）

③线性筛欧拉函数求[1,n]之间每个数的质因数的个数（求[1,n]中所有数的欧拉函数时间复杂度： O ( n ) O(n) O(n)）

第三种方法的证明