普通筛法时间界 O(nlnlnn) 的证明

定义

朴素素数筛法即是利用每一个素数筛出所有他的倍数。

对于待筛选的最大数n，由于素数分布定理，其中的素数个数约等于 nlnn，第i个素数约为 ilni。则算法总的运行次数为：

\sum i = 1 n ln n n i ln i = n \sum i = 1 n ln n 1 i ln i \dots (1)

(为了方便，计 ln1=1 )
考虑对

\sum i = 1 n ln n 1 i ln i \dots (2)

用积分估值。有：

\sum i = 1 n ln n 1 i ln i = O (\int n ln n 2 1 i ln i d i) \dots (3)

由微积分基本定理：

(3) = O (F (n ln n)) \dots (4) F (x) = \int 1 i ln i d i = ln ln i

因而：

(2) = (4) = O (ln ln n ln n) = O (ln ln n - ln ln ln n) = O (ln ln n)

所以：

(1) = O (n ln ln n)

证毕。