1. 前言 C 語言因其能夠高速且高效地建立程式，被廣泛應用於系統開發、嵌入式裝置等多個領域。本文將詳細介紹使用 C 語言實作「質數判定」的方法。 質數是指除了 1 和它本身之外，沒有其他正因數的自然數。例如，2、3、5、7 是質數，但 4 和 6 則不是。質數在加密技術和數學問題的解決中扮演著重要角色。 本文將從 C 語言撰寫基本的質數判定程式，到更高效的演算法進行淺顯易懂的說明，內容適合從初學者到中級程式設計師，請務必閱讀到最後。
2. 什麼是質數 質數的定義 質數（Prime Number）是指大於 1 的自然數中，除了 1 和它本身之外，沒有其他因數的數字。質數的例子 以下是一些較小的質數範例：2, 3, 5, 7, 11, 13, 17, 19, 23, 29 質數的重要性 質數不僅在數學中是重要的概念，在電腦科學和加密技術中也有廣泛應用。特別是在加密演算法中，常利用大型質數來建立安全系統。質數與 C 語言的關係 由於 C 語言能進行高效的整數運算，特別適合撰寫需要處理大量資料的質數判定程式。接下來將介紹使用 C 語言進行質數判定的具體方法。3. C 語言的質數判定方法 基本演算法 最基本的質數判定方法包含以下兩步：如果數字 ( n ) 小於 2，則判定為非質數。 將 ( n ) 依序除以 2 到 ( sqrt{n} ) 之間的整數，若有餘數為 0 的情況則判定為非質數。 C 語言的基本實作範例 以下程式會判斷使用者輸入的整數是否為質數：#include <stdio.h>
#include <math.h>
// 質數判定函數
int is_prime(int n) {
if (n <= 1) return 0; // 1 以下不是質數
if (n == 2) return 1; // 2 是質數
if (n % 2 == 0) return 0; // 偶數不是質數
// 只檢查奇數
for (int i = 3; i <= sqrt(n); i += 2) {
if (n % i == 0) return 0; // 能整除則不是質數
}
return 1; // 判定為質數
}
int main() {
int num;
// 輸入
printf("請輸入整數: ");
scanf("%d", &num);
// 判斷與結果輸出
if (is_prime(num))
printf("%d 是質數。
", num);
else
printf("%d 不是質數。
", num);
return 0;
}程式碼說明 引入標頭檔 <stdio.h>：用於標準輸入與輸出。<math.h>：使用 sqrt 函數計算平方根所需。is_prime 函數若 n <= 1 則判定為非質數。 2 特例為質數。 偶數（除 2 外）皆為非質數。 迴圈僅檢查奇數，減少計算次數。 檢查至平方根 因質數的因數呈對稱分布，只需檢查至 ( sqrt{n} ) 即可。 使用者輸入與輸出結果
4. 高效演算法介紹 加速處理的方法 雖然基本的質數判定演算法簡單易懂，但當數字變大時，計算量會大幅增加，導致處理速度變慢。可以透過以下方法進行優化：排除偶數 除了 2 以外的偶數都不是質數，因此僅判定奇數即可。 檢查到平方根 因因數在平方根位置呈對稱分佈，因此只需檢查到 ( sqrt{n} ) 為止。 加入預先判定 先用小質數（如 2、3、5、7）進行除法測試，能快速排除部分數字。 什麼是埃拉托斯特尼篩法 埃拉托斯特尼篩法是一種能在指定範圍內高效找出所有質數的演算法，步驟如下：初始化 剔除倍數 從 2 開始，將每個數字的倍數標記為「false」，表示不是質數。 結束條件 埃拉托斯特尼篩法的 C 語言實作範例 #include <stdio.h>
#include <stdbool.h>
#define MAX 1000 // 質數搜尋的上限
void sieve_of_eratosthenes(int n) {
bool prime[n + 1]; // 儲存質數判定的陣列
for (int i = 0; i <= n; i++)
prime[i] = true; // 初始化為質數候選
for (int p = 2; p * p <= n; p++) {
if (prime[p]) {
for (int i = p * p; i <= n; i += p)
prime[i] = false; // 剔除倍數
}
}
// 顯示結果
printf("質數列表:
");
for (int i = 2; i <= n; i++) {
if (prime[i])
printf("%d ", i);
}
printf("
");
}
int main() {
int limit;
printf("請輸入要搜尋質數的範圍上限: ");
scanf("%d", &limit);
if (limit < 2) {
printf("請輸入大於或等於 2 的數值。
");
return 1;
}
sieve_of_eratosthenes(limit);
return 0;
}程式碼說明 初始化陣列 prime[] 假設所有數字都是質數，先將它們設定為「true」。 剔除倍數 從 2 開始，將每個數字的倍數標記為「false」，表示不是質數。 檢查到平方根 輸出結果
5. 實作注意事項 1. 處理大型數值 問題點 在 C 語言中，整數型別 (int) 的大小會依環境不同而異，在 32 位元環境下上限約為 21 億（2,147,483,647）。若需處理更大的數字，需採取以下措施： 解決方法 使用 long long int 可處理最大約 9 × 1018 （9,223,372,036,854,775,807）。 long long int num = 9223372036854775807LL;使用外部函式庫 例如 GMP（GNU MP）函式庫，可處理多倍長整數。 #include <gmp.h>
mpz_t num;
mpz_init(num);2. 計算量與效能最佳化 問題點 質數判定計算量大，特別是在大範圍列舉質數時，可能導致運算變慢。 最佳化方法 使用快取（Memoization） 使用平行處理 #pragma omp parallel for
for (int i = 0; i < n; i++) {
// 平行處理
}選擇合適的演算法 小範圍用「試除法」，大範圍用「埃拉托斯特尼篩法」。 3. 錯誤處理的重要性 可能出現的錯誤 無效輸入 ：負數、零或非法字串。溢位 ：輸入數值過大。解決方法 輸入驗證 int num;
printf("請輸入整數: ");
if (scanf("%d", &num) != 1) {
printf("輸入無效。
");
return 1;
}範圍限制 防止記憶體洩漏 4. 程式碼可讀性與維護性 問題點 即使是為初學者設計的程式，如果結構過於複雜，也會降低可讀性與維護性。 改善建議 函數拆分 加強註解 使用具描述性的變數名稱 避免使用 num、prime 等模糊名稱，可改用 input_number、is_prime_result。
6. 範例程式執行結果 本節將示範前面介紹的 C 語言質數判定程式與埃拉托斯特尼篩法的執行結果，並透過實際輸出確認各程式的運作情況。基本質數判定程式的執行範例 程式碼（再次列出） #include <stdio.h>
#include <math.h>
// 質數判定函數
int is_prime(int n) {
if (n <= 1) return 0; // 1 以下不是質數
if (n == 2) return 1; // 2 是質數
if (n % 2 == 0) return 0; // 偶數不是質數
// 僅檢查奇數
for (int i = 3; i <= sqrt(n); i += 2) {
if (n % i == 0) return 0; // 可整除則不是質數
}
return 1; // 判定為質數
}
int main() {
int num;
// 輸入
printf("請輸入整數: ");
scanf("%d", &num);
// 判斷與輸出
if (is_prime(num))
printf("%d 是質數。
", num);
else
printf("%d 不是質數。
", num);
return 0;
}執行範例 請輸入整數: 17
17 是質數。
請輸入整數: 18
18 不是質數。
請輸入整數: 1
1 不是質數。
請輸入整數: -5
-5 不是質數。埃拉托斯特尼篩法程式的執行範例 程式碼（再次列出） #include <stdio.h>
#include <stdbool.h>
#define MAX 1000 // 質數搜尋上限
void sieve_of_eratosthenes(int n) {
bool prime[n + 1];
for (int i = 0; i <= n; i++)
prime[i] = true;
for (int p = 2; p * p <= n; p++) {
if (prime[p]) {
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
printf("質數列表:
");
for (int i = 2; i <= n; i++) {
if (prime[i])
printf("%d ", i);
}
printf("
");
}
int main() {
int limit;
printf("請輸入要搜尋質數的範圍上限: ");
scanf("%d", &limit);
if (limit < 2) {
printf("請輸入大於或等於 2 的數值。
");
return 1;
}
sieve_of_eratosthenes(limit);
return 0;
}執行範例 請輸入要搜尋質數的範圍上限: 50
質數列表:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47執行注意事項 輸入值限制 輸入過大的數值可能導致記憶體不足或運算速度下降。特別是埃拉托斯特尼篩法在範圍過大時會消耗更多記憶體，因此應設定合理限制。 錯誤處理檢查 當輸入無效數值或發生例外錯誤時，需確保能正確顯示錯誤訊息。 不同環境下的測試 不同 C 編譯器或標準函式庫版本可能導致行為差異，建議在多個環境中進行測試。
7. 總結 本文詳細介紹了 C 語言質數判定的方法，從基本演算法到高效實作，並提供了注意事項與實際範例。1. 重點回顧 質數的定義 質數是大於 1 且只有 1 和自身作為因數的自然數，在數學與加密技術中有重要地位。 C 語言的基本判定方法 介紹了利用試除法進行質數判定，並透過平方根優化計算。 高效演算法 實作注意事項 程式範例 2. 後續應用與進階學習 透過本文學習的質數判定演算法，還可延伸至更多應用與進階主題： 1. 高階演算法 Miller-Rabin 質數測試 ：一種快速的機率性判定法，適合大數判定。AKS 質數判定法 ：可保證判定結果正確的演算法，在數學上具有重要意義。2. 加密技術應用 RSA 加密 ：利用質數實作公鑰加密系統，並學習其運作原理。3. 大數據處理與最佳化 學習平行運算或 GPU 加速以處理大規模質數計算。 4. 多語言實作 將質數判定演算法移植到 Python、C++ 等語言並比較效能差異。 3. 結語 質數判定雖是基礎程式設計主題，但與數學理論與加密應用緊密相關。希望透過本文，讀者能掌握 C 語言的質數判定技巧，並進一步挑戰更高效的演算法與實際應用，持續提升程式開發能力。
