线性筛 埃氏筛 对于每个数\(x\)，枚举其倍数，将\(kx\)筛去。在埃氏筛过程中，每个数都会被筛掉多次，且对于每个数x，枚举其倍数的次数为\(\frac{n}{x}\)故埃氏筛的时间复杂度为\(\sum_{i=1}^{n}\frac{n}{i}=n\sum_{i=1}^{n}\frac

首先有以下性质：(p 为素数) 1. （p）=p-1 2. 如果i mod p==0，那么( i*p )=p*( i ) 3. 若i mod p≠0，那么（i*p）=（i）*（p-1） 证明见http://blog.csdn.net/Lytning/article/det