C 語言求 2~5000 中特殊素數：各位數字與各位和均為素數

題目要求

找出 2 到 5000 之間滿足條件的素數 x：

1. x 是素數。
2. x 的每一位數字（個位、十位、百位...）都是素數（即只能是 2, 3, 5, 7）。
3. x 的各位數字之和也是素數。

解題思路：模塊化分解

將問題拆解為三個獨立函數，主函數遍歷調用：

1. isPrime(int n)：判斷素數（試除法至 √n）。
2. digitsArePrime(int n)：逐位取模 10 判斷每位是否 ∈ {2,3,5,7}。
3. digitSumIsPrime(int n)：累加各位，調用 isPrime 判斷和是否為素數。

完整代碼

#include <stdio.h>
#include <math.h>
#include <stdbool.h>

// 判斷素數
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;
}

// 判斷每位數字是否為素數（2,3,5,7）
bool digitsArePrime(int n) {
    while (n > 0) {
        int d = n % 10;
        if (d != 2 && d != 3 && d != 5 && d != 7) return false;
        n /= 10;
    }
    return true;
}

// 判斷各位數字之和是否為素數
bool digitSumIsPrime(int n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return isPrime(sum);
}

int main() {
    printf("2~5000 滿足條件的特殊素數：\n");
    for (int x = 2; x <= 5000; x++) {
        if (isPrime(x) && digitsArePrime(x) && digitSumIsPrime(x)) {
            printf("%d ", x);
        }
    }
    printf("\n");
    return 0;
}

運行結果

2~5000 滿足條件的特殊素數：
2 3 5 7 23 223 227 337 353 373 557 577 733 757 773 2333 2357 2377 2557 2753 2777 3253 3257 3323 3527 3727 5233 5237 5273 5323 5527 7237 7253 7333 7523 7723 7727

優化提示

• 預計算 0-5000 素數表（埃拉托斯特尼篩法），isPrime 變為 O(1) 查表。
• 生成候選數時直接組合 {2,3,5,7} 位，避免遍歷所有數再判斷位數。