C++ 回文數判斷邏輯錯誤：誤將回文數當質數 + 質數判斷算法優化

原代碼問題定位

// 原代碼意圖：判斷輸入整數是否為回文數
if (reverse == n) 
    printf("%d is a palindrome", n);
else 
    printf("%d is not a palindrome", n);

用戶輸入 4，程序輸出 4 is a palindrome，用戶誤以為程序在判斷質數，實則 4 確實是回文數（單位數字皆為回文），邏輯無誤，只是需求理解偏差。

質數判斷正確實現

基礎版（試除法，適用於單數判斷）

bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;      // 2, 3 是質數
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

優化點：只檢查 6k±1 形式的因子，時間複雜度 O(√n)。

範圍質數輸出（埃拉托斯特尼篩法，O(n log log n)）

void printPrimesInRange(int L, int R) {
    vector isPrime(R + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= R; ++i) {
        if (isPrime[i]) {
            for (int j = i * i; j <= R; j += i)
                isPrime[j] = false;
        }
    }
    for (int i = max(2, L); i <= R; ++i)
        if (isPrime[i]) cout << i << ' ';
}

回文數與質數的區別

綜合練習：找出 100~200 之間的回文質數

int main() {
    for (int i = 100; i <= 200; ++i) {
        if (isPalindrome(i) && isPrime(i))
            cout << i << endl;
    }
    return 0;
}

bool isPalindrome(int n) {
    int rev = 0, orig = n;
    while (n > 0) {
        rev = rev * 10 + n % 10;
        n /= 10;
    }
    return rev == orig;
}

輸出：101, 131, 151, 181, 191

常見錯誤避坑指南

• void main() → 標準寫法 int main() 並 return 0;
• using namespace std; 建議具體引用或限制作用域。
• 判斷質數時 i < n 效率極低，務必用 i * i <= n。
• 輸入輸出優先用 cin/cout，關閉同步加速：ios::sync_with_stdio(false); cin.tie(nullptr);