素數公式

在計算機科學中，素數公式是一種算法 f ( n ) ，這樣對于自然數 n? 值 f ( n )? n - 第 一個素數。 在數學，尤其是數論中，這對應于提供大量素數的公式（素數公式）。 到目前為止，還沒有找到更高效的素數公式，尤其是沒有切實可行的生成素數的封閉公式。

但是，有些公式生成的數有一定的概率是素數，所以生成的數還是要檢驗一下是不是素數。 本文還討論了其他不實用但已在數學文獻中討論過它們是否會產生許多素數的公式。

確定素數的最古老的算法之一是埃拉托色尼篩法，在該算法中，這些數字從自然數列表中一個接一個地刪除，這些數字是尚未刪除的最小數的倍數。 這將素數留在初始列表中。

歐拉已經給出了公式 n 2 + n + 17和 n 2 ? n + 41 ，對于 0 ≤ n < 16 或 0 ≤ n <; 41 返回素數。 即使對于更大的 n值，這兩個公式也會返回許多質數，因為結果永遠不會被質數 p <; 17? 或 p 4沒有這樣的素數。

根據狄利克雷素數定理，一個等差數列包含 a ? m + b，無窮多個素數（也包括合數）。對于每個 k都有算術序列，產生 k 連續值的素數。

一個平凡的素數公式可以歸納地定義如下：

• f ( 1 ) = 2
• f ( 2 ) = 3
• 對于 n ≥ 2? 是 f ( n ) 之后的質數，其中f ( n ) + 2 中的所有數字按升序進行素數測試是。

然而，這種方法非常低效，因為所有奇數自然數都必須一個接一個地進行測試。 作為替代方案，建議使用篩分方法，例如埃拉托色尼篩法或阿特金篩法，創建一個足夠長的素數列表，然后遍歷該列表直到達到所需的素數。 這樣做時，有時首先要確定與素數（幾乎是素數）相似的數量。

所有素數的一個不太實用的公式是基于威爾遜定理的。

如果你對單個變量使用自然數，當且僅當不等式滿足時， k + 2 是質數。

還有一個 n 丟番圖方程組，它只用十個變量生成素數（而且只有這些），但次數非常高，人們總能找到這樣一個最多只有四次多項式的系統，但在這種情況下，變量的數量非常多。 到目前為止，這些方法還沒有任何實際用途。