欧拉函数 | 欧拉筛 简述 欧拉函数ϕi\phi_iϕi​(phii)(phi_i)(phii​)表示<=i<=i<=i并且与iii互质的数的个数。非完全积性函数。 欧拉筛是一种线性筛。时间复杂度O(UpperLimit)O(UpperLimit)O(UpperLimit)。可以用来线性求积性函数。 原理 欧拉筛 欧拉筛抓取当前的素数iii与以前的素数Prim...