从维基百科：
该算法的复杂性是 O(n(logn)(loglogn))位运算。
O(n(logn)(loglogn))
你怎么到达的？
包含loglogn术语的复杂性告诉我在sqrt(n)某个地方。
loglogn
sqrt(n)
假设我在前100个数字（n =100）上运行筛子，假设将数字标记为复合数字需要固定的时间（数组实现），那么我们使用的次数mark_composite()将类似于
n =100
mark_composite()
n/2 + n/3 + n/5 + n/7 + ... + n/97 = O(n^2)
并且要查找下一个质数（例如，7在除掉所有倍数为的数字后跳至5），操作数将为O(n)。
7
5
O(n)
因此，复杂度为O(n^3)。 你同意吗？
O(n^3)
您的n / 2 + n / 3 + n / 5 +…n / 97不是O（n），因为项数不是常数。[编辑后编辑：O（n 2）的上限太宽松。]宽松的上限是n（1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 +… 1 / n）（不超过n 的 所有 数字的倒数之和），即O（n log n）：请参见谐波数。一个更合适的上限是n（1/2 + 1/3 + 1/5 + 1/7 +…），即最高达n的质数的倒数之和，即O（n log log n）。（请参阅此处或此处。）
总的来说，“查找下一个质数”位仅O（n），摊销后 –您将向前查找 总共 仅n次的下一个数，而不是逐步查找。因此，算法的整个部分仅需O（n）。
因此，使用这两个，可以得到O（n log log n）+ O（n）= O（n log logn）算术运算的上限。如果您对位运算进行计数，则由于您要处理的数字最多为n，因此它们大约有log n位，这就是log n的因数，给出了O（n log nlog log n）位运算。
