关于质数筛法的时间复杂度问题

[何欣洋]

主要是因为今天直播的老师将复杂度讲错了……

1. 一种暴力的筛法（见今天J组初赛模拟第17题）：

   for (int i = 2; i < maxn; ++i)
           for (int j = i * 2; j < maxn; j += i)
               isNotPrime[j] = 1;
   

   这个复杂度很明显是：

   \sum_{i=1}^n \dfrac{n}{i}=n\sum_{i=1}^n \frac{n}{i} \approx n\log n

2. 埃式筛法

   memset(prime,1,sizeof(prime));
   prime[0]=prime[1]=0;
   for(int i=2;i<=n;++i){
   	if(prime[i]){
   		for(int j=2*i;j<=n;j+=i) prime[j]=0;
   	}
   }
   

   相比上面那一个，这个判断了 i 是否为质数。经过估算，这个复杂度约为 n \log \log n。

3. 欧拉筛法

   也就是著名的线性筛，复杂度 \mathcal{O}(n)，代码不放了。

[CZF2919 (陈泽樊)]

@何欣洋

\displaystyle\sum_{i=1}^n \frac{n}{i}=n \displaystyle \sum_{i=1}^n \frac{n}{i}≈n \log n

应该写成 \displaystyle\sum_{i=1}^n \frac{n}{i}=n \displaystyle \sum_{i=1}^n \frac{1}{i}≈n \log n 吧！