如何找到與複雜度爲O n個素數（1）

-6

2011-10-10 Harini

用什麼語言？ –

你確定這可能嗎？你甚至無法連續打印第n個素數。 – bmm6o

+10

如果你可以做那個_without_首先找到所有可能的素數，那麼數學上帝希望聽到你的消息。 – Widor

爲O做到這一點的唯一方法（1）將所有質數的數組第n個素數。所以，您只能根據計算機的內存支持某個數字。

編輯：

可能有一些方法來計算這個涉及了一堆演算的，但這已經超出了我:)

2011-10-10 16:43:37

您確定可以在恆定時間內搜索數組內的數字（未定義長度）嗎？不要這樣認爲...：-s –

爲什麼你需要搜索？第n個素數是數組中的第n個索引。這是編譯器的指針遞增。 –

是的。好點子。沒想到這一點。 –

你不能。事實上，如果不進行詳盡的搜索，就無法枚舉素數。

如果你有所有質數數據庫最多ň你可以在o(log n)搜索第n素數（最多ñ）。

2011-10-10 16:44:00

那麼最簡單的方法是找到複雜度最小的第n個素數？ – Harini

-1：事實上，你*可以在沒有詳盡搜索的情況下找到第n個素數。事實上，pi（x）的快速算法允許一種類似於二分搜索的技術。 – Charles

要在固定時間內找到第n個素數將意味着有一個計算pi（n）（返回第n個素數）的合理公式。有關此主題的初步討論，請參閱http://primes.utm.edu/notes/faq/p_n.html。

2011-10-10 16:46:44 lurker

回答