題目 1163：尋找個位為 1 的質數

問題描述

輸入一個整數 n（2 ≤ n ≤ 10000），輸出所有大於 1 且小於 n、個位數字為 1 的質數。質數之間用空格分隔，最後一個質數後不加空格；若不存在則輸出 -1。輸入包含多組測試資料，每行一個 n，EOF 結束。

範例

輸入：
100

輸出：
11 31 41 61 71

解題思路

1. 預先用埃拉托斯特尼篩法（Sieve of Eratosthenes）求出 10000 以內所有質數，時間複雜度 O(N log log N)。
2. 對每組輸入 n，遍歷 2 到 n-1，檢查是否為質數且個位為 1（即 i % 10 == 1）。
3. 收集符合條件的質數並格式化輸出。

優化要點

• 篩法預處理一次即可服務所有測試資料，避免重複判斷質數。
• 輸出時注意格式：首個質數前不加空格，其後每個前加一空格，或用標誌變量控制。

參考代碼 (C)

#include 
#include 
#include 

#define MAXN 10000
bool is_prime[MAXN + 1];

void sieve() {
    for (int i = 2; i <= MAXN; i++) is_prime[i] = true;
    for (int i = 2; i * i <= MAXN; i++)
        if (is_prime[i])
            for (int j = i * i; j <= MAXN; j += i)
                is_prime[j] = false;
}

int main() {
    sieve();
    int n;
    while (scanf("%d", &n) != EOF) {
        bool first = true;
        for (int i = 2; i < n; i++) {
            if (is_prime[i] && i % 10 == 1) {
                if (!first) printf(" ");
                printf("%d", i);
                first = false;
            }
        }
        if (first) printf("-1");
        printf("\n");
    }
    return 0;
}

複雜度

預處理 O(MAXN log log MAXN) ≈ 10⁴，每查詢 O(n)，極快滿足限制。