C 語言質數判定教學：從基礎到高效演算法完整指南│C言語ナビゲーター～システム開発のための最強リソース～

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

特別值得注意的是，2 是唯一的偶數質數，其餘的質數全為奇數。

質數的重要性

質數不僅在數學中是重要的概念，在電腦科學和加密技術中也有廣泛應用。特別是在加密演算法中，常利用大型質數來建立安全系統。

質數與 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」，表示不是質數。

檢查到平方根

從 p^2 開始檢查，可減少不必要的運算。

輸出結果

輸出仍然標記為「true」的數字，即為質數。

5. 實作注意事項

1. 處理大型數值

問題點
在 C 語言中，整數型別 (int) 的大小會依環境不同而異，在 32 位元環境下上限約為 21 億（2,147,483,647）。若需處理更大的數字，需採取以下措施：

解決方法

使用 long long int

可處理最大約 9 × 10¹⁸（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）

將已判定的結果儲存，下次遇到相同輸入時直接取用。

使用平行處理

使用多執行緒或 OpenMP 提升運算速度。

#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 語言的質數判定技巧，並進一步挑戰更高效的演算法與實際應用，持續提升程式開發能力。

C 語言質數判定教學：從基礎到高效演算法完整指南

1. 前言

2. 什麼是質數

質數的定義

質數的例子

質數的重要性

質數與 C 語言的關係

3. C 語言的質數判定方法

基本演算法

C 語言的基本實作範例

程式碼說明

4. 高效演算法介紹

加速處理的方法

什麼是埃拉托斯特尼篩法

埃拉托斯特尼篩法的 C 語言實作範例

程式碼說明

5. 實作注意事項

1. 處理大型數值

2. 計算量與效能最佳化

3. 錯誤處理的重要性

4. 程式碼可讀性與維護性

6. 範例程式執行結果

基本質數判定程式的執行範例

埃拉托斯特尼篩法程式的執行範例

執行注意事項

7. 總結

1. 重點回顧

2. 後續應用與進階學習

3. 結語

C 語言 #ifdef 完整教學：語法、用途與最佳實務指南

C 語言比較運算子完整教學｜基礎用法、範例與常見錯誤解析