CP区 前缀和 大批 矩阵 欧拉函数-phi(n),Φ(n) n和i(1到n-1)之间的互质数(GCD == 1) 蛮力解(查找所有互素)-> O(nlogn) 具有公式(2)的解决方案-> O(sqrt(n)) 乘积规则(3)的解决方案示例:phi(5)= 4 1-如果n为质数-> phi(n)= n-1 2-如果a = p ^ n-> phi(a)= p ^ n-p ^(n-1) 3- phi(n)= n *((1-1 / p1)* .... *(1-1 / pi)) 筛 筛选基于创建从1到n的数组 eratosthenes筛子:查找给定数字是否为质数,Sieve数组将包含布尔值,