-
篩法公式
鎖定
篩法，是求不超過自然數N（N＞1）的所有質數的一種方法。篩法公式就是求不超過自然數N（N>1）的所有質數的公式。
篩選法又稱篩法，具體做法是：先把N個自然數按次序排列起來。1不是質數，也不是合數，要劃去。第二個數2是質數留下來，而把2後面所有能被2整除的數都劃去。2後面第一個沒劃去的數是3，把3留下，再把3後面所有能被3整除的數都劃去。3後面第一個沒劃去的數是5，把5留下，再把5後面所有能被5整除的數都劃去。這樣一直做下去，就會把不超過N的全部合數都篩掉，留下的就是不超過N的全部質數。
質數公式，又稱素數公式，在數學領域中，表示一種能夠僅產生質數（素數）的公式。即是説，這個公式能夠一個不漏地產生所有的質數，並且對每個輸入的值，此公式產生的結果都是質數。由於質數的個數是可數的，因此一般假設輸入的值是自然數集（或整數集及其它可數集）。
迄今為止，人們尚未找到易於計算且符合上述條件的質數公式，但對於質數公式應該具備的性質已經有了大量的瞭解。
- 中文名
- 篩法公式
- 外文名
- Sieve formula
- 目 的
- 求不超過自然數N的所有質數
- 領 域
- 數學
- 來 源
- 埃拉多斯染尼氏篩法
- 相關名詞
- 素數公式
篩法公式簡介
埃拉託斯特尼篩法，簡稱埃氏篩或愛氏篩，是一種由希臘數學家埃拉託斯特尼所提出的一種簡單檢定素數的算法。要得到自然數n以內的全部素數，必須把不大於根號n的所有素數的倍數剔除，剩下的就是素數。
給出要篩數值的範圍n，找出以內的素數。先用2去篩，即把2留下，把2的倍數剔除掉；再用下一個質數，也就是3篩，把3留下，把3的倍數剔除掉；接下去用下一個質數5篩，把5留下，把5的倍數剔除掉；不斷重複下去......。
篩法公式例子
詳細列出算法如下：
列出2以後的所有序列：
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
標出序列中的第一個素數，也就是2，序列變成：
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
將剩下序列中，劃掉2的倍數，序列變成：
2 3 5 7 9 11 13 15 17 19 21 23 25
如果這個序列中最大數小於最後一個標出的素數的平方，那麼剩下的序列中所有的數都是素數，否則回到第二步。
本例中，因為25大於2的平方，我們返回第二步：
剩下的序列中第一個素數是3，將主序列中3的倍數劃掉，主序列變成：
2 3 5 7 11 13 17 19 23 25
我們得到的素數有：2，3
25仍然大於3的平方，所以我們還要返回第二步：
序列中第一個素數是5，同樣將序列中5的倍數劃掉，主序列成了：
2 3 5 7 11 13 17 19 23
我們得到的素數有：2，3，5 。
因為23小於5的平方，跳出循環.
結論：2到25之間的素數是：2 3 5 7 11 13 17 19 23。
- 詞條統計
-
- 瀏覽次數：次
- 編輯次數：20次歷史版本
- 最近更新： 饮不完的杯中九