區間最大約數個數問題：窮舉法與優化策略 C 實作

給定區間 [a, b] (a ≤ b)，找出約數個數最多的整數及其約數個數。本文提供基礎窮舉法 O((b-a+1)√b) 實作，並討論篩法預計算優化至 O(N log log N) 的思路，適合教學與中等資料範圍。

基礎窮舉法

對區間內每個數 x，檢查 1‥√x 計算約數個數：

int countDivisors(int x) {
    int cnt = 0;
    for (int i = 1; i * i <= x; ++i) {
        if (x % i == 0) {
            cnt += (i * i == x) ? 1 : 2;  // 完全平方數只算一次
        }
    }
    return cnt;
}

主程式遍歷 [a, b] 記錄最大值。

完整 C 程式碼（含互動迴圈）

#include <stdio.h>

int countDivisors(int x) {
    int cnt = 0;
    for (int i = 1; i * i <= x; ++i) {
        if (x % i == 0) cnt += (i * i == x) ? 1 : 2;
    }
    return cnt;
}

int main() {
    int a, b;
    char cont = 'n';
    do {
        printf("請輸入區間 a b：");
        scanf("%d %d", &a, &b);
        if (a < 1 || b < 1 || a > b) {
            printf("輸入錯誤！\n");
            continue;
        }

        int bestNum = a, bestDiv = 0;
        for (int x = a; x <= b; ++x) {
            int d = countDivisors(x);
            if (d > bestDiv) {
                bestDiv = d;
                bestNum = x;
            }
        }
        printf("數 %d 有 %d 個約數（最多）\n", bestNum, bestDiv);

        printf("繼續？(y/n)：");
        scanf(" %c", &cont);  // 空白吃掉換行
    } while (cont == 'y' || cont == 'Y');
    return 0;
}

複雜度分析

• 時間：O((b-a+1) × √b)。若 b ≤ 10^5 可接受；10^6 以上建議優化。
• 空間：O(1)。

優化策略：篩法預計算約數個數

若需多次查詢或 b 較大（≤ 10⁶~10⁷），可預先篩選：

const int MAXN = 1000000;
int divCnt[MAXN + 1] = {0};

void sieveDivisors() {
    for (int i = 1; i <= MAXN; ++i) {
        for (int j = i; j <= MAXN; j += i) {
            divCnt[j]++;  // i 是 j 的約數
        }
    }
}
// 查詢區間 [a,b] 只需掃描 divCnt[a..b] 找最大值，O(b-a+1)

複雜度：預處理 O(N log N) ≈ O(N log log N)，查詢 O(1) 或 O(區間長度)。

數學補充：高約數數特徵

• 高合成數：約數數創紀錄的數（1, 2, 4, 6, 12, 24, 36, 48, 60, 120...）。
• 質因數分解 n = p1^e1 * p2^e2 * ...，約數個數 τ(n) = (e1+1)(e2+1)...。
• 若知上界，可預先生成高合成數表直接查表。

總結

區間最大約數問題以窮舉法為基礎，理解約數計算的 √n 優化與篩法預計算兩大技巧，即可根據資料範圍靈活選擇實作策略。