Eratosthenes的篩接近複雜性近似

我試圖給Eratosthenes的篩更精確的近似值。Eratosthenes的篩接近複雜性近似

基本操作和我用的權重：

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））。

2013-03-26 flatronka

經過數對數的操作，你會看到'O（nloglogn）== O（nloglog（開方（N）））'。 – SomeWittyUsername 2013-03-26 10:42:17

你能告訴我嗎？我現在看不到它。 – flatronka 2013-03-26 10:51:02

除此之外，您的證明看起來不正確：1.您的內部循環僅在外部循環的索引被標記爲素數時纔會執行 - 您無視這一事實。 2.我認爲你的（1）和（4），（5）之間沒有任何關係。總和拆分應該看起來完全不同 – SomeWittyUsername 2013-03-26 10:53:48

是的，這是正確的，O(nloglogn)==O(nloglog(sqrt(n)))：

enter image description here

2013-03-26 14:18:26 SomeWittyUsername

感謝您的時間和幫助：D，這是我所期望的完美答案：D。 – flatronka 2013-03-26 14:56:29

回答