如何计算的厄拉多塞筛法的时间复杂度?

Question

这是书中的原文:

厄拉多塞筛法是一种用于计算小于N的所有素数的方法. 我们从制作整数2到N的表开始. 找出最小的未被删除的整数i,然后删除i,2i,3i.... 当i>√N时, 算法终止

答案是NloglogN, 却没有说具体是怎么算的.

上网找了好久, 都是只有结论, 没有讲如何算出来的.

Answer 1

O(NloglogN)数的是算术运算的次数。当N很大时，每个算术运算不一定在常数个指令周期内完成。不妨假设算术运算的时间复杂度是O(logN)，也就是存储N所需要的空间。

此时厄拉多塞筛法的时间复杂度是O(NloglogN) * O(logN) = O(NlogNloglogN)。

而这个loglogN又是怎么来的呢？厄拉多塞筛法找到k的时候需要标记O(N/k)个数为合数。因此一共需要标记 次，其中p <= N表示所有小于等于N的素数。这就是N乘以小于等于N的素数的倒数之和。右手边是O(N)*O(loglogN) = O(NloglogN)的。