第四章　質數 (1)　兼談動態連結程式庫

心路歷程

寫個程式還有「心路歷程」？真是見鬼了。但是不騙你們，我真的有些想法。起源是最近寫組合語言的人真的越來越少了，連大陸的 Aogo 彙編小站 ( 大陸稱組合語言為彙編語言 ) 的討論區都冷清的可以，更別說台灣了。甚至還有人說，組合語言已死。雖然有點言過其實，但是大家一定也都同意，組合語言能做得到而高階語言做不到的事，幾乎是沒有了。大家也都同意，高階語言能做得到的，組合語言一定能做得到。那現在組合語言還有什麼優勢呢？或許在複雜的計算過程，還有些許的優勢，不過也可能很快就沒了。

最近幾年 ( 民國 106 年，西元 2017 年左右 )，許多國家都想辦法在中小學裏，把程式設計列為學生學習的項目，我國政府也想推行這政策。但是以小木偶這數十年來的觀察，想要學習程式設計，非得要具有清晰的邏輯以及基本的數學為基礎；但這還不是非常重要的，更重要的是要有堅毅的耐心。前面兩個條件，許多智商高的人，輕而易舉就能做到；但是講到耐心，就不是一般人能做到了。尤其是在歷屆政府的政策「鼓舞」下，希望能減低下一代的壓力，於是造成能夠吃苦耐勞、能有恆心有毅力的年輕人已經越來越少。這種氛圍之下，能推廣程式設計，我看是很難。

好了，發牢騷就此打住。小木偶打算在接下來的幾章內，記錄小木偶撰寫將某一正整數分解成質因數乘積的過程。在這過程內，會用到幾個副程式，例如，求小於某正整數的質數、求一正整數的平方根、判斷一正整數是否為質數等。小木偶覺得它們挺管用的，因此把它們製作成動態連結程式庫 ( dynamic-link library )。因此這一章的標題就變成「質數 (1)　兼談動態連結程式庫」，看似兩個無關的主題，卻合在一起了。

原理

Win64 的動態結程式庫

事實上，在 Win64 系統內，想要製作動態連結程式庫，和在 Win32 系統幾乎一樣。動態連結程式庫可以看成是一些副程式的集合或是某些資源的集合。這些副程式或是資源，都是被其他程式所呼叫或使用，所以不需要建立視窗，也不需要訊息迴圈或終結視窗的程式碼。每個動態連結程式庫的格式都固定的，底下就先來看看動態連結程式庫的樣子：

OPTION CASEMAP:NONE

OPTION WIN64:7

;假如需要用到包含檔，那麼可以在此處定義

INCLUDE WINDOWS.INC

INCLUDELIB KERNEL32.LIB

;*****************************************************************************************

.DATA?

;此處定義未初始化的變數

;*****************************************************************************************

.CODE

;-----------------------------------------------------------------------------------------

;進入／離開副程式的進入點

DLLEntry PROC hInstance,dwReason,dwReserved

mov rax,dwReason

.IF rax==DLL_PROCESS_ATTACH

;保存hInstance

;初始化動態連結程式庫需要的各種資源

.IF ;初始化成功

mov rax,TRUE

.ELSE

mov rax,FALSE

.ENDIF

.ELSEIF rax==DLL_THREAD_ATTACH

;釋放動態連結程式庫使用的資源

.ELSEIF rax==DLL_THREAD_DETACH

;為新的執行緒分配資源

.ELSEIF rax==DLL_PROCESS_DETACH

;為執行緒釋放資源

.ENDIF

DLLEntry ENDP

;進入／離開副程式結束

;-----------------------------------------------------------------------------------------

SubRoutine1 PROC Param1,Param2 ;此處為第一個副程式的參數

;此處為第一個副程式的程式碼

ret

SubRoutine1 ENDP

;-----------------------------------------------------------------------------------------

SubRoutine2 PROC ParamA,ParamB ;此處為第二個副程式的參數

;此處為第二個副程式的程式碼

ret

SubRoutine2 ENDP

;*****************************************************************************************

END DLLEntry

上面的動態連結程式庫模板，是由一個稱為 DLLEntry 副程式及兩個副程式組成，DLLEntry 副程式稱為「進入／離開副程式」，每個動態連結程式庫都會有這個副程式，它的名稱其實可以任意訂定，只要符合組譯器的命名規則即可。雖然「進入／離開副程式」也叫副程式，但是並不像其他副程式一樣是讓其他程式呼叫的，而是作業系統載入或卸載動態連結程式庫時，由作業系統呼叫，讓作業系統有機會做一些事前處理或是離開時作一些清除動作用的。「進入／離開副程式」有固定的格式執行一些動作，假如不需要做這些動作的話，「進入／離開副程式」也可以只是把 1 存入 RAX 裏，然後把 1 當成返回值就跳離。

質數表

要把所有質數列出來成一張表，這是不可能的。早在西元前三百多年，古希臘數學家歐幾里德就已經證明了「有無限多個質數」( 見昌爸工作坊 )。既然建立無法有無限多個的質數表格，只能退而求其次，只要能建立小於某個正整數的質數即可。而 64 位元的 CPU，所能表示的正整數最大為 2⁶⁴－1，所以小木偶就想寫出一副程式，能列出小於 2⁶⁴－1 的所有質數。( 各位看倌，乍看之下，會以為這個數不大，但實際算過後得知，2⁶⁴－1＝18446744073709551615≒1.8447×10¹⁹，其實是很大的數，共有 20 位數。)

在網路上查詢可以知道，有許多方法能計算質數表，小木偶使用 Eratosthenes 篩選法。這個方法的原理很簡單，底下簡述這種方法。假設想要列出小於 N 的質數，可以先由 2 開始把小於 N 的正整數一一列出，然後把 2 的倍數刪去。之後再由 2 開始找到第一個沒被刪去的數，3，即為質數，再把 3 的倍數刪去。刪去之後再由 3 開始，找到第一個沒被刪去的數，5，這就是下一個質數，再刪去 5 的倍數。然後由 5 開始，找到下一個沒被刪去的數，7，7 就是下個質數……如此循環不已，直到 N 為止。結果如下圖：

Eratosthenes 篩選法

如果用 Eratosthenes 篩選法當成演算法，寫成電腦程式來列出質數的步驟，大致就是：①先配置 N 個元素的陣列。②設一個兩層的迴圈，第一層迴圈由 2 開始，到 N 結束，每一次都先檢查此數是否已被刪除，如果刪除，就不進入第二層迴圈，直接跳到第一層迴圈的下一個數繼續。如果沒被刪除，表示此數為質數，然後進入第二層迴圈。③第二層迴圈由該數開始，直到 N 結束，主要目的是檢查輪到的數是否為該數的倍數，如果是則刪除。④結束。

Eratosthenes 篩選法的原理雖然簡單，但是如果 N 很大時，缺點就會顯現出來，那就是：

要花費大量記憶體。如果你要求 1000 以內的質數，需要先配置 1KB 的記憶體，大概不致有什麼問題；但是如果是要求一億以內的質數，就得需要 100MB 的記憶體。
速度太慢。以一億為例，刪去 2 的倍數時，要重複迴圈五千萬次，刪去 3 的倍數時要重複三千三百萬次…，其實是很沒有效率的。

因此有以下的改進方法。

改進建立質數表的方法

底下說明建立質數表時，如何增進速度。因為底下的說明，太過於瑣碎，需配合原始碼，相互閱讀，大約才能了解。

①以一個位元代表一個奇數

用組合語言，就能彌補第一個缺點，因為組合語言很擅長處理位元，因此小木偶改用以一位元代替一個數，而不是用一個位元組表示一個數。另外，偶數中就只有 2 是質數，故乾脆額外處理 2，然後把偶數全部刪去，這樣的話一個位元組就能代表 16 個數了。也就是說，第零個位元組的第零位元代表 3、第一位元代表 5、第二位元代表 7、第三位元代表 9…，見下圖最底下一行的白色字。因此如果是第 P 個位元組的第 Q 個位元，所代表的數可以輕易算出是「16P＋2Q＋3」，當然 P、Q 均從 0 開始，Q 必須是 0 到 7 的整數。例如，第 3 個位元組的第 4 個位元，代表 59。反過來，如果要求某個奇數，X，在第幾個位元組 ( 以 P 表示 ) 裏面的第幾個位元 ( 以 Q 表示 )，可以經由下面步驟算出：

　　P＝( X－3 )÷16 的商數
　　Q＝( X－3 )÷16 的餘數，再除以 2

配置記憶體時，一般是呼叫 GlobalAlloc，可以用 GPTR 參數使所配置的記憶體內容均設為 0。因此小木偶設定：若某個位元為 0，表示此位元所代表的數為質數；若某個位元為 1，表示此位元所代表的數不是質數。一開始，先假定所有的數均為質數，故每個位元都為 0，但如果某數是 2 的倍數，或其他數的倍數，表示此數可以被該數整除，就不是質數，應將此位元設為 1。例如 15 可被 3 整除，不是質數，該位元應設為一。不過 2 已經刪除，所以從 3 開始。參考下圖，您應該可以發現，距離 3 往右三個位元處的 9 是 3 的倍數，此位元應該設為一；再往右三個位元的 15 也是 3 的倍數，此位元也應設為一……。如果事先把這些位元設為一，表示刪除的話，將來就可以減少許多計算。

既然如此，何不一開始就乾脆連 5 和 7 的倍數，也先刪除。也就是說，在配置記憶體之後，就先把 3、5、7 的倍數所代表的位元設為 1，這樣就可以減少更多計算。參考下圖，您會可以發現，刪除 5 的倍數時，是五個一數，該位元就是代表 5 的倍數；刪除 7 的倍數時，是七個一數，該位元就是代表 7 的倍數。當然，在刪除 5 倍數時，有些可能在刪除 3 的倍數時，就已經刪去了，例如 15；同樣的事，也發生在刪除 7 的倍數時。綜合上述結果，第零～四個位元組的數值分別是 48H、9AH、0A5H、0CDH、0B2h，如下圖所示。

如果想要在計算前，事先刪除 3、5、7 的倍數，再加上每 8 個數組成一個位元組，至少需要 3×5×7×8 個位元，恰好是 105 個位元組。意思是，每 105 個位元組會重複出現。因此可以先定義這 105 個位元組的資料，然後在配置記憶體之後，把這 105 個位元組的資料，以組合語言 REP MOVSB 指令，重複的填入配置完成的記憶體內，就立刻刪除了 2、3、5、7 的倍數。但是，要注意的是，第零個位元組並不會重複，因為代表 3、5、7 的位元沒被刪除，此三位元為 0，是質數。而其後的 3 個位元組，會在 105 個位元組之後重複出現。小木偶以筆算花了一些時間得到結果，後來想想筆算很可能算錯，後來還是寫了個程式做這件事。最後這 105 個位元組是可查閱這裏。

②刪去質數的倍數時，從該質數的平方開始刪除

除了上面的方法之外，還有幾個方法可以減少計算次數。首先，找到某個質數後，要刪去該質數的倍數時，可以從該質數的平方開始刪除，因為前面的倍數都已經刪去。例如要刪去 11 的倍數時，3×11、5×11、9×11 必定都已經在刪除 3、5 的倍數時刪去了，所以從 11×11 開始刪除即可。那麼，要怎麼找到質數的平方呢？如果您仔細觀察上圖，會發現：

3² 所代表的位元，距離 3 有  3 個位元遠。 3 可以寫成 1×3
5² 所代表的位元，距離 5 有 10 個位元遠。10 可以寫成 2×5
7² 所代表的位元，距離 7 有 21 個位元遠。21 可以寫成 3×7
9² 所代表的位元，距離 9 有 36 個位元遠。36 可以寫成 4×9

從前面幾個質數的平方，就能看出來一些規律。質數的平方距離該質數，有 ( n×質數 ) 個位元那麼遠，n 是從一開始的正整數，它代表由三開始的第幾個奇數。或者換一方式思考，我們可以把所配置的記憶體，看成由 0 開始到 100 或 1000 或 10000 個位元所組成的，並想成使位元組的界限消失，亦即不使八個位元變成一個位元組。第零個位元就代表 3，第一個位元就代表 5……第八個位元代表 19，第九個位元代表 21……那麼，n 就是所配置的記憶體中的第幾個位元再加一。R11 暫存器，就代表這個數值，在原始碼的第 153 行就定義了 R11 從 4 開始，而第 154～160 行，就是計算出從某個質數開始，到質數的平方有多少個位元。

③以加法代替乘法，刪除質數的倍數

每個質數的倍數距離下一個倍數，有多少位元？您也可以從上圖觀察。：

3 距離  9 有 3 個位元，15 距離  9 有 3 個位元，21 距離 15 有 3 個位元……
5 距離 15 有 5 個位元，15 距離 25 有 5 個位元，25 距離 35 有 5 個位元……
7 距離 21 有 7 個位元，21 距離 35 有 7 個位元，35 距離 49 有 7 個位元……

換句話說，質數的倍數距離下一個倍數的位元數，距離和質數大小一樣。意思是，我們可以以加法累進刪除質數的倍數，而不用乘法，因為乘法速率較加法慢。在原始碼的第 167 行就已計算完成，每個倍數距離下一個倍數的位元數，記錄在 R8:R9 裏。因為記憶體中，仍以位元組內的第幾個位元表示，所以程式裏 R8:R9 的意思，質數的倍數距離下一個倍數有 R8 個位元組再加上 R9 位元這麼遠。

④篩選到根號 N 就可以了

還有一個可以加快 Eratosthenes 篩選法的方法。如果想要把小於 N 的質數列出來，以 Eratosthenes 篩選法篩選，只要篩選到就可以了。例如要列出 100 以下的質數，只要篩選掉 10 以下的質數倍數就可以了。在刪除 2 的倍數時，必定會刪除 2×11、2×13、2×17…；在刪除 3 的倍數時，也會刪除 3×11、3×13、3×17…；而且兩個都大於 10 的數相乘所得的乘積一定超過 100，例如 11×11＝121。綜觀上面的理由，就可得知，只需刪除到就可以了。

一數的平方根可以用 FPU 指令，FSQRT 計算，但是這個指令只能計算小於 9223372036854775807 ( ＝2⁶³－1 ) 的平方根，超過這個數，只好用牛頓法求到整數位。有關牛頓法求一數之平方根，可以參考大陸博客園的「一個 Sqrt 函數引發的血案」文章。小木偶已經撰寫好一個副程式，square_root，可供呼叫。以 square_root 計算使用者所輸入數值的平方根，並將其轉變成 SqrtByte 及 SqrtBit。這兩個變數，分別代表所輸入數值的平方根，在所配置記憶體的第 SqrtByte 位元組的第 SqrtBit 位元 ( 見程式碼第 107～119 行 )。在程式碼的第 153 行，設定 R11 為四，就是開始刪除 11 的倍數，11 的倍數刪完，就輪到 13 的倍數，13 的倍數刪完，就輪到 17 的倍數……直到第 188～191 行，就是檢查是否已經刪除到了。

判斷一正整數是否為質數

既已計算出質數列表，要判斷某個正整數是否為質數，就不是件難事了。只要以該正整數當做被除數，把小於該正整數的質數當做除數，做除法運算，如能整除，那麼該正整數就不是質數；如果所有小於該正整數的質數，都不能整除該正整數，那麼這個正整數就是質數。不過為了加速，可以不需要把所有質數列出來，才做除法運算。小木偶的做法是，只要一找到質數，就立刻相除。這樣就會使速率變快很多。因為只需判斷是否為質數即可，另外也可指出是哪一個質數能整除該正整數。

原始碼

講了這麼多，這一章要製作三個副程式：square_root、find_prime、is_prime，其功用分別是求出某數的平方根、求出小於或等於某正整數的所有質數、判斷某正整數是否為質數。小木偶想，或許可以把這三個副程式，包裝成一個動態連結程式庫 ( DLL )，名稱為「PRIMEDLL.ASM」。而第一個副程式，square_root，較為簡單所以不特別說明。

小於或等於某正整數的質數列表：find_prime

副程式，find_prime，是用來列出所有小於某個正整數的質數，其原型為：

find_prime  PROTO   num:QWORD,pMemPrm:LPSTR

它有兩個參數，num、pMemPrm。第一個參數，num，為正整數，傳給 find_prime 副程式，使之計算小於或等於 num 的質數。而其結果存於第二個參數，pMemPrm，所指的記憶體區塊裏。這塊記憶體，必須由主程式配置好，並將其位址，pMemPrm，傳給 find_prime。pMemPrm 所指的記憶體區塊長度與 num 之值有關，為個位元組，並且一開始，每個位元組都應該是 0，因此如果是呼叫 GlobalAlloc 來建立 pMemPrm 記憶體區塊，應使用 GPTR 參數。

判斷某正整數是否為質數：is_prime

副程式，is_prime，的原型是

is_prime    PROTO   num:QWORD

她只有一個參數，num，num 為正整數。is_prime 會計算 num 是否為質數，返回時，若 RAX＝0，表示 num 為 0 或 1；若 RAX＝1，表示 num 為質數；若 RAX 為其他數，表示 num 不是質數，而 RAX 為其最小之質因數。

原始碼

底下是 PRIMEDLL.ASM 的原始碼：

;此程式只包含三個副程式，為64位元版本

;1.square_root求某數平方根

;2.find_prime：於記憶體中，列出小於或等於某正整數的質數。

;3.is_prime：判斷某正整數是否為質數

OPTION CASEMAP:NONE

OPTION WIN64:7

INCLUDELIB KERNEL32.LIB

GlobalAlloc PROTO :QWORD,:QWORD

GlobalFree PROTO :QWORD

;*****************************************************************************************

.CODE

;-----------------------------------------------------------------------------------------

DLLEntry PROC hInstance,dwReason,dwReserved

mov rax,1

ret

DLLEntry ENDP

;-----------------------------------------------------------------------------------------

;求num的平方根，把平方根的整數部份存於RAX後返回。若num≦7fffffffffffffffh，用NDP(FPU)運

;算；若超過，NDP無法處理改用牛頓法計算(程式碼位於big_number到sqrt_root_ok之間)

;呼叫前後不變的暫存器：R9～R15、RBX、RSI、RDI

;輸入：num－求num之平方根，num為無號數

;輸出：RAX＝根號num之整數部分

square_root PROC num:QWORD

mov rdx,7fffffffffffffffh

cmp rcx,rdx

ja big_number

finit

fild num

fsqrt

fistp num

mov rax,num

jmp sqrt_root_ok

big_number: mov r8,3719550786 ;xn＝3719550786

next_time: sub rdx,rdx

mov rax,num

div r8

add rax,r8

shr rax,1

cmp rax,r8

je sqrt_root_ok

mov r8,rax

jmp next_time

sqrt_root_ok: ret

square_root ENDP

;-----------------------------------------------------------------------------------------

;find_prime副程式用來搜尋小於或等於正整數num的所有質數，返回時把結果記錄在pMemPrm所指的位

;址。pMemPrm所指記憶體區塊，由父程式配置，長度為(num/16+20h)位元組。(因為偶數不須佔用位元

;，且每個數佔用一位元，故8個奇數佔用一個元組，故除以16)。

;呼叫前後，不變的暫存器：R12～R15、RBX、RSI、RDI

;輸入：num－一正整數，find_prime會計算小於此正整數的所有質數

;　　　pMemPrm－記憶體區塊位址，其內容應全為0，find_prime計算後，若某一位元為0，表示該位元

;　　　　　　　　所代表的數為質數；若某位元為1，該位元所代表的數不是質數。第P位元組的第Q個

;　　　　　　　　位元，所代表的數＝16P＋2Q＋3，P由0開始，0≦Q≦7。

;輸出：RAX－小於或等於正整數num的質數個數

find_prime PROC USES rsi rdi num:QWORD,pMemPrm:QWORD

LOCAL MaxByte:QWORD,MaxBit:QWORD ;最大位元數

LOCAL SqrtByte:QWORD,SqrtBit:QWORD ;num的平方根在第幾個位元組內的第幾

;使用技巧： ;個位元

;1.pMemPrm所指的記憶體區塊內的每個位元代表一個奇數，亦即已刪除2的倍數

;2.在標號again:處及其後數行，載入一個105位元組的字串，就能刪除3、5、7的倍數

;3.由pMemPrm所指之記憶體區塊開始，看哪個位元為0，即為質數；1為合數

;4.第零個位元組的第零、一、二位元分別代表3、5、7，第三個位元是9，在此副程式的前幾行程式碼就

;　已被刪除，故從第四個位元開始，此位元代表11，開始刪除11的倍數。

;5.但是刪除時，3*11、5*11、7*11、9*11都已經刪除過了，換句話說只要從11*11始就可以了。質言之

; ，每次找到質數p，要刪除p的倍數時，只需從p的平方開始刪去即可，直至num為止

;6.質數11的倍數刪除後，再搜尋下一個是0的位元，該位元所代表的數為質數，再從該質數的平方刪去

;　該質數的倍數

;7.重複步驟6，一直到num的平方根為止，即可找到小於num的質數

mov rdi,rdx

mov al,48h

stosb

.IF rcx<=1

xor rax,rax ;使用者輸入0、1

.ELSEIF rcx==2

mov rax,1 ;使用者輸入2

.ELSEIF rcx<=4

mov rax,2 ;使用者輸入3、4

.ELSEIF rcx<=6

mov rax,3 ;使用者輸入5、6

.ELSEIF rcx<=10

mov rax,4 ;使用者輸入7、8、9、10

.ELSE

jmp over_10

.ENDIF

jmp exit_fp

;刪除3、5、7的倍數，所需的資料。共105個位元組。從第一個位元組開始，第0個位元組是48h，沒列入

multiple_of_357 DB 09ah,0a5h,0cdh,0b2h,076h,049h,0b7h,0a6h,0d9h,0d2h,02ch,079h,09eh

DB 034h,04bh,09bh,065h,0edh,092h,06eh,04dh,0b3h,0a5h,059h,0f2h,03ch

DB 069h,096h,036h,0cbh,0dah,025h,0ddh,09ah,066h,04bh,0b3h,0e4h,079h

DB 0d2h,02ch,06dh,096h,0b5h,04bh,0bah,035h,0cdh,096h,066h,0c9h,0f3h

DB 0a4h,059h,0dah,02ch,06bh,097h,074h,06bh,09ah,02dh,0cdh,092h,0e7h

DB 049h,0b3h,0b4h,059h,0d6h,02eh,0e9h,0d6h,034h,05bh,09ah,025h,0cfh

DB 093h,066h,069h,0b3h,0ach,05dh,0d2h,0adh,069h,0b6h,034h,04bh,09eh

DB 027h,0cdh,0d2h,066h,059h,0bbh,0a4h,05bh,0d3h,06ch,069h,096h,03ch

DB 04fh

;下表是用來計算某個位元組內，共有幾個位元是零，例如第0筆資料是8，即數值是0的位元組有8個0

;；第一筆資料是7，即數值是1的位元組有7個0；第二筆資料是7，即數值是2的位元組有7個0

tbl_of_no_of_0 DB 8,7,7,6,7,6,6,5,7,6,6,5,6,5,5,4,7,6,6,5,6,5,5,4,6,5,5,4,5,4,4,3

DB 7,6,6,5,6,5,5,4,6,5,5,4,5,4,4,3,6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2

DB 6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2,5,4,4,3,4,3,3,2,4,3,3,2,3,2,2,1

DB 7,6,6,5,6,5,5,4,6,5,5,4,5,4,4,3,6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2

DB 6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2,5,4,4,3,4,3,3,2,4,3,3,2,3,2,2,1

DB 5,4,4,3,4,3,3,2,4,3,3,2,3,2,2,1,4,3,3,2,3,2,2,1,3,2,2,1,2,1,1,0

over_10: INVOKE square_root,rcx

;根號num在pMemPrm所指記憶體的第SqrtByte個位元組的第SqrtBit個位元，以

;SqrtByte:SqrtBit記錄之

test rax,1 ;RAX＝num的平方根

jnz odd_0

dec rax ;若為num之平方根為偶數，減一使成奇數

odd_0: sub rdx,rdx ;SqrtByte＝(RAX-3)/16之商

sub rax,3 ;SqrtBit＝(RAX-3)/16之餘數再除以2

mov r8,16

div r8

mov SqrtByte,rax

shr rdx,1

mov SqrtBit,rdx

;算出pMemPrm所指的記憶體區塊，最多到MaxByte個位元組內的第MaxBit個位元

mov rax,rcx

test rcx,1

jnz odd_1

dec rax ;使用者輸入偶數，因此最後的偶數不用計算

odd_1: shr rax,1 ;除去偶數

xor rdx,rdx

mov r8,8

div r8

mov MaxByte,rax

mov MaxBit,rdx ;最後一個位元是第MaxByte位元組的第MaxBit位元

;刪除3、5、7的倍數，方法是把multiple_of_357字串共105個位元組，填入pMemPrm所指的記憶體裏

xor rdx,rdx

mov r11,105

div r11

mov r9,rax

or rax,rax

jz remain

again: mov rcx,r11

lea rsi,multiple_of_357

rep movsb

dec r9

jnz again

remain: mov rcx,rdx

lea rsi,multiple_of_357

rep movsb

;在hMemPrm記憶體區塊裏，每個位元代表一個奇數，從第0個位元組的第2個位元開始搜尋，

;第一個找到的位元為0的表示此為質數，將其倍數刪去，然後再找到下一個位元為零的，就

;是質數…依此程序，直到最後一個位元

mov rdi,pMemPrm

mov rsi,MaxByte

;把pMemPrm記憶體區塊的位元組、位元界限消失，看成連續位元，R11＝第幾個位元，從0開

;始到(num-1)

mov r11,4 ;R11＝4，表示數值11，數值＝2*R11+3

find_a_prime: mov rax,r11

mov r8,r11

shl rax,1

inc r8

add rax,3

mov r9,rax ;RAX＝R9＝找到的質數

mul r8 ;RAX＝質數的平方所代表的位元距離該質數有多少個位元＝(R11+1)*RAX

add rax,r11

mov r8,r9

mov rcx,rax

and rcx,7 ;從質數的平方開始，刪去質數的倍數。

and r9,7 ;質數的平方在第RAX:RCX處，每次增加R8:R9

shr rax,3

shr r8,3

next_multiple: cmp rax,rsi ;刪去之前，先檢查RAX:RCX是否超過MaxByte:MaxBit

jb set_bit_on ;若沒有超過，跳到set_bit_on

ja next_number

cmp rcx,MaxBit

ja next_number

set_bit_on: mov r10b,1

shl r10b,cl

or [rdi+rax],r10b

add rcx,r9

add rax,r8

cmp rcx,7

jbe next_multiple

inc rax

sub rcx,8

jmp next_multiple

next_number: inc r11 ;已經刪除該質數的倍數，檢查下一個位元所代表的數是否為質數

mov r10,r11 ;下一個數就是使R11增加一，也就是在pMemPrm所指的記憶體區塊

mov rcx,r11 ;的第R11位元須把這個記憶體區塊視為連續的位元組成，使位元

shr r10,3 ;組的界限消失，而第R11個位元是在第R10個位元組裏的第RCX位元

and rcx,7

cmp r10,SqrtByte ;在檢查下一位元前，先檢查是否超過SqrtByte:SqrtBit

jbe lt_max ;如果超過，表示已經刪除了所有小於根號num所有質數之

cmp rcx,SqrtBit ;倍數，跳至get_no_of_prm處

jae get_no_of_prm

lt_max: mov al,1

shl al,cl

test [rdi+r10],al ;檢查下個位元，如果為0，表示下一位元所代表的數為質

jnz next_number ;數，跳躍至find_a_prime處；否則表示不是質數，就

jmp find_a_prime ;跳到next_number

;已經檢查到num平方根，表示在pMemPrm所指的記憶體區塊，長MaxByte個位元組內的位元為0者為

;質數。底下是計算小於或等於num的質數共有多少個

get_no_of_prm: mov r10,OFFSET tbl_of_no_of_0

mov r8,0

mov rax,1 ;第一個質數不在pMemPrm所指的記憶體內，故由1開始

;計算在pMemPrm所指記憶體內的每一個位元組共有幾個位元為0，並且將其總加起來

next_8_bits: cmp r8,MaxByte

jae less_1_byte

movzx r9,BYTE PTR [rdi+r8]

movzx rsi,BYTE PTR [r10+r9]

add rax,rsi

inc r8

jmp next_8_bits

;計算完整的位元組後還剩幾個位元，計算位元為0的個數

less_1_byte: mov dl,[rdi+r8]

mov rcx,MaxBit

jrcxz exit_fp

@@: shr dl,1

jc nxt_bit

inc rax

nxt_bit: loop @b

exit_fp: ret

find_prime ENDP

;-----------------------------------------------------------------------------------------

;判斷num是否為質數

;呼叫前後不變的暫存器：R12～R15、RBX、RSI、RDI

;輸入：num－判斷num是否為質數，num必須小於18446744073709551616(＝2^64)

;返回值：RAX＝0，表示num為0或1

;　　　　RAX＝1，表示num為質數

;　　　　RAX＝其他數，表示num不是質數，且RAX為其最小之質因數

is_prime PROC USES r12 r13 rsi rdi num:QWORD

LOCAL sqrt_n:QWORD ;√n

LOCAL hMem:QWORD

or rcx,rcx

je num_is_1_or_0

cmp rcx,1

jne chk_2_3_5

num_is_1_or_0: xor rax,rax

jmp quit

three_five DB 9ah,25h,0cdh,92h,66h,49h,0b3h,0a4h,59h,0d2h,2ch,69h,96h,34h,04bh

;檢查RCX是否為2、3、5，如果是的話，返回時，RAX＝1

chk_2_3_5: cmp rcx,2

je num_is_235

cmp rcx,3

je num_is_235

cmp rcx,5

jne chk_even

num_is_235: mov rax,1

jmp quit

;檢查RCX是否為偶數，如果是的話，返回時，RAX＝2

chk_even: test rcx,1

jnz odd_number0

mov rax,2

jmp quit

;檢查num是否為3或5的倍數

odd_number0: mov rax,num

mov rcx,3

xor rdx,rdx

div rcx

or rdx,rdx

jnz chk_5

mov rax,rcx

jmp quit

chk_5: mov rax,num

mov rcx,5

xor rdx,rdx

div rcx

mov rax,rcx

or rdx,rdx

jz quit

INVOKE square_root,num

test rax,1

jnz odd_number1

inc rax

odd_number1: mov sqrt_n,rax

mov rdx,rax

;底下要配置記憶體，每個奇數佔用一位元，偶數不必佔用空間，因此每個位元組可容納8個奇

;數，而奇、偶數相隔，所以要計算到數值大小為RDX，只要配置RDX/16個位元組，為求保險，

;再多20h個位元組

shr rdx,4

add rdx,20h

and rdx,0fffffffffffffff0h

INVOKE GlobalAlloc,40h,rdx ;GPTR＝40h

mov hMem,rax

;計算最後一個位元在hMem後的第R10(從第0個位元組開始)個位元組裡面的第R11個位元

mov r10,sqrt_n

test r10,1

jnz odd_number2

dec r10

odd_number2: mov r11,r10

shr r10,4

sub r11,3

mov rdi,rax

and r11,0fh

shr r11,1

;第一個位元組的第0、1、2、3、4、5、6、7分別代表3、5、7、9、11、13、15、17，計算完

;成後，若某位元為1，表示合數；若某位元為0，表示質數。因此計算完成後，第一個位元組

;是的第0位元到第7位元分別是0、0、0、1、0、0、1、0，亦即48h。

mov al,48h

stosb

mov rdx,r10

;把3、5的倍數所代表的位元設為1

next_15bytes: mov rcx,15

lea rsi,three_five

rep movsb

sub rdx,15

jg next_15bytes

;檢查hMem裏的每一位元，若為1，表示非質數，再檢查下一位元；若為0，表示質數，先檢查

;n是否能被該質數整除，如果能的話，則使RAX＝該質數，並跳出此副程式，如果不能整除，

;則使該質數的所有倍數所代表的位元變為1，再檢查下一位元

mov rsi,hMem

mov r8,0 ;以R8:RCX指向hMem裏的每個位元

mov rcx,2 ;從質數7開始檢查，R8:RCX＝0:2，表示7

next_bit: cmp r8,r10 ;先檢查是否超過sqrt_n，R10:R11＝sqrt_n在第R10個位元組裏的

jb not_max ;第R11個位元

ja n_is_prime

cmp rcx,r11

ja n_is_prime

not_max: mov al,1

shl al,cl

test [r8+rsi],al

jz a_prime

inc rcx ;此位元代表的數並非質數，跳到下一數

cmp rcx,8 ;檢查是否已經到下一個位元組

jne next_bit

xor rcx,rcx

inc r8

jmp next_bit

;R8:RCX所代表的數為新找著的質數，先試驗是否能整除num，然後再刪除該質數的倍數

a_prime: mov r9,r8

shl r9,4

mov rdx,rcx

add r9,3

shl rdx,1

add r9,rdx ;R9＝16R8＋2RCX＋3＝質數

mov rax,num

xor rdx,rdx

div r9

or rdx,rdx

jnz indivisibility ;indivisibility是除不盡的意思

push r9 ;num能被找到的質數，R9整除

INVOKE GlobalFree,hMem

pop rax

jmp quit

;num不能被找著的質數整除，要從該質數的平方處開始，刪除該質數的倍數。

indivisibility: mov rax,r9

dec rax

xor rdx,rdx

shr rax,1

mul r9 ;該質數的平方，距離該質數(R8:RCX所指的位元)有RAX個位元

mov rdx,rax ;RAX＝質數×(質數－1)/2

and rax,7

shr rdx,3

add rax,rcx

add rdx,r8

push rcx ;RCX為指向hMem裏的每個位元，在前面以R8:RCX表示，因此

cmp rax,7 ;必須保存起來

jbe start_to_del

sub rax,8

inc rdx

start_to_del: mov r13,r9 ;計算R12:R13，R12:R13是每次增加的質數所代表的位元組數

mov r12,r9 ;及位元數

mov rcx,rax

shr r12,3

and r13,7 ;從RDX:RCX開始，每次增加R12:R13，直到R10:R11

chk_over: cmp rdx,r10 ;檢查是否超過R10:R11

jb chk_not_over

ja set_1_over

cmp rcx,r11

ja set_1_over

chk_not_over: mov al,1 ;如果沒有超過R10:R11，把每個質數的倍數所代表的位元設為1

shl al,cl

or [rsi+rdx],al

add rcx,r13

add rdx,r12

cmp rcx,8

jb chk_over

inc rdx

sub rcx,8

jmp chk_over

set_1_over: pop rcx ;已把所有質數倍數所代表的位元設為1，要搜尋下一個質數

inc rcx

cmp rcx,8

jb next_bit

sub rcx,8

inc r8

jmp next_bit

n_is_prime: INVOKE GlobalFree,hMem

mov rax,1

quit: ret

is_prime ENDP

;*****************************************************************************************

END DLLEntry

PRIMEDLL.DEF 的內容是：

EXPORTS

square_root

find_prime

is_prime

組譯與連結

在「命令提示字元」裏，依下面方法組譯及連結：

E:\HomePage\SOURCE\Win64\PRIME>uasm64 -win64 PRIMEDLL.ASM [Enter]
UASM v2.46, Jan  8 2018, Masm-compatible assembler.
Portions Copyright (c) 1992-2002 Sybase, Inc. All Rights Reserved.
Source code is available under the Sybase Open Watcom Public License.

PRIMEDLL.ASM: 386 lines, 3 passes, 26 ms, 0 warnings, 0 errors

E:\HomePage\SOURCE\Win64\PRIME>link /DLL /DEF:PRIMEDLL.DEF PRIMEDLL.OBJ [Enter]
Microsoft (R) Incremental Linker Version 9.00.21022.08
Copyright (C) Microsoft Corporation.  All rights reserved.

/SUBSYSTEM:WINDOWS /DEBUG
   Creating library PRIMEDLL.lib and object PRIMEDLL.exp

E:\HomePage\SOURCE\Win64\PRIME>

補充解說

在 find_prime 裏，計算質數個數

在 PRIMEDLL.ASM 的第 199～217 行。而在 tbl_of_no_of_0 處，定義了 256 各位元組所組成的陣列，如下面：

tbl_of_no_of_0  DB      8,7,7,6,7,6,6,5,7,6,6,5,6,5,5,4,7,6,6,5,6,5,5,4,6,5,5,4,5,4,4,3
                DB      7,6,6,5,6,5,5,4,6,5,5,4,5,4,4,3,6,5,5,4,5,4,4,3,5,4,4,3,4,3,3,2
                ……

從 0 到 255 每個數都可以以 8 個位元表示，您也能說 8 個位元可以表示 0～255 共 256 個整數。而這 8 個位元有幾個位元是 0？有幾個位元是 1？可以參照上面的 tbl_of_no_of_0 陣列。例如第 0 個位元組代表 0，有 8 個位元是 0；第一個位元組代表數值 1，有 7 個位元是 0；第二個位元組代表數值 2，有 7 個位元是 0…。所以在第 199～217 行就是以查表的方式，去計算每 16 個奇數裏，共有幾個位元是 0，就代表有幾個質數，然後全部累加起來，最後記錄在 RAX 裏。

因為第一個質數是 2，不在 hMemPrm 所指的記憶體區塊中，因此 RAX 由 1 開始。如果 num＜10 的話，已在第 73～81 行處理了，所以可大膽的設定 RAX 由 1 開始。

副程式內用到的資料

有些資料，只有在副程式裏會用到，其他地方用不著。例如 tbl_of_no_of_0 陣列、multiple_of_357 陣列，都只在 find_prime 裏使用，其他地方都不會用到這兩陣列的資料。像這時候，如果要把副程式封裝起來，就可以像上面的寫法，在無條件跳躍指令之後，定義這些資料，不過這些資料，只能讀取，不能修改，畢竟這是安插在程式碼區段中的資料。

第四章 質數 (1) 兼談動態連結程式庫

心路歷程

原理

Win64 的動態結程式庫

質數表

改進建立質數表的方法

①以一個位元代表一個奇數

②刪去質數的倍數時，從該質數的平方開始刪除

③以加法代替乘法，刪除質數的倍數

④篩選到根號 N 就可以了

判斷一正整數是否為質數

原始碼

小於或等於某正整數的質數列表：find_prime

判斷某正整數是否為質數：is_prime

原始碼

組譯與連結

補充解說

在 find_prime 裏，計算質數個數

副程式內用到的資料

第四章　質數 (1)　兼談動態連結程式庫