# 題目: UVa 11960 - Divisor Game

# 題目說明

給一個整數N，求<= N中的哪一個整數有最多因數

---

INPUT:
第一行輸入一個整數T，代表有幾筆資料
每筆資料輸入一個整數N

---

OUTPUT:
<= N中有最多因數的整數

# 解題方法

先做質因數分解，透過以下公式能找到每個整數的因數個數
假設 $24 = 2^3 \cdot 3$
其因數為 1, 2, 3, 4, 6, 8, 12, 24，共8個
則將分解後的次方加1相乘即為因數個數
$(3 + 1) \cdot (1 + 1) = 8$

先找到2 - 1000000中每個數字的最小因數(不包括1)，並建表fact
對每個數除以它的最小因數，反覆做後能得到次方數
將所有次方數加1相乘後，則為因數個數，並建表ans儲存
最後再將<= N中的有最大因數個數的數分別存入表ans中

# 參考程式碼

#include <iostream>
#include <vector>

#define maxx 1000000
using namespace std;

int main()
{
    // fast io
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // init
    int T, x;
    vector<int> fact, ans;
    fact.assign(maxx + 1, 0);
    ans.assign(maxx + 1, 1);

    // find the smallest factor of 2 - 1000000 (except 1)
    for (long long i = 2; i <= maxx; ++i) if (!fact[i])
    {
        fact[i] = i;
        for (long long j = i * i; j <= maxx; j += i)
            if (!fact[j]) fact[j] = i;
    }

    // count the numbers of factors
    for (long long i = 2; i <= maxx; ++i)
    {
        auto tmp = i;
        while (tmp != 1)
        {
            int f = fact[tmp], cnt = 0;
            while (tmp % f == 0)
            {
                tmp /= fact[tmp];
                ++cnt;
            }
            ans[i] *= (cnt + 1);
        }
    }

    // find the number that has most factors <= i
    int maxn = 2, maxans = ans[2];
    for (long long i = 2; i <= maxx; ++i)
    {
        if (ans[i] >= maxans)
        {
            maxans = ans[i];
            maxn = i;
        }
        ans[i] = maxn;
    }

    cin >> T;
    while (T--)
    {
        cin >> x;
        cout << ans[x] << "\n";
    }

    return 0;
}

# 參考資料

https://hackmd.io/@SCIST/BasicMath3