公數

公數是經由類埃拉托斯特尼篩法篩選之後的一個整數集合，數量無限，最小的是3，由鄭祖扶在公元2012年發現並給予命名。

基本介紹

• 中文名：公數
• 性質：科學
• 類別：數學

釋義

公數是一種經由類埃拉托斯特尼篩法而篩選出來剩餘的整數集合，不同於埃拉托斯特尼篩法的按所有大於1的正整數的倍數篩掉數字（不篩掉第1個），最後篩掉最小的正整數1的倍數（只能篩除1），公數篩選法為按所有大於1的正整數的倍數的位數篩掉數字（全部都篩），最後篩掉最小的正整數1的倍數的位數（只能篩除1），所得到的整數集。

篩選法

公數篩選法為篩除所有正整數的倍數的位數，最後剩餘的數便是公數。

給出正整數集[1，100]

1 2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17 18 19 20

21 22 23 24 25 26 27 28 29 30

31 32 33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 48 49 50

51 52 53 54 55 56 57 58 59 60

61 62 63 64 65 66 67 68 69 70

71 72 73 74 75 76 77 78 79 80

81 82 83 84 85 86 87 88 89 90

91 92 93 94 95 96 97 98 99 100

第一步、按所有整數的位數倍篩選，先篩除2的倍數的位數，得：

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29

31 33 35 37 39 41 43 45 47 49 51 53 55 57 59

61 63 65 67 69 71 73 75 77 79 81 83 85 87 89

91 93 95 97 99

第二步、再篩除3的倍數的位數，得：

1 3 7 9 13 15 19 21 25 27 31 33 37 39 43 45 49

51 55 57 61 63 67 69 73 75 79 81 85 87 91 93 97 99

第三步、再篩除4的倍數的位數，得：

1 3 7 13 15 19 25 27 31 37 39 43 49 51 55 61 63 67 73 75 79 85 87 91 97 99

第四步、再篩除5的倍數的位數，得：

1 3 7 13 19 25 27 31 39 43 49 51 61 63 67 73 79 85 87 91 99

第五步、再篩除6的倍數的位數，得：

1 3 7 13 19 27 31 39 43 49 61 63 67 73 79 87 91 99

第六步、再篩除7的倍數的位數，得：

1 3 7 13 19 27 39 43 49 61 63 67 79 87 91 99

第七步、再篩除8的倍數的位數，得：

1 3 7 13 19 27 39 49 61 63 67 79 87 91 99

第八步、再篩除9的倍數的位數，得：

1 3 7 13 19 27 39 49 63 67 79 87 91 99

第九步、再篩除10的倍數的位數，得：

1 3 7 13 19 27 39 49 63 79 87 91 99

第十步、再篩除11的倍數的位數，得：

1 3 7 13 19 27 39 49 63 79 91 99

第十一步、再篩除12的倍數的位數，得：

1 3 7 13 19 27 39 49 63 79 91

最後一步、再篩除1的倍數的位數，只允許篩除第一個，所以篩除1，得出100以內的公數為：3 7 13 19 27 39 49 63 79 91

算法

公式算法

第一個：（1+1）²÷1=4,4-1=3

第二個：（2+1）²÷2=4.5，[4.5]×2÷1=8,8-1=7

第三個：（3+1）²÷3≈5.3，[5.3]×3÷2=7.5，[7.5]×2÷1=14,14-1=13

以此類推。

易語言算法

.版本 2

.支持庫 shellEx

.程式集 視窗程式集_啟動視窗

.子程式 __啟動視窗_創建完畢

.子程式 __啟動視窗_被激活

熱鍵 = 註冊熱鍵 (_啟動視窗.取視窗句柄 (), 標籤1.取視窗句柄 (), 0, #回車鍵)

.子程式 __啟動視窗_被取消激活

撤銷熱鍵 (_啟動視窗.取視窗句柄 (), 熱鍵)

.子程式 _標籤1_反饋事件, 整數型

.參數 參數一, 整數型

.參數 參數二, 整數型

.如果真 (熱鍵 = 參數一)

_圖形按鈕2_被單擊 ()

.如果真結束

.子程式 _圖形按鈕2_被單擊

.局部變數 所輸入的數字, 長整數型

.局部變數 所輸入數字相應的變數, 長整數型

.局部變數 求得的數字, 雙精度小數型

所輸入的數字 = 到數值 (編輯框1.內容)

所輸入數字相應的變數 = 所輸入的數字 + 1

求得的數字 = 求次方 (所輸入數字相應的變數, 2) ÷ 所輸入的數字

.如果真 (所輸入的數字 > 90568)

信息框 (“您輸入的數字過大，系統將會無法正確計算，請重新輸入！”, 0, , )

所輸入數字相應的變數 = 0

.如果真結束

.如果真 (所輸入的數字 < 1)

編輯框1.內容 = “”

.如果真結束

.如果真 (取整 (求得的數字) = 求得的數字)

求得的數字 = 求得的數字 － 1

.如果真結束

.如果真 (取整 (求得的數字) ≠ 求得的數字)

求得的數字 = 取整 (求得的數字)

.如果真結束

.判斷循環首 (所輸入的數字 ≠ 1)

所輸入的數字 = 所輸入的數字 － 1

所輸入數字相應的變數 = 所輸入的數字 + 1

求得的數字 = 求得的數字 × 所輸入數字相應的變數 ÷ 所輸入的數字

.如果真 (取整 (求得的數字) = 求得的數字)

求得的數字 = 求得的數字 － 1

.如果真結束

.如果真 (取整 (求得的數字) ≠ 求得的數字)

求得的數字 = 取整 (求得的數字)

.如果真結束

.如果真 (編輯框1.內容 = “”)

跳出循環 ()

.如果真結束

處理事件 ()

.判斷循環尾 ()

編輯框2.內容 = 到文本 (求得的數字)

來源

對素數的研究使得希臘數學家埃拉托斯特尼提出了檢定素數的算法。人們對於素數研究的熱情使得埃拉托斯特尼篩法產生各種變種篩法，例如：幸運數等等。

2012年，鄭祖扶在對素數和幸運數的研究當中發現了一種埃拉托斯特尼篩法變種篩出的整數集合，並命名為“公數”。