109 年 國立成功大學資訊管理研究所乙組《計算機概論》

ASCII 是「American Standard Code for Information Interchange」的

此題考驗網路互連裝置的功能。
(a) Switches (交換器)：主要在區域網路 (LAN) 內部，根據 MAC 位址轉送封包，連接同質性網路。
(b) Gateways (閘道器)：用於連接不同協定或不同網路架構的網路，是 OSI 模型中最高層級的設備，可以進行協定轉換。
(c) Routers (路由器)：用於連接不同的網路 (例如 LAN 和 WAN)，根據 IP 位址轉送封包，並選擇最佳路徑。

此題考驗對硬碟儲存結構的理解。
硬碟的儲存結構由多個圓形盤片 (platter) 組成，每個盤片有兩個表面。在每個表面上，資料以同心圓的方式記錄，這些同心圓軌道稱為「磁軌 (track)」。

此題考驗對網路作業系統 (Network Operating System, NOS) 及用戶端/伺服器 (Client/Server) 架構的理解。

(a) 正確。多使用者作業系統 (Multiuser OS) 的核心功能之一就是管理多個使用者如何同時存取和共享網路資源。
(b) 正確。現代許多作業系統（如 Windows Server, Linux）都內建了豐富的網路功能，以便支援網路服務。
(c) 正確。

核心觀念
OSI（Open Systems Interconnection）模型將網路功能分為七層，其中最底層的兩層為

• 第1層：實體層（Physical Layer） – 處理原始位元的傳輸、電氣與機械規格。
• 第2層：資料連結層（Data Link Layer） – 負責在相同網段內的封包傳遞與錯誤檢測，常見的子層有 MAC 子層與 LLC 子層。

在這兩層上運作的網路設備會直接處理電氣訊號或 MAC 位址，而不涉及網際協定（IP）等上層資訊。

解題方法

1. 先釐清題目要求：「在 OSI 模型的最底兩層（第1層與第2層）上工作的元件」。
2. 依據每個選項的功能與所在層級判斷其所屬層：
   • 只涉及電氣訊號或 MAC 位址的設備 → 第1層或第2層。
   • 需要 IP 位址或路由表的設備 → 第3層（網路層）以上。
3. 逐一檢視選項，將符合條件的標記為正確。

選項分析

核心觀念
本題測驗對 HTTP（HyperText Transfer Protocol） 的基本認識。

• HTTP 是用於 客戶端（Client） 與 伺服器（Server） 之間傳遞 超文字（Hypertext） 的應用層協定。
• 只要系統（軟體或裝置）在其通訊過程中 採用 HTTP 協定，便稱之為 使用 HTTP 的系統。
• 常見的使用者端有 Web Browser，提供服務的端有 Web Server，而 WWW（World Wide Web） 是以 HTTP 為主要傳輸協定的全球資訊網，屬於概念層面而非具體系統。

解題方法
辨識題目所問的「任一使用 HTTP 協定的系統」的定義，對照選項中每個名詞的屬性：

1. 判斷 Web Browser 是否僅是「使用 HTTP」的系統；
2. 判斷 Web Server 是否符合「使用 HTTP」的系統；
3. 判斷 WWW 是否指代具體的「系統」或僅是概念。
   比較後即可排除不符合「任一使用 HTTP 的系統」之描述的選項。

選項分析

此題考驗對網路協定中 ARP (Address Resolution Protocol) 的理解。ARP 協定在 TCP/IP 協定堆疊中，主要用於在區域網路 (LAN) 中，將已知的 IP 位址 (IP address) 解析 (resolve) 成對應的實體位址 (physical address)，也就是 MAC 位址 (MAC address)。

此題考驗對不同類型惡意軟體的理解。

(a) Worm (蠕蟲)：是一種獨立的惡意程式，可以自我複製並透過網路傳播，不需要依附在其他檔案上。
(b) Bomb (炸彈)：通常指邏輯炸彈 (Logic Bomb)，是一種惡意程式碼，會在特定條件滿足時（例如特定日期、事件發生）才被觸發並執行破壞性動作。

此題考驗 C++ 中的型別轉換 (type casting) 和浮點數運算在計算平均值時可能遇到的問題。要計算四個整數 $a, b, c, d$ 的平均值，正確的做法是將總和除以 4，並確保結果是浮點數。

讓我們逐一分析選項：
假設 $a, b, c, d$ 都是整數。

a) float ((a + b + c + d) / 4.0)

• a + b + c + d：整數加法，結果是整數。
• (a + b + c + d) / 4.0：整數總和除以浮點數 4.0。這會觸發浮點數除法，結果是一個浮點數。
• float(...)：將浮點數結果轉換為 float 型別。這通常是正確的。
• 此選項正確。

b) (float (a + b + c + d)) / 4

• a + b + c + d：整數加法，結果是整數。
• float (a + b + c + d)：將整數總和轉換為 float 型別。
• (float(...)) / 4：浮點數除以整數 4。這也會觸發浮點數除法，結果是一個浮點數。
• 此選項正確。

核心觀念

本題考查物件導向程式語言中的「函式多載」（function overloading）。

函式多載是指：在同一個作用域中，可以定義多個「同名函式」，但它們必須具有不同的參數列表（parameter list），讓編譯器能根據呼叫時提供的參數，判斷應執行哪一個函式。

參數列表通常包含：

• 參數個數
• 參數型別
• 參數排列順序

例如：

void print(int x);
void print(double x);
void print(int x, int y);

上述三個函式名稱皆為 print，但參數列表不同，因此構成函式多載。

解題方法

判斷函式是否能夠多載的關鍵，是確認「僅根據函式呼叫中的參數」，編譯器是否能分辨不同函式。

因此，多載函式必須在參數列表上有所差異：

回傳型別並不會出現在一般函式呼叫的辨識依據中。例如：

int calculate(int x);
double calculate(int x);

呼叫：

calculate(5);

編譯器無法只依據呼叫內容判斷要使用哪一個函式，因此不能僅靠不同回傳型別形成多載。

選項分析

a) Different parameter lists.

正確。

多載函式必須具有不同的參數列表，可以是參數個數、型別或順序不同。例如：

void show(int x);
void show(int x, int y);

兩者同名，但參數個數不同，因此可以形成多載。

b) Different return types.

錯誤。

此題考驗十進位小數轉換為十六進位小數。
將十進位數 $(346.25)_{10}$ 轉換為十六進位數。我們需要分別轉換整數部分和分數部分。

整數部分轉換：
將 346 除以 16，記錄餘數，直到商為 0。
$346 \div 16 = 21$ 餘 $10$ (A)
$21 \div 16 = 1$ 餘 $5$
$1 \div 16 = 0$ 餘 $1$

此題考驗十六進位小數轉換為八進位小數。
將十六進位數 $(1AD.86)_{16}$ 轉換為八進位數。
轉換十六進位到八進位，最直接的方法是先將十六進位轉換為二進位，然後再將二進位轉換為八進位。
每個十六進位數字對應 4 個二進位數字。
每個八進位數字對應 3 個二進位數字。

步驟 1：將十六進位轉換為二進位
$1_{16} = 0001_2$
$A_{16} = 10_{10} = 1010_2$
$D_{16} = 13_{10} = 1101_2$
$.$
$8_{16} = 1000_2$
$6_{16} = 0110_2$

所以，$(1AD.86)_{16} = (0001 \ 1010 \ 1101 . 1000 \ 0110)_2$

步驟 2：將二進位轉換為八進位
從二進位小數點開始，向左和向右每三位分組，不足補零。

整數部分：$(0001 \ 1010 \ 1101)_2$
分組：$(000 \ 110 \ 101 \ 101)_2$
轉換：$000_2 = 0_8$
$110_2 = 6_8$
$101_2 = 5_8$
$101_2 = 5_8$
所以整數部分為 $(0655)_8 = (655)_8$。

小數部分：$(1000 \ 0110)_2$
分組：$(100 \ 001 \ 100)_2$ (注意：這裡需要補零使總位數是 3 的倍數，從點開始向右分組。$(.86)_{16} = (.1000 \ 0110)_2$ 。正確分組是：$.100 \ 001 \ 100$。所以是 $100 \ 001 \ 100$。)

核心觀念

• 二補數 (two's complement)：在固定長度 $n$ 位元的二進位系統中，負數 $-x$ 的表示方式為「先將正數 $x$ 的二進位表示全部取反 (1→0, 0→1)，再加 1」。
• 位元寬度：本題要求使用 16 位元；因此正數 $x$ 必須先以 16 位元的形式寫出，缺少的高位補 0。

解題方法

1. 求 $2020$ 的 16 位元二進位表示。
2. 取反得到 $2020$ 的一的補數 (1's complement)。
3. 在一的補數基礎上加 $1$，得到 $-2020$ 的二補數表示。

步驟示範

1. 正數 2020 的 16 位元二進位

$2020_{10}=0x07E4_{16}=0000\;0111\;1110\;0100_{2}$

（先將十進位轉成十六進位 $0x07E4$，再展開為 16 位元二進位）

2. 取反 (1's complement)

$\overline{0000\;0111\;1110\;0100}=1111\;1000\;0001\;1011$

3. 加 1 取得二補數

此題考驗遞迴函數 (Recursive Function) 的執行過程。
我們需要計算 Fun(2) 的返回值。
遞迴函數的定義是：

• 終止條件 (Base Case)：當 n == 4 時，函數回傳 2。
• 遞迴步驟 (Recursive Step)：當 n != 4 時，函數回傳 2 * Fun(n+1)。

讓我們逐步追蹤 Fun(2) 的呼叫過程：

1. Fun(2) 被呼叫：

   • n 是 2。n == 4 為 false。
   • 執行 return 2 * Fun(2+1)，即 return 2 * Fun(3)。
   • 需要先計算 Fun(3) 的返回值。

2. Fun(3) 被呼叫：

   • n 是 3。n == 4 為 false。

此題考驗 C++ 的 do-while 迴圈和字元運算。
程式碼的執行流程如下：

1. 初始化： char c = 'A';
   變數 c 被初始化為字元 'A'。

2. 進入 do-while 迴圈： do-while 迴圈的特性是先執行一次迴圈體，然後再檢查條件。

   第一次迴圈執行：

   • c += 2;：字元 'A' 的 ASCII 值是 65。c 變成 65 + 2 = 67。字元 67 對應 'C'。所以 c 現在是 'C'。
   • cout << c << " ";：輸出字元 'C'，後面跟一個空格。輸出：C
   • 檢查條件 while ( c <= 'M' );：'C' 的 ASCII 值 (67) 是否小於或等於 'M' 的 ASCII 值 (77)？ 是 (67 <= 77)。條件為 true。

   第二次迴圈執行：

   • c += 2;：c 現在是 'C' (ASCII 67)。c 變成 67 + 2 = 69。字元 69 對應 'E'。所以 c 現在是 'E'。
   • cout << c << " ";：輸出字元 'E'，後面跟一個空格。輸出：C E
   • 檢查條件 while ( c <= 'M' );：'E' 的 ASCII 值 (69) 是否小於或等於 'M' 的 ASCII 值 (77)？ 是 (69 <= 77)。條件為 true。

   第三次迴圈執行：

   • c += 2;：c現在是 'E' (ASCII 69)。c 變成 69 + 2 = 71。字元 71 對應 'G'。所以 c 現在是 'G'。
   • cout << c << " ";：輸出字元 'G'，後面跟一個空格。輸出：C E G
   • 檢查條件 while ( c <= 'M' );：'G' 的 ASCII 值 (71) 是否小於或等於 'M' 的 ASCII 值 (77)？ 是 (71 <= 77)。條件為 true。

   第四次迴圈執行：

   • c += 2;：c現在是 'G' (ASCII 71)。c 變成 71 + 2 = 73。字元 73 對應 'I'。所以 c 現在是 'I'。

核心觀念

本題考查 Web 應用程式中的 HTTP Cookie、HTTP 無狀態特性，以及 Cookie 與間諜軟體的區別。

HTTP 通訊本身是無狀態的（stateless）：伺服器處理完一次請求後，不會自動記得下一次請求是否來自同一位使用者。因此，網站需要某種機制保存使用者識別資訊，例如登入狀態、購物車內容與個人化設定，Cookie 即是其中最常見的方法。

Cookie 是由網站伺服器傳送給瀏覽器的一小段名稱—數值資料，瀏覽器依照規則保存，之後向同一網站提出請求時，再將 Cookie 傳回伺服器。

解題方法

可從三個角度回答：

1. Cookie 在 Web 應用程式中做什麼。
2. Cookie 為何稱為 Cookie。
3. Cookie 為何不等於 spyware。

一、Cookie 是什麼

典型流程如下：

1. 使用者第一次造訪網站。
2. 伺服器在 HTTP 回應中加入 Set-Cookie 標頭。
3. 瀏覽器保存該 Cookie。
4. 使用者再次向符合條件的網站發出請求時，瀏覽器在 HTTP 請求中加入 Cookie 標頭。
5. 伺服器讀取 Cookie，辨識使用者或取得相關設定。

簡化的 HTTP 訊息如下：

HTTP/1.1 200 OK
Set-Cookie: sessionId=abc123; Path=/; HttpOnly

之後瀏覽器提出請求：

GET /profile HTTP/1.1
Host: example.com
Cookie: sessionId=abc123

伺服器便可藉由 sessionId=abc123 查詢後端的 Session 資料，確認使用者已登入。

Cookie 本身通常只保存少量資料，例如：

• Session ID
• 語言或地區設定
• 購物車識別資訊
• 使用者偏好
• 分析與廣告識別碼

重要的是，Cookie 通常不是用來保存完整的密碼或大量個人資料，而是保存一個識別值，實際資料則存放在伺服器端。

二、Cookie 在 Web 應用程式中的用途

Cookie 主要用於：

1. 維持登入狀態

登入成功後，伺服器建立 Session，並把 Session ID 放入 Cookie。使用者瀏覽其他頁面時，瀏覽器自動附帶該 Cookie，伺服器因此能辨識使用者。

2. 保存使用者偏好

網站可以記錄語言、佈景主題、字型大小等設定，使使用者下次造訪時維持相同介面。

3. 維持購物車或交易流程

電子商務網站可利用 Cookie 辨識購物車或暫存的操作流程。

4. 進行網站分析與追蹤

網站可利用 Cookie 判斷訪客是否曾造訪、瀏覽哪些頁面，以及不同頁面的使用情形。此用途涉及隱私議題，但不代表 Cookie 本身就是惡意軟體。

三、為什麼稱為 Cookie

「Cookie」源自早期計算機系統中的 magic cookie 概念。Magic cookie 指的是一段由系統產生、由程式保存並在後續交易中原樣帶回的資料，用來辨識狀態或授權身分。

Web Cookie 的概念與此相似：

• 伺服器先交給瀏覽器一段資料；
• 瀏覽器保存這段資料；
• 後續請求時再把它交還給原網站；
• 伺服器藉此辨識使用者或延續狀態。

此題考驗對程式語言編譯 (compiled) 與直譯 (interpreted) 機制的理解。

1. Python 的語言類型：
Python 通常被認為是一種直譯語言 (interpreted language)，但實際上它是一個「混合體」。

• Python 原始碼 (.py 檔) 首先被編譯成一種稱為「位元組碼」(bytecode) 的中間形式 (.pyc 檔)。
• 然後，Python 虛擬機器 (Python Virtual Machine, PVM) 會逐條執行這些位元組碼。
• 因此，Python 既有編譯的步驟（生成位元組碼），又有直譯的步驟（執行位元組碼）。
• 在實際應用中，由於編譯成位元組碼的過程對使用者是透明的，且執行時是逐條解釋位元組碼，因此 Python 常被歸類為直譯語言。

2. Java 的語言類型：
Java 是一種編譯與直譯混合的語言。

• Java 原始碼 (.java 檔) 被編譯成一種稱為「位元組碼」(bytecode) 的中間形式 (.class 檔)。這個編譯過程類似於 Python。
• 然後，這些 Java 位元組碼會在 Java 虛擬機器 (Java Virtual Machine, JVM) 上執行。
• JVM 可以透過兩種方式執行位元組碼：
  • 直譯 (Interpretation)： 逐條讀取並執行位元組碼。
  • 即時編譯 (Just-In-Time, JIT Compilation)： 在程式執行過程中，將位元組碼編譯成機器碼，以提高執行效率。
• 因此，Java 結合了編譯（生成位元組碼）和直譯/JIT 編譯（在 JVM 上執行）的特性。

3. 編譯式語言與直譯式語言的差異：

此題要求針對 Gartner 對區塊鏈 (Blockchain) 在 2020 年的戰略影響力預測，以及其「實驗性與小規模應用，但對企業部署仍不成熟」的論點，表達同意或不同意，並提供論據。這是一個需要結合技術發展趨勢和實際應用情境來論述的開放性問題。

我同意 Gartner 的論點，即區塊鏈在 2020 年仍處於實驗性和小規模應用階段，對企業級大規模部署而言尚不成熟。

理由與論據：

1. 技術成熟度與可擴展性 (Scalability) 問題：

   • 論點： 儘管區塊鏈技術的核心概念（去中心化、不可篡改、透明性）非常吸引人，但目前主流的區塊鏈平台（如比特幣、以太坊）在交易處理速度 (Transactions Per Second, TPS) 上存在顯著瓶頸。例如，比特幣約為 7 TPS，以太坊約為 15-30 TPS。這遠遠無法滿足許多企業級應用對高吞吐量的需求（例如 Visa 每秒可處理數千筆交易）。
   • 證據： 許多研究和實際測試都表明，現有的公鏈在擴展性方面面臨挑戰。雖然有 Layer 2 解決方案（如閃電網路、Rollups）和新的共識機制（如 PoS 的變種）在努力解決此問題，但它們本身也還在發展和驗證階段，且可能引入新的複雜性或權衡。

2. 企業部署的複雜性與成本：

   • 論點： 企業級區塊鏈解決方案的部署不僅僅是技術問題，還涉及整合現有系統、法律法規遵循、治理模型建立、標準化，以及高昂的開發和維護成本。
   • 證據： 雖然有許多企業（如 IBM, Oracle, SAP）提供了企業級區塊鏈平台，但許多項目仍處於概念驗證 (PoC) 或試點階段。成功的大規模企業部署案例相對較少，且通常局限於特定行業（如供應鏈金融、數位身份驗證）或聯盟鏈 (Consortium Blockchain) 的形式，其去中心化程度不如公鏈。

3. 標準化與互操作性 (Interoperability) 的缺乏：

此題為選擇題，需將短語與對應的定義配對。
短語：「Do this to add your e-mail name and address to a mailing list.」（執行此操作以將您的電子郵件名稱和地址添加到郵寄清單。）
這個動作是指「訂閱」郵寄清單。

此題為選擇題，需將短語與對應的定義配對。
短語：「Windows 7 and Linux are examples.」（Windows 7 和 Linux 是...的例子。）
Windows 7 和 Linux 是眾所周知的電腦作業系統。

此題為選擇題，需將短語與對應的定義配對。
短語：「Kind of software that consists of programs designed to make users more productive.」（一種軟體，由旨在提高使用者生產力的程式組成。）
旨在提高使用者生產力的軟體，通常指的是應用程式或工具軟體。

此題為選擇題，需將短語與對應的定義配對。
短語：「A collection of unprocessed items, which can include text, numbers, images, audio, and video.」（未經處理項目的集合，可能包含文字、數字、圖像、音訊和視訊。

此題為選擇題，需將短語與對應的定義配對。
短語：「A device consists of electronic components that store instructions waiting to be executed and data needed by those instructions.」（一個由電子元

此題為選擇題，需將短語與對應的定義配對。
短語：「A program controls how you enter data and instructions and how information is displayed on the screen.」（一個程式，控制您如何輸入數據和指令，以及資訊如何在螢幕上顯示。）

此題為選擇題，需將短語與對應的定義配對。
短語：「The process of setting up the software.」（設定軟體的過程。）

此題為選擇題，需將短語與對應的定義配對。
短語：「A software for organizing data in rows and columns and performing calculations on the data.」（一種用於將資料組織成行和列並對資料進行計算

此題為選擇題，需將短語與對應的定義配對。
短語：「The component of the processor that directs and coordinates most of the operations in the computer.」（處理器中負責指揮和協調電腦中大多數操作的組件。）

核心觀念
本題測驗的是 指令流水線 (Instruction Pipelining) 的概念。

• 流水線：將指令執行的完整機械週期（取指‐譯碼‐執行‐寫回）切分為多個階段，讓不同指令同時佔用不同階段。
• 目的：提高 CPU 效能，使處理器在前一指令尚未完成整個週期時即可取下一指令，減少閒置時間。
• 相關術語：Pipeline Hazard（資料冒險、控制冒險、結構冒險）、pipeline depth、clock cycle。

解題方法

1. 讀題敘述：“Frees processors from having to wait for one instruction to complete the machine cycle before fetching the next.”
2. 判斷描述對應的機制。
   • 若是 「在完整週期結束前就能取指」，只有 指令流水線 能滿足此條件；其他技術（快取、分支預測、DMA、Interrupt）皆屬於 降低記憶體或 I/O 延遲，不會改變指令取用的順序。
3. 因此答案即為 Pipelining（指令流水線）。

選項分析（假設常見的四個選項）

此題為選擇題，需將短語與對應的定義配對。
短語：「If application software has stopped responding and the hard disk's LED blinks repeatedly, the operating system probably is doing this.」（如果應用程式軟體停止回應，並且硬碟的 LED 持續閃爍，則作業系統可能正在執行此操作。）

此題為選擇題，需將短語與對應的定義配對。
短語：「Your Internet service provider supplies this, for an e-mail address.」（您的網際網路服務提供者為電子郵件地址提供的東西。）
網際網路服務提供者 (ISP) 通常會為用戶提供一個電子郵件地址。

此題為選擇題，需將短語與對應的定義配對。
短語：「Keeps track of changes made to Web sites by checking RSS feeds.」（透過檢查 RSS feed 來追蹤網站變更。）

此題為選擇題，需將短語與對應的定義配對。
短語：「Self-service gas pumps often print receipts using this kind of printer.」（自助加油機經常使用這種印表機列印收據。）

此題為選擇題，需將短語與對應的定義配對。
短語：「Can be negatively affected by the distance between two points, the type of transmission media, and the number of nodes through which data must travel.」（可能受到兩點之間的距離、傳輸媒體的類型以及數據必須經過的節點數量的負面

核心觀念

本題評量**十六進位數值運算（Hexadecimal Arithmetic）與進位制轉換（Base Conversion）**能力。

1. 十六進位符號對應：十六進位基底為 16，符號包含 $0 \sim 9$ 以及 $\text{A} \sim \text{F}$（其中 $\text{A}_{16}=10_{10}$、$\text{B}_{16}=11_{10}$、$\text{C}_{16}=12_{10}$、$\text{D}_{16}=13_{10}$、$\text{E}_{16}=14_{10}$、$\text{F}_{16}=15_{10}$）。
2. 十六進位乘法原則：乘法運算遵循直式乘法法則，但每位數的乘積與進位皆以 逢 16 進 1（$\text{Base } 16$）處理。

解題方法

本題可採用「十六進位直式乘法」直接求解，亦可透過「轉十進位計算法」進行輔助驗算。

【方法一】十六進位直式乘法（標準解法）

計算式為 $\text{A3}_{16} \times \text{2D}_{16}$：

1. 計算第一列：$\text{A3}_{16} \times \text{D}_{16}$（其中 $\text{D}_{16} = 13_{10}$）

   • 個位數相乘：$3 \times 13 = 39_{10} = 2 \times 16 + 7 \implies$ 該位寫 $7$，進位 $2$。
   • 高位數相乘加進位：$\text{A}_{16} \times 13 + 2 = 10 \times 13 + 2 = 132_{10}$。
   • 將 $132_{10}$ 化為十六進位：$132 = 8 \times 16 + 4 \implies$ 為 $84_{16}$。
   • 故 $\text{A3}_{16} \times \text{D}_{16} = \mathbf{847_{16}}$。

2. 計算第二列：$\text{A3}_{16} \times 2_{16}$

   • 個位數相乘：$3 \times 2 = 6_{10} \implies$ 該位寫 $6$，進位 $0$。
   • 高位數相乘：$\text{A}_{16} \times 2 = 10 \times 2 = 20_{10} = 1 \times 16 + 4 \implies$ 為 $14_{16}$。
   • 故 $\text{A3}_{16} \times 2_{16} = \mathbf{146_{16}}$（對齊至 $16^1$ 權重位）。

3. 將各列乘積相加（十六進位加法）：

此題考驗二進位數的乘法。
我們需要計算 $x \times y$ 的結果，其中 $x = (1001)_2$ 且 $y = (100)_2$。

方法一：直接進行二進位乘法
$1001_2$
$\times$ $100_2$

$0000$ ($1001 \times 0$)
$00000$ ($1001 \times 0$, 左移一位)
$100100$ ($1001 \times 1$, 左移兩位)

$100100_2$

方法二：轉換為十進位計算再轉換回二進位

此題要求編寫一個程式來找出小於正整數 N 的所有質數，並證明其正確性。這是一個典型的演算法問題。

程式碼 (以 Python 為例)：

def find_primes_less_than_n(n):
    """
    Finds all prime numbers less than a positive integer n.

    Args:
        n: A positive integer.

    Returns:
        A list of prime numbers less than n.
    """
    if n <= 2:
        return [] # No primes less than or equal to 2 (or less than 2)

    # Initialize a boolean list "is_prime" where is_prime[i] is True if i is potentially prime.
    # We only need to check up to n-1. The size of the list is n.
    # We can assume all numbers from 2 up to n-1 are prime initially.
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False # 0 and 1 are not prime numbers

    # Iterate from p = 2 up to sqrt(n-1).
    # We only need to check for factors up to the square root of the number.
    # If a number 'i' has a factor greater than its square root, it must also have a factor smaller than its square root.
    # We iterate up to sqrt(n), because if a number 'k' < n is composite,
    # it must have a prime factor p <= sqrt(k) <= sqrt(n).
    p = 2
    while (p * p < n):
        # If is_prime[p] is still True, then p is a prime number.
        if (is_prime[p] == True):
            # Mark all multiples of p (starting from p*p) as not prime.
            # We start from p*p because any multiple smaller than p*p (e.g., 2*p, 3*p, ..., (p-1)*p)
            # would have already been marked by smaller prime factors (2, 3, ..., p-1).
            for i in range(p * p, n, p):
                is_prime[i] = False
        p += 1

    # Collect all numbers 'i' for which is_prime[i] is True.
    prime_numbers = []
    for i in range(n):
        if is_prime[i]:
            prime_numbers.append(i)

    return prime_numbers

# Example usage:
# n_value = 30
# primes = find_primes_less_than_n(n_value)
# print(f"Prime numbers less than {n_value}: {primes}")

正確性證明 (Justification of Correctness):