在學習 C 語言的過程中，「質數判定」是常出現的基本問題之一。對於程式設計初學者來說，「了解數字的性質，並具備選擇適當演算法的能力」是一個很好的機會。此外，透過學習更有效率的質數判定演算法，亦能加深對演算法計算量差異與程式最佳化的理解。 本文將使用 C 語言介紹質數判定的方法，並提供可實際執行的範例程式碼。從基本的試除法到更快速的埃拉托斯特尼篩（篩法），將介紹各種不同的手法。
2. 什麼是質數？
質數是指除 1 與其本身外沒有正因數的自然數。例如，2、3、5、7、11 等都是質數。
2.1. 質數的基本特徵
最小的質數是 2（唯一的偶數質數）
1 不是質數（因為只有 1 個因數）
質數無限存在
若大於等於 2 的整數 n 不是質數，必定能被大於等於 2 的質數整除
2.2. 質數的具體例子
數值
是否為質數
2
✅ 質數
3
✅ 質數
4
❌ 合成數（2×2）
5
✅ 質數
6
❌ 合成數（2×3）
7
✅ 質數
8
❌ 合成數（2×4）
9
❌ 合成數（3×3）
3. C語言的基本素數判定方法（🔰 初學者向）
在此，我們介紹最基本的方法「試除法」。
3.1. 試除法（基本）
試除法是指，對於 2 以上的整數 N，檢查是否能被 1 與 N 本身以外的整數整除的方法。
若 N 為 2 以上的整數，確認是否能被 2 到 N-1 的數字整除
若有可整除的數字則為「合成數」，若無則為「素數」
範例程式碼（基本版）
#include <stdio.h>
int is_prime(int n) {
if (n < 2) return 0; // 1 以下不是素數
for (int i = 2; i < n; i++) { // 確認是否能被 2 到 n-1 整除
if (n % i == 0) return 0;
}
return 1;
}
int main() {
int num = 7;
if (is_prime(num))
printf("%d 是素數\n", num);
else
printf("%d 不是素數\n", num);
return 0;
}
執行結果
7 是素數
此方法簡單且易於理解，但有因計算量為 O(N) 且較大，當 N 增大時處理時間會變長的缺點。接下來的章節將介紹更有效率的方法。
4. C語言中有效判斷質數的方法【埃拉托斯特尼篩法・改良版試除法】
為了最佳化質數判斷的計算，說明以下兩種方法。
√N まで的試除法（最佳化）
埃拉托斯特尼篩（篩子）
4.1. √N まで的試除法（最佳化）
非質數的數字 N 必定有 √N 以下的因數，因此只要檢查 到 N 的平方根的範圍 即可，這是重點。 範例程式碼
#include <stdio.h>
#include <math.h>
int is_prime_optimized(int n) {
if (n < 2) return 0;
if (n % 2 == 0 && n != 2) return 0; // 偶數除2外皆非質數
for (int i = 3; i <= sqrt(n); i += 2) { // 只檢查奇數（跳過偶數）
if (n % i == 0) return 0;
}
return 1;
}
int main() {
int num = 29;
if (is_prime_optimized(num))
printf("%d 是質數n", num);
else
printf("%d 不是質數n", num);
return 0;
}
執行結果
29 是質數
透過此方法，計算量從 O(N) → O(√N) 改善，即使對於大數也能快速判斷。
4.2. 埃拉托斯特尼篩（篩子）
埃拉托斯特尼篩是一種「透過刪除小質數的倍數，來有效找出質數的演算法」。
從 2 開始，刪除其所有倍數
接著刪除剩下的最小數（3）的倍數
如此重複，僅留下質數
範例程式碼
#include <stdio.h>
#include <stdbool.h>
void sieve(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;
}
}
for (int p = 2; p <= n; p++)
if (prime[p])
printf("%d ", p);
printf("n");
}
int main() {
int n = 50;
sieve(n);
return 0;
}
執行結果
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
埃拉托斯特尼篩的計算量為 O(N log log N)，在大量求取質數的情況下最為適合。
5. C語言的素數判定演算法效能比較【速度測量與最佳化】
素數判定的演算法有幾種不同的手法，但它們的處理速度與效率差異很大。本節將對以下三種方法，測量 C 語言的執行時間，並探討哪種手法在何種情況下有效。
int is_prime(int n) {
if (n < 2) return 0;
for (int i = 2; i < n; i++) {
if (n % i == 0) return 0;
}
return 1;
}
void test_trial_division(int limit) {
int count = 0;
for (int i = 2; i <= limit; i++) {
if (is_prime(i)) count++;
}
printf("總素數: %d\n", count);
}
5.3. 執行時間的比較（圖表化）
方法
計算量
10,000 時
100,000 時
1,000,000 時
試除法
O(N)
0.25 秒
2.5 秒
數十秒〜數分
√N 試除法
O(√N)
0.02 秒
0.15 秒
1.5 秒
埃拉托斯特尼篩法
O(N log log N)
0.001 秒
0.005 秒
0.03 秒
可見埃拉托斯特尼篩法壓倒性地快。
6. FAQ（常見問題）
在本節中，我們將回答有關 C 語言素數判定的常見問題。
Q1: 為什麼在素數判定中使用平方根？
A: 若某個數 N 不是素數，則必定在 N 的平方根以下存在約數，這是一個數學性質。 例如，當 N = 49 時，約數的配對如下。
