篩法，是求不超過自然數N（N>1）的所有質數的一種方法。篩法公式就是求不超過自然數N（N>1）的所有質數的公式。
篩法公式可以對埃拉多斯染尼氏（Eratosthenes） 篩法進行計算， 即“篩法計算公式” （它包括計算素數和計算奇合數兩個公式）， 計算素數的公式也可以稱為“素數公式”。給素數找出一個通項表達式， 即已知任一素數後邊緊跟的那個素數的公式。
基本介紹
- 中文名：篩法公式
- 外文名：Sieve formula
- 目的：求不超過自然數N的所有質數
- 領域：數學
- 來源：埃拉多斯染尼氏篩法
- 相關名詞：素數公式
公式介紹,依據和過程,素數普遍公式,
公式介紹
篩法公式可以對埃拉多斯染尼氏（Eratosthenes） 篩法進行計算， 即“篩法計算公式” （它包括計算素數和計算奇合數兩個公式）， 計算素數的公式也可以稱為“素數公式”。給素數找出一個通項表達式， 即已知任一素數後邊緊跟的那個素數的公式。
篩法計算公式：計算素數的公式。
式中mp為1至N數列中素數個數；N 為任意大的自然數；
為素數，其中：p1 = 2，p2 = 3，p3 = 5，p4 = 7......。
計算：應先根據 N 的值（
） 來確定 n 的值，再根據 n 值確定公式的大小 ( 項數)，最後進行計算。計算時將 N 分別乘以括弧內各項， 然後一項一項相除， 除不盡時必須四捨五入取整數， 最後進行加減 ,得出的結果是素數個數。再根據定理確定是否是素數，是第幾個素數和 1 至 N 數列中共多少個素數。這裡的 n 為已知素數序號， mp 為未知 (要計算的） 素數個數，mp= n，當求出mp值後即應以n代表素數序號。
依據和過程
我們知道任何數學公式的發現、推導都離不開該數列自身固有的規律。“先從少數的事例中摸索出規律出發， 再從理論上來證明這一規律的一般性，這是人們認識客觀法則的方法之一” 華羅庚《數學歸納法》。 那么素數序列到底有什麼規律呢? 回答是沒有任何規律。U. 杜德利在《基礎數論》 中寫得清楚： “素數卻如此雜亂無章地散布在整數中，甚至原因也可能說不清楚”。 [德]漢斯. 拉德枚徹、 [德] 托. 托普利茨在合著的《數學欣賞》 中寫到：“較自然的方法是試求任一已知素數後邊緊跟的那個素數。但是由於素數組成的極端的無規則性，所作的這種嘗試最後都失敗了。 ”在素數序列上找不到規律，那么可否從合數序列上去尋找規律呢？ 因為素數與合數是相輔相成、 相互依存的。通過摸索發現合數序列是有規律的，我們可以通過合數的規律來研究、了解素數及其與合數的關係。合數的有規律與素數的無規律好比是篩法的篩子，篩眼的大小我們用已知素數來編是有規律的，而且從篩眼大的到篩眼小的我們可以編 n 種，篩掉的合數是有規律的(根據篩眼的大小知道)，而留在篩子裡的素數是沒有規律的一樣。通過大量事例摸索出三條主要規律：
區段性的規律
合數的規律隨著區段的增加其規律也在變化，在同一區段內合數的規律是一樣的。區段是以前一個素數的平方到後一個素數的平方來劃分。 用符號（ ）表示。 這是合數的最基本的一條規律。這個規律兩千多年前已經被人們發現。
逐項相除四捨五入的規律
在兩數相除時一定要一項一項相除,除不盡時必須而且只能四捨五入取整數。 這是關鍵性的一條規律。
隨從數的規律
（註： “隨從數” 也叫後繼數， 就是緊接在某一個自然數後面的一個數。例如，1的隨從是 2，2的隨從是3， 3的隨從是4等等。）當我們用“奇合數公式”來計算奇合數時，所得出的值是隨從數的，那么這個隨從數必定是奇合數；如果用“素數公式” 來計算素數時，所得出的值是隨從數的，那么這個隨從數必定是素數。這是判斷性的一條規律。上面這三條規律是發現、推導“篩法計算公式” 的重要基礎和依據。兩千多年前埃拉多斯染尼（Eratosthenes） 根據第一條規律發現了篩法，根據第二、 三條規律找到了篩法的計算公式。
就上面三條規律來分析一下合數的規律及其與素數的關係。因為偶數中只有2是素數，其餘都是合數， 為簡便明了， 這裡我們只討論奇數、 奇合數和素數。
從第二個素數 3 的平方 9 起， 是 3 的整倍數的奇數有： 9, 15, 21, 27,……
從第三個素數 5 的平方 25 起， 是 5 的整倍數的奇數有： 25, 35,45, 55,……
從第四個素數 7 的平方 49 起， 是 7 的整倍數的奇數有： 49, 63, 77, 91,……
從上面 3， 5， 7 的整倍數看，我們發現了合數的第一個規律即區段性的規律。每增加一個區段，就要增加計算一個素數的倍數， 我們將增加的這個素數序號， 同時也作為這個區段的區號。
關於篩法公式 的說明
有兩千多年歷史的埃拉多斯染尼氏篩法， 都是篩去(劃掉) 合數，留下素數， 而篩法公式可以：
⑴計算出素數或奇合數；
⑵是第幾個素數或奇合數；
⑶在這個數之前共有多少個素數或者奇合數。
“篩法計算公式” 從理論上講可以對任意大的自然數進行計算。但是，當數字很大時，手工計算起來就不那么容易， 由於該公式比較複雜，當計算一個很大的數如 N（）， 就要進行（
） 項除法運算， 手工計算起來非常繁瑣、費時。 但是， 在計算機高度發達的今天， 將這個公式編製成電腦程式， 在計算機上計算就容易多了。如果編成程式，在計算機上計算就太簡便了。例如， 輸入一個奇數9403， 計算機會在十分鐘左右從1 至9403 按順序、 一個不多、 一個不少、 一個不錯的計算並顯示出9403 以前的所有1163個素數。
1971年到 2008年美國、 英國、 德國的科學家、 計算機專家、 數學愛好者， 他們算出的最大素數分別是：
219937-1；244497-1；2216091-1；2756839-1；224036583-1；225964951-1；237156667-1；243112609-1。
但是他們只知道這幾個數是素數，並不知道是第幾個素數，也不知道在這幾個素數中間還有多少個素數。 如果使用“篩法計算公式” 用對數編制的程式， 就有可能算出這個數以內的全部素數以及(243112609-1) 這個數是第幾個素數。
素數普遍公式
素數普遍公式是公元前250年同樣是古希臘的數學家埃拉托塞尼提出一種篩法。其要求是：
（一）“要得到不大於某個自然數N的所有素數，只要在2---N中將不大於√N的素數的倍數全部划去即可”。
（二）將上面的內容等價轉換：“如果N是合數，則它有一個因子d滿足1<d≤√N”。
（三）再將（二）的內容等價轉換：“若自然數N不能被不大於(根號)√N的任何素數整除，則N是一個素數”。
