C語言解題：找出陣列中約數個數最多的數（最多約數問題）

最多約數問題解析

給定一組整數，找出其中約數（因子）個數最多的那個數。若有多個數擁有相同最多約數個數，題目隱含要求輸出較大者（因先排序再遍歷，後覆蓋前）。

問題描述

• 輸入：多組測資，每組先給 n，再給 n 個整數。
• 對每個數計算約數個數（含 1 和自身）。
• 追蹤最大約數個數 mark 與對應數值 max。
• 輸出 max。

原始解法：排序 + 試除法 O(n × max_val/2)

#include <stdio.h>

void sort(int arr[], int n);

int main()
{
    int n, arr[200];
    while(scanf("%d", &n) != EOF)
    {
        for(int i=0; i mark) { mark = count; max = arr[i]; }
        }
        printf("%d\n", max);
    }
    return 0;
}

void sort(int arr[], int n) { /* 氣泡排序 */ }

執行結果示意

關鍵修正：約數計數邏輯

原碼 count=1; for(j=2; j<=arr[i]/2; j++) if(...) count++;
這計算的是「1 到 n/2 的約數個數」，**漏算了 n 本身**。
正確應為：count = 0; for(j=1; j*j<=arr[i]; j++) ... 或最後 count++ 加上自身。

優化：約數個數 O(√n) 計算

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;
}

時間從 O(n/2) 降為 O(√n)。

進階：篩法預計算約數個數 O(N log N)

若數值範圍已知（如 ≤ 10⁵），可預處理所有數的約數個數：

vector div_cnt(MAXN+1, 0);
for(int i=1; i<=MAXN; i++)
    for(int j=i; j<=MAXN; j+=i)
        div_cnt[j]++;

查詢時 O(1) 取得約數個數。

題目陷阱提醒

• 輸入可能包含負數？題目通常限定正整數。
• 0 的約數無限多，需特判排除。
• 排序非必要，但可確保相同約數個數時輸出較大值（若題目要求）。