考虑一种线性筛法，可在优于 \(\Theta (n)\) 或 \(\Theta(n)\) 的复杂度下筛素数。
变量解释
-
\(phi[i]\): 这个就是 \(\varphi(i)\) ， 其中 $$\varphi(n)=\sum_{i=1} ^{n} [i|n]$$ 其中 \(\varphi(n)\) 是一个积性函数.
-
考虑到埃氏筛法的冗余计算，考虑优化反复标记操作的冗余。维护一个数组 \(vis[N]\)，\(vis[i]\) 表示 \(i\) 的最小质数。如果被标记迭代就表示 \(i\) 并非质数，反之为质数。考虑优化。
维护一个数组 \(prime[N]\) ， \(prime[i]\) 等于第 \(i\) 个质数。
后续再证明一下
巧妙之处
与埃氏筛法相比，欧拉筛将自己的复杂度控制到了 \(\Theta (n)\), 它的核心原理是优化对于 \(x\) 处理 \(x\) 相关的标记。
甚至还能处理对于最小质因数。
先在这里说一下积性函数的性质：
\[\varphi(x) \times \varphi(y) = varphi(x\times y)
\]
筛选标记的过程
如果要筛选 \(x\) 相关的质数，维护以下操作：
枚举 \(\forall y\in [1,x] \cap prime\)，对 \(y\) 进行以下操作：
首先考虑到欧拉函数的性质，然后对 \(phi[i] , vis[i]\) 迭代。
其次注意到如果 \(y|n\) ， 那么就跳出此次的循环。
肉眼可见，因为欧拉还是具有一些奇奇怪怪的冗余东西和大量的 \(\%\) ， 导致了欧拉筛巨大的常数。
证明
不证明.jpg