这是书中的原文:
厄拉多塞筛法是一种用于计算小于N的所有素数的方法. 我们从制作整数2到N的表开始. 找出最小的未被删除的整数i,然后删除i,2i,3i.... 当i>√N时, 算法终止
答案是NloglogN, 却没有说具体是怎么算的.
上网找了好久, 都是只有结论, 没有讲如何算出来的.
O(NloglogN)数的是算术运算的次数。当N很大时，每个算术运算不一定在常数个指令周期内完成。不妨假设算术运算的时间复杂度是O(logN)，也就是存储N所需要的空间。
此时厄拉多塞筛法的时间复杂度是O(NloglogN) * O(logN) = O(NlogNloglogN)。
而这个loglogN又是怎么来的呢？厄拉多塞筛法找到k的时候需要标记O(N/k)个数为合数。因此一共需要标记 次，其中p <= N表示所有小于等于N的素数。这就是N乘以小于等于N的素数的倒数之和。的。