0

我试图对埃拉托色尼筛法给出更精确的近似值。

我使用的基本操作和权重：

 prime[p]         -> 1 operation
 m = p * p        -> 2 operations
 prime[m] = false -> 1 operation
 m = m + p        -> 2 operations

我的证明：

我的证明正确吗？我在文献中发现复杂度是 O(nlog(log(n))) 或 O(nlog(log(n))/log(n))。

4

1 回答 1

2

是的，这是正确的，O(nloglogn)==O(nloglog(sqrt(n)))：

在此处输入图像描述

于 2013-03-26T14:18:26.517 回答