complexity-theory - 複雑さの近似に近いエラトステネスのふるい

Question

私はエラトステネスのふるいにもっと正確な近似を与えようとしました。

私が使用した初歩的な操作と重み：

 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））であることがわかりました。

Answer 1

はい、その通りです、O(nloglogn)==O(nloglog(sqrt(n)))：