113 年 國立中央大學企業管理學系碩士班己組《計算機概論》

QUIC 協定是由 Google 開發，並於 2012 年首次推出，2015 年成為 IETF 的工作項目。其發展背景主要源於對現有 TCP 協定在現代網路環境下的一些限制和瓶頸的思考。

發展背景：

1. TCP 的隊頭阻塞 (Head-of-Line Blocking, HOLB)： 在 TCP 中，資料是以連續的封包序列傳輸的。如果其中一個封包因為網路丟失或延遲而未能及時送達，即使後續的封包已經順利到達，也不能被上層應用程式處理，必須等待丟失的封包重傳。這種情況稱為隊頭阻塞，它會顯著影響網頁載入速度和串流媒體的體驗。
2. TCP 的延遲和握手開銷： TCP 的三次握手（three-way handshake）在建立連接時需要額外的往返時間（RTT），這在延遲敏感的應用中是不利的。
3. TLS 握手開銷： 傳統上，TCP 需要先完成三次握手，然後 TLS (Transport Layer Security) 再進行加密握手，這又增加了額外的 RTT，進一步延遲了應用資料的傳輸。
4. TCP 在擁塞控制上的限制： TCP 的擁塞控制演算法（如 Cubic、Reno）通常是在作業系統核心層實現的，更新和部署新的擁塞控制演算法相對困難，也難以針對特定應用進行優化。
5. UDP 的靈活性與 TCP 的可靠性結合需求： UDP 協定雖然有低延遲、低開銷的優點，但缺乏可靠性、流量控制和擁塞控制。QUIC 旨在利用 UDP 的靈活性，同時在應用層實現 TCP 的可靠性特性。

QUIC 的特色：

1. 基於 UDP： QUIC 運行在 UDP 之上，繞過了作業系統核心層對 TCP 的限制，允許更靈活的實現和部署。

VPN（Virtual Private Network，虛擬私人網路）是一種技術，允許使用者在公共網路上建立一個安全、加密的連接，如同他們直接連接到私人網路一樣。

VPN 的一般功能：

1. 安全性： VPN 會對傳輸的資料進行加密，保護資料在傳輸過程中不被竊聽或篡改，確保資訊的機密性和完整性。
2. 隱藏 IP 位址： VPN 客戶端會透過 VPN 伺服器進行網路存取，因此外部網路看到的是 VPN 伺服器的 IP 位址，而非客戶端的真實 IP 位址，從而保護使用者的隱私，並允許存取地理限制的內容。
3. 遠端存取： 允許遠端使用者（如在家工作或在差旅中的員工）安全地存取公司內部的網路資源，如檔案伺服器、應用程式等。
4. 網路整合： 連接不同地理位置的區域網路（LAN），形成一個更大的虛擬網路。

IPSec VPN、SSL VPN 與 MPLS VPN 的比較：

特性	IPSec VPN	SSL VPN	MPLS VPN
協定基礎	主要基於 IPSec 協定套件（AH, ESP, IKE）	主要基於 SSL/TLS 協定	基於 MPLS (Multiprotocol Label Switching) 技術
運作層級	通常在網路層（Layer 3）	通常在應用層（Layer 7）或傳輸層（Layer 4）	在資料鏈路層（Layer 2）和網路層（Layer 3）之間運作
存取方式	通常需要安裝專用的 VPN 客戶端軟體	通常透過網頁瀏覽器即可存取，無需安裝額外軟體（或僅需輕量級插件）	通常由網路服務提供商部署，終端使用者無感或僅需簡單設定

此題主要考查虛擬記憶體管理中的 TLB (Translation Look-aside Buffer) 和分頁 (Paging) 相關概念，包括 TLB 的作用、TLB Reach 的計算、實體位址空間的計算，以及多層級分頁結構下的有效存取時間計算。

已知條件：

• TLB 大小 (TLB entries)：1024
• 記憶體搜尋時間 (Memory access time)：200 ns
• TLB 命中率 (TLB hit rate)：90% = 0.9
• TLB 搜尋時間 (TLB access time)：20 ns
• 分頁表大小 (Page table size)：64 (此處應為分頁表項數，但題目給的是 64，後續計算會以 64 項來理解)
• 每個分頁表項的基底位置 (Page table entry base address bits)：11 bits
• 每個分頁大小 (Page size)：512 B

甲、此系統的 TLB 觸及範圍 (TLB Reach) 為多少？

TLB Reach 指的是 TLB 在一次記憶體存取中能夠直接映射的總記憶體位址空間大小。它等於 TLB 中的項目數量乘以每個項目所能映射的頁面大小。

• TLB 項目數 = 1024
• 頁面大小 = 512 B = $2^9$ B (因為 $512 = 2^9$)

TLB Reach = TLB 項目數 $\times$ 頁面大小
TLB Reach = 1024 $\times$ 512 B
TLB Reach = $2^{10} \times 2^9$ B
TLB Reach = $2^{19}$ B
TLB Reach = 524,288 B
TLB Reach = 512 KB

【答案】此系統的 TLB 觸及範圍為 512 KB。

乙、此系統的實體位址空間大小為何？

實體位址空間的大小由分頁表項中的基底位置（Physical Frame Number, PFN）的位元數決定。題目中提到「每個分頁表項的基底位置為 11 bits」。這 11 bits 代表了實體記憶體中的頁框號 (Page Frame Number, PFN)。

• PFN 的位元數 = 11 bits

實體位址空間大小 = $2^{\text{PFN 的位元數}}$
實體位址空間大小 = $2^{11}$
實體位址空間大小 = 2048 (這裡的單位是「頁框」)

然而，題目給定的「每個分頁大小為 512 B」與「分頁表大小為 64」可能存在一些混淆。通常，分頁表項會包含 PFN 和其他資訊（如 valid/invalid bit, dirty bit, protection bits）。如果 11 bits 是 PFN，那麼實體位址空間的大小是 $2^{11}$ 個頁框。
但題目又說「每個分頁大小為 512 B」，這通常是虛擬和實體記憶體共用的頁面大小。
我們需要釐清「基底位置」的含義。在傳統的分頁機制中，一個實體位址由「頁框號 (PFN)」和「頁內偏移 (Page Offset)」組成。頁面大小決定了頁內偏移的位元數。

• 頁面大小 = 512 B = $2^9$ B。因此，頁內偏移需要 9 bits。
• 實體位址的總位元數 = PFN 的位元數 + 頁內偏移的位元數。

如果題目中「每個分頁表項的基底位置為 11 bits」指的是 PFN 的位元數，那麼：
實體位址總位元數 = 11 (PFN) + 9 (頁內偏移) = 20 bits。
實體位址空間大小 = $2^{20}$ B = 1 MB。

另一種解釋：
題目說「分頁表大小為 64」，這似乎是指分頁表的總表項數。但這與 TLB 大小 (1024) 和 PFN 位元數 (11) 似乎沒有直接關聯。

最可能的解釋：
「每個分頁表項的基底位置為 11 bits」是指 實體頁框號 (PFN) 需要 11 bits 來表示。
而「每個分頁大小為 512 B」意味著頁內偏移需要 9 bits ($512 = 2^9$)。
因此，一個完整的實體位址的總位元數是 PFN 的位元數加上頁內偏移的位元數。
實體位址總位元數 = 11 (PFN) + 9 (頁內偏移) = 20 bits。
實體位址空間大小 = $2^{20}$ Bytes = 1 MB。

重要提示： 題目中「分頁表大小為 64」這個資訊在這個問題的計算中沒有被直接使用，這可能是一個干擾資訊，或者題目描述不夠清晰。通常，分頁表大小是指系統支援的虛擬頁面總數，或者物理頁框總數。如果 64 是指虛擬頁面數，那麼虛擬位址空間大小是 $64 \times 512$ B。但題目問的是「實體位址空間」。

基於「11 bits 的基底位置 (PFN)」和「512 B 的頁面大小 (決定頁內偏移)」，我們計算實體位址空間。

• PFN 位元數 = 11 bits
• 頁內偏移位元數 = $\log_2(512 \text{ B}) = 9$ bits
• 總實體位址位元數 = 11 + 9 = 20 bits
• 實體位址空間大小 = $2^{20}$ B = 1 MB。

【答案】此系統的實體位址空間大小為 1 MB。

丙、若分頁表採取了三階層式 (three-level) 的實作方式，其記憶體有效存取時間 (effective access time) 為何？

有效存取時間 (Effective Access Time, EAT) 的計算公式為：
EAT = (TLB Hit Rate $\times$ TLB Access Time) + (TLB Miss Rate $\times$ Page Table Access Time)

在多層級分頁結構中，Page Table Access Time 的計算會更複雜，因為存取一次分頁表可能需要多次記憶體讀取。
對於三階層式分頁，一次分頁表查找通常需要：

1. 讀取第一層分頁表（在記憶體中）。
2. 讀取第二層分頁表（在記憶體中）。
3. 讀取第三層分頁表（在記憶體中）。
4. 最終讀取到實體頁框號 (PFN)。

假設每次記憶體存取（讀取分頁表項）的時間是記憶體搜尋時間 (Memory access time)，即 200 ns。
如果 TLB Miss 發生，我們需要存取分頁表。

此題考查行程 (process) 和執行緒 (thread) 的概念，特別是 fork() 系統呼叫在多個層級下的行為，以及 thread_create() 的作用。

核心概念：

• fork(): 創建一個新的行程，該行程是呼叫 fork() 的行程的複本。父行程和子行程會從 fork() 呼叫之後的指令開始繼續執行。fork() 返回值不同：父行程收到子行程的 PID，子行程收到 0。
• thread_create(): 在當前行程內創建一個新的執行緒。執行緒與其所屬行程共享記憶體空間、檔案描述符等資源。

甲、請問會產生多少個獨立的行程 (process)?

我們逐行分析程式碼的執行流程，並追蹤行程的產生：

1. pid_t pid;：宣告一個變數 pid。

2. pid = fork();：

   • 此時，原始行程（假設為 P0）呼叫 fork()。
   • 系統創建一個 P0 的複本，稱為 P1。
   • P0 收到 P1 的 PID，繼續執行。
   • P1 收到 0，進入 if (pid == 0) 區塊。
   • 目前有 2 個行程：P0, P1。

3. if (pid == 0) { ... }：

   • P1 的 pid 是 0，所以 P1 進入此區塊。
   • P1 執行 fork();：
     • P1 創建一個自己的複本，稱為 P2。
     • P1 收到 P2 的 PID，繼續執行（在 if 區塊內部）。
     • P2 收到 0，進入 if (pid == 0) 區塊（但 P2 已經是子行程，所以它的 pid 也是 0，它也會執行 fork() 內部代碼）。
     • 此時，行程有 P0, P1, P2。

4. thread_create( . . .);：

   • 重要： thread_create() 是創建執行緒，不是行程。它在「當前」行程內執行。
   • 誰會執行 thread_create()？
     • P0 執行到這裡（因為 P0 的 pid 不是 0，它跳過了 if 區塊）。
     • P1 執行到這裡（在 if 區塊內部，fork() 之後）。
     • P2 執行到這裡（在 if 區塊內部，它也是 pid == 0 的子行程，所以它也執行了 thread_create）。
   • 假設 thread_create() 會在它被呼叫的行程中創建一個執行緒。
   • P0 創建一個執行緒 T1。
   • P1 創建一個執行緒 T2。
   • P2 創建一個執行緒 T3。
   • 行程數量仍然是 3 個：P0, P1, P2。 執行緒不增加行程數量。

5. fork();：

   • 這個 fork() 呼叫會被所有當前存活的行程執行。
   • P0 執行 fork()：創建 P3。P0 收到 P3 的 PID。
   • P1 執行 fork()：創建 P4。P1 收到 P4 的 PID。
   • P2 執行 fork()：創建 P5。P2 收到 P5 的 PID。
   • 目前行程有 P0, P1, P2, P3, P4, P5。

總結行程數量：

• 初始行程：1 個 (P0)
• 第一次 fork(): P0 複製為 P1。總計 2 個 (P0, P1)。
• P1 進入 if 區塊，執行 fork(): P1 複製為 P2。總計 3 個 (P0, P1, P2)。
• thread_create() 不影響行程數量。
• 最後一個 fork(): P0, P1, P2 各自複製一個新的行程。
  • P0 產生 P3。
  • P1 產生 P4。
  • P2 產生 P5。
• 最終的行程總數 = 3 (P0, P1, P2) + 3 (P3, P4, P5) = 6 個。

【答案】會產生 6 個獨立的行程。

乙、請問會產生多少個獨立的執行緒 (thread)?

執行緒的創建由 thread_create() 函數決定。
我們需要確定 thread_create() 被執行了多少次，以及在哪些行程中執行。

資料庫正規化（Database Normalization）的目標是消除資料冗餘、避免資料更新異常（如插入、刪除、修改異常），並確保資料的一致性。1NF、2NF 和 3NF 是正規化過程中的三個基本階段。

這三個正規化層級的發展，核心是圍繞著函數依賴 (Functional Dependency, FD) 這個觀念。

• 1NF (第一正規形式): 要求關係模式的每個屬性都必須是原子性的（不可再分割），並且確保沒有重複的群組。這主要是為了消除重複的群組，確保表的結構是基本的。
• 2NF (第二正規形式): 在 1NF 的基礎上，要求所有非主屬性（non-prime attributes）必須完全函數依賴於主鍵（primary key）。也就是說，任何非主屬性都不能只依賴於主鍵的一部分。這就解決了部分函數依賴 (Partial Functional Dependency) 的問題。

此題考查 C 語言的指標 (pointer) 和變數的記憶體操作。透過指標，可以間接存取和修改變數的值。

程式碼分析與執行流程：

1. int a = 11, b = 21;

   • 宣告整數變數 a，並初始化為 11。
   • 宣告整數變數 b，並初始化為 21。
   • 已知 a 儲存在記憶體位址 0X0012FF74。
   • 已知 b 儲存在記憶體位址 0X0012FF78。

2. int *p;

   • 宣告一個整數型指標 p。它是一個變數，用來儲存一個記憶體位址。

3. p = &a;

   • &a 是取 a 的記憶體位址，即 0X0012FF74。
   • 將 a 的位址賦值給指標 p。
   • 此時，p 的值為 0X0012FF74。p 現在指向變數 a。

本題的核心觀念為關聯式資料庫的正規化理論（Normalization Theory），重點考驗考生對正規形（1NF、2NF、3NF、BCNF）的判斷條件、遞移相依（Transitive Dependency）的消除與正規化分解，以及正規化在極端狀況下對於消除資料重複（Data Redundancy）與節省儲存空間的量化分析。

---

(a) 甲

解題過程與觀念說明：

1. 候選鍵（Candidate Key）與主鍵（Primary Key）分析：
   題目給定 $A$ 為 Primary Key 且為唯一的 Candidate Key。
   因此，主屬性（Prime Attribute）為 $A$；非主屬性（Non-prime Attributes）為 $B, C, D$。

2. 第一正規形（1NF）檢查：
   Table $X$ 的所有屬性皆為單一值且不可再分（Atomic Domain），因此符合 1NF。

3. 第二正規形（2NF）檢查：
   2NF 要求「消除部分相依（Partial Functional Dependency）」，即所有非主屬性必須完全函數相依於候選鍵。
   因為本題的 Candidate Key 僅由單一屬性 $A$ 組成（非複合鍵），故不可能存在對候選鍵「部分子集」的相依。所有非主屬性 $B, C, D$ 均完全相依於主鍵 $A$（即 $A \to B, C, D$），故符合 2NF。

4. 第三正規形（3NF）檢查：
   3NF 要求「消除遞移相依（Transitive Functional Dependency）」。對於任何非平凡的函數相依 $Y \to Z$，必須滿足下列條件之一：

   • $Y$ 為 Superkey（超鍵）。
   • $Z$ 為 Prime Attribute（主屬性）。
     觀察題目給定的函數相依 $B \to D$：
   • $B$ 並非 Superkey（因為 $B$ 無法決定 $A$ 與 $C$）。
   • $D$ 是非主屬性（Non-prime Attribute）。
     由於存在 $A \to B$ 且 $B \to D$，導致非主屬性 $D$ 遞移相依於主鍵 $A$。因此，Table $X$ 不符合 3NF。

綜合上述，Table $X$ 僅滿足第 1 正規形與第 2 正規形。

【答案】Table $X$ 滿足 1st NF 與 2nd NF（但不滿足 3rd NF）。原因在於 Candidate Key 為單一屬性 $A$，故無部分相依（滿足 2NF）；但存在函數相依 $B \to D$，其中 $B$ 非超鍵且 $D$ 非主屬性，造成遞移相依 $A \to B \to D$，因而違反 3NF。

---

(b) 乙

解題過程與觀念說明：

1. 是否需要進一步正規化？
   需要。因為 Table $X$ 存在遞移相依 $B \to D$，在未正規化的狀況下會引發資料異常（Anomalies）：

   • 新增異常（Insertion Anomaly）： 若要新增一組 $B \to D$ 的對應關係，但在尚無對應 $A$ 值時無法存入。
   • 刪除異常（Deletion Anomaly）： 刪除某筆 $A$ 資料時，可能不小心一併刪除唯一的 $B \to D$ 資訊。
   • 更新異常（Update Anomaly）： 若某個 $B$ 對應的 $D$ 需要修改，必須同步修改多筆重複資料，否則會造成資料不一致。

2. 如何進行正規化分解（Decomposition）：
   為了消除 $B \to D$ 帶來的遞移相依，依據正規化定理，將 Table $X(A, B, C, D)$ 分解為兩個關聯表：

   • $X_1(B, D)$：主鍵為 $B$，包含函數相依 $B \to D$。

本題考查資料庫系統（Database Systems）中「併發控制（Concurrency Control）」與「封鎖機制（Locking Mechanism）」的核心觀念。主要涵蓋兩個層面：一是鎖的類型與相容性（Lock Types & Compatibility），即共享鎖（Shared Lock）與排他鎖（Exclusive Lock）在讀寫權限與多交易（Transaction）間互斥排他性的差異；二是封鎖粒度（Lock Granularity），即鎖定資料範圍的大小（如 Tuple vs. Table）對系統併發度（Concurrency）、管理開銷（Overhead）與死鎖風險（Deadlock Risk）之間的權衡（Trade-off）。

---

(a) 甲、共享鎖 (Shared Lock) 與排他鎖 (Exclusive Lock) 之差異說明

在資料庫交易處理中，共享鎖（簡稱 $S$ 鎖，又稱 Read Lock）與排他鎖（簡稱 $X$ 鎖，又稱 Write Lock）施加於資料項目（Data Item）時，其主要差異在於操作存取權限與多交易間的相容性（Compatibility）：

1. 操作存取權限 (Access Permissions)：

   • 共享鎖 ($S$ 鎖)：當交易對某資料項目取得 $S$ 鎖後，該交易僅獲得**讀取（Read）**該項目的權限，不可修改或寫入（Write）。
   • 排他鎖 ($X$ 鎖)：當交易對某資料項目取得 $X$ 鎖後，該交易同時獲得**讀取（Read）與寫入（Write）**該項目的完整權限。

2. 多交易相容性與併發性 (Compatibility & Concurrency)：

   • 共享鎖 ($S$ 鎖)：具有相容性。多個交易可以同時對同一資料項目持有 $S$ 鎖（即 $S-S$ 相容）。這允許系統實現併發讀取（Concurrent Read），不會造成資料不一致問題。
   • 排他鎖 ($X$ 鎖)：具有獨佔排他性。一旦某交易對資料項目持有 $X$ 鎖，任何其他交易均無法獲取該項目的 $S$ 鎖或 $X$ 鎖（即 $S-X$、 $X-S$、 $X-X$ 皆不相容）。此機制是為了保護正在進行寫入的資料，避免產生髒讀（Dirty Read）、不可重複讀（Non-repeatable Read）或丟失更新（Lost Update）等衝突。

3. 鎖相容性矩陣 (Lock Compatibility Matrix)：

已持有鎖 \ 請求鎖	$S$ 鎖 (Shared Lock)	$X$ 鎖 (Exclusive Lock)
$S$ 鎖 (Shared Lock)	允許 (Compatible)	拒絕 (Incompatible)
$X$ 鎖 (Exclusive Lock)	拒絕 (Incompatible)	拒絕 (Incompatible)

本題的核心觀念在於數值狀態轉化的代數特性與位元運算（Bitwise Operation）性質。考驗考生是否能摒棄常規思維中額外宣告暫存變數（Temporary Variable）的做法，轉而利用數學運算（如加減法）或邏輯運算（如 XOR 位元互斥或）將兩個變數的狀態資訊相互編碼與解碼，以達到數值互換（Swap）的目的。

---

完整解題過程與原理說明

在標準的數值交換中，若使用 $temp$ 暫存變數，過程為 $temp=a;$ $a=b;$ $b=temp;$。若受限於不得使用第三個變數，主要有兩種經典解法：

方法一：算術加減法（Arithmetic Addition & Subtraction）

利用兩數之和暫存於其中一個變數中，再經由減法依序還原對方原本的值：

1. 第一步（求和編碼）： 將兩數之和存入 $a$
   $a = a + b$
   為什麼？ 此時變數 $a$ 同時攜帶了原始 $a_{old}$ 與 $b_{old}$ 的總和資訊，而 $b$ 仍保有原始值 $b_{old}$。

2. 第二步（解碼並還原原 $a$ 給 $b$）： 從總和 $a$ 減去現有的 $b$
   $b = a - b = (a_{old} + b_{old}) - b_{old} = a_{old}$
   為什麼？ 因為此時 $a$ 是總數，扣除舊的 $b$ 後，剩餘的值必然為舊的 $a$。此時 $b$ 已成功更新為 $a_{old}$。

3. 第三步（解碼並還原原 $b$ 給 $a$）： 從總和 $a$ 減去已更新的 $b$
   $a = a - b = (a_{old} + b_{old}) - a_{old} = b_{old}$
   為什麼？ 此時 $b$ 的值已經是 $a_{old}$，故總數 $a$ 減去現有的 $b$（即 $a_{old}$），結果即為 $b_{old}$，再將其賦值回 $a$。

補充說明： 在 Java 的整數二補數（Two's Complement）表示法中，即便 $a+b$ 產生了整數溢位（Overflow），其二進位位元的溢出也會被自動捨棄，代數運算結果在二補數系統下依然完美成立。

方法二：位元 XOR 法（Bitwise XOR Swap）

利用位元運算 XOR（$\oplus$）的自反性（$x \oplus x = 0$）、恆等性（$x \oplus 0 = x$）與交換律：

本題考查的核心觀念包含：質數判別（Prime Testing）演算法的設計與效能最佳化、試除法（Trial Division）上限的數學證明、Wheel Factorization（車輪因數分解法，如 $6k \pm 1$ 優化），以及 Java Console 輸入/輸出與控制結構。此題之評分關鍵在於能否證明演算法具備最佳的時間複雜度 $O(\sqrt{n})$ 與常數項最佳化，而非僅寫出基礎的試除迴圈。

---

1. 演算法設計與效能最佳化說明

本題要求編寫一 Java 程式，接收使用者輸入的整數 $n$，並輸出 $n$ 是否為質數（必須同時印出輸入數字與結果），且明確禁止呼叫 Java 內建庫（如 BigInteger.isProbablePrime）。以下針對演算法之正確性與最高效率設計進行分步證明：

(1) 搜尋上限最佳化：縮減至 $\sqrt{n}$

【為什麼只需檢查至 $\sqrt{n}$？】
假設整數 $n$ 為合數（Composite Number），則必可分解為兩個大於 $1$ 的整數相乘，即 $n = a \times b$（不妨設 $a \le b$）。
若 $a > \sqrt{n}$，則 $b \ge a > \sqrt{n}$，可推得：
$a \times b > \sqrt{n} \times \sqrt{n} = n$
此結果與 $a \times b = n$ 產生矛盾！
因此，$n$ 若為合數，其最小的非 $1$ 因數 $a$ 必定滿足 $a \le \sqrt{n}$。我們只需檢查至 $\lfloor\sqrt{n}\rfloor$ 即可；若在此範圍內找不到任何能整除 $n$ 的數，則 $n$ 必為質數。

• 時間複雜度由傳統試除法的 $O(n)$ 降至 $O(\sqrt{n})$。

(2) 候選因數最佳化：$6k \pm 1$ 篩選法（Wheel Factorization）

【為什麼只需檢查 $6k \pm 1$ 形式的數字？】
所有大於 $3$ 的正整數均可表示為以下六種形式之一（其中 $k \ge 1$）：
$6k, \quad 6k+1, \quad 6k+2, \quad 6k+3, \quad 6k+4, \quad 6k+5$
觀察各項的因子特性：

• $6k, 6k+2, 6k+4$ 均可被 $2$ 整除（偶數）。
• $6k+3$ 可被 $3$ 整除。
• $6k+5$ 等價於 $6(k+1)-1$。

因此，除了 $2$ 與 $3$ 本身之外，所有質數必定落在 $6k+1$ 或 $6k-1$ 兩種形式中。
在演算法設計中：

1. 先排除 $n \le 1$（非質數）、處理 $n = 2, 3$（質數）。
2. 排除所有 $2$ 與 $3$ 的倍數（n % 2 == 0 || n % 3 == 0）。
3. 測試迴圈變數 $i$ 自 $5$（即 $6(1)-1$）開始，每次增加 $6$，於迴圈內僅需檢測 $i$（即 $6k-1$）與 $i+2$（即 $6k+1$）是否能整除 $n$。

【效率比較】

• 基礎試除法：需檢查約 $n$ 個數。
• 奇數試除法（排除偶數）：需檢查約 $\frac{\sqrt{n}}{2}$ 個數。
• $6k \pm 1$ 優化試除法：僅需檢查約 $\frac{\sqrt{n}}{3}$ 個數。比僅排除偶數的方法再減少約 $33.3\%$ 的除法運算，為單次確定性試除法（Deterministic Trial Division）中效率最高的做法。

---

2. 完整 Java 程式碼