ZeroJudge 解題筆記：k376. 求包含最大質因數的數

作者：王一哲
日期：2025年11月28日


ZeroJudge 題目連結：k376. 求包含最大質因數的數

解題想法

先用埃拉托斯特尼篩法建立1 ~ 20000 之間的質數表 primes。讀取 n 個數字 m，用內建的二分搜尋法從 primes 之中找 m 插入的位置 idx，如果 m 是質數，再檢查 m 是否是新的答案； 如果 m 不是質數，從 idx 往回找最大的質因數 fac，再檢查 fac 是否是新的答案。

Python 程式碼

使用時間約為 17 ms，記憶體約為 3.3 MB，通過測試。

from bisect import bisect_left

""" 建立 1 ~ 20000 之間的質數表 """
maxn = 20000
sieve = [True]*(maxn+1)
sieve[0] = sieve[1] = False
for i in range(2, int(maxn**0.5) + 1):
    if sieve[i]:
        for j in range(i+i, maxn+1, i):
            sieve[j] = False
primes = [i for i in range(maxn+1) if sieve[i]]
""" 讀取 n 個數字找答案 """
ans, fmax = 0, 0  # 答案，最大質因數
n = int(input())
for _ in range(n):
    m = int(input())
    idx = bisect_left(primes, m)  # 用二分搜尋法找 m 在 primes 之中插入的位置
    if m == primes[idx] and m >= fmax and m > ans:  # 如果 m 是質數
        ans = m; fmax = m
    else:  # 如果 m 不是質數，從 idx 往回找最大的因數
        for i in range(idx, -1, -1):
            fac = primes[i]
            if m%fac == 0:
                if fac >= fmax and m > ans:
                    ans = m; fmax = fac
                break
print(ans)

C++ 程式碼

使用時間約為 2 ms，記憶體約為 312 kB，通過測試。

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int main() {
    const int maxn = 20000;
    vector<bool> sieve (maxn+1, true);
    sieve[0] = false;
    sieve[1] = false;
    for(int i=2; i<=int(sqrt(maxn)); i++) {
        if (sieve[i]) {
            for(int j=i*i; j<=maxn; j+=i) {
                sieve[j] = false;
            }
        }
    }
    vector<int> primes;
    for(int i=0; i<=maxn; i++) {
        if (sieve[i]) {
            primes.push_back(i);
        }
    }
    int ans = 0, fmax = 0, n;
    scanf("%d", &n);
    while(n--) {
        int m; scanf("%d", &m);
        int idx = lower_bound(primes.begin(), primes.end(), m) - primes.begin();
        if (m == primes[idx] && m >= fmax && m > ans) {
            ans = m; fmax = m;
        } else {
            for(int i=idx; i>=0; i--) {
                int fac = primes[i];
                if (m%fac == 0) {
                    if (fac >= fmax && m > ans) {
                        ans = m; fmax = fac;
                    }
                    break;
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}