C語言實作：輸出 10000 以內所有回文素數（含遞迴判斷邏輯修正）

題目需求

列印 10000 以內所有回文素數：即同時滿足「素數」與「回文數」的整數。例如 101、131、151…

原始代碼的邏輯錯誤與修正

原始碼中 isPalindrome(isPrimer(i)) 將素數判斷函數的回傳值（素數則回傳數值本身，非素數回傳 0）直接傳給回文判斷，導致邏輯錯誤。正確做法應分兩步獨立判斷：

1. isPrime(i) 回傳布林值（1/0）
2. isPalindrome(i) 直接檢查原數 i

修正後完整代碼

#include <stdio.h>
#include <stdbool.h>  // C99 布林型別

bool isPrime(int n);
bool isPalindrome(int n);

int main() {
    for (int i = 2; i < 10000; i++) {
        if (isPrime(i) && isPalindrome(i)) {
            printf("回文素數: %d\n", i);
        }
    }
    return 0;
}

// 素數判斷：試除法至 sqrt(n)
bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

// 回文判斷：數字反轉比對
bool isPalindrome(int n) {
    int original = n, reversed = 0;
    while (n > 0) {
        reversed = reversed * 10 + n % 10;
        n /= 10;
    }
    return original == reversed;
}

執行結果與效能優化

10000 以內回文素數共有 20 個：
2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929

優化方向

• 素數篩（Sieve of Eratosthenes）預先篩選，O(N log log N)
• 回文數生成法：直接構造回文數再測素數，減少檢查次數
• 位運算優化：偶數、5 的倍數直接跳過

本題適合練習函數模組化、布林邏輯與基礎數論概念。