ZeroJudge 解題筆記：o580. 因數計算 (Factor)

作者：王一哲
日期：2025年6月13日


ZeroJudge 題目連結：o580. 因數計算 (Factor)

解題想法

我先寫一個找因數用的函式 num_of_factor，輸入整數 x，用 set 儲存 x 的因數，最後回傳因數的數量。在主程式中，讀取要找的範圍 start、end，依序找 start 到 end 的因數數量並更新答案。

Python 程式碼

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

import sys

def num_of_factor(x):  # 輸入 x，找 x 的因數
    factor = {1, x}  # 因數，一定有 1, x
    for i in range(2, int(x**0.5)+1):  # 暴力解，找 i = 2 ~ sqrt(x)
        if x%i == 0:  # 如果 x 可以被 i 整除
            factor.add(i)  # i 是 x 的因數
            factor.add(x//i)  # x//i 是 x 的因數
    return len(factor)  # 回傳因數的數量

for line in sys.stdin:
    start, end = map(int, line.split())  # 要計算 start ~ end 的因數數量
    ans, imax = 0, 0  # 因數最多的數字 ans，因數數量 imax
    for i in range(start, end+1):  # 依序代入 start ~ end
        fac = num_of_factor(i)  # 呼叫 num_of_factor 計算 i 的因數數量
        if fac > imax:  # 如果 fac 大於 imax，更新 ans 及 imax
            ans = i; imax = fac
    print(ans, imax)

C++ 程式碼

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

#include <cstdio>
#include <set>
using namespace std;

int num_of_factor(int x) { // 輸入 x，找 x 的因數
    set<int> factor = {1, x};  // 因數，一定有 1, x
    for(int i=2; i*i <= x; i++) {  // 暴力解，找 i = 2 ~ sqrt(x)
        if (x%i == 0) {  // 如果 x 可以被 i 整除
            factor.insert(i);  // i 是 x 的因數
            factor.insert(x/i);  // x/i 是 x 的因數
        }
    }
    return (int)factor.size();  // 回傳因數的數量
}

int main() {
    int start, end;  // 要計算 start ~ end 的因數數量
    while(scanf("%d %d", &start, &end) != EOF) {
        int ans = 0, imax = 0;  // 因數最多的數字 ans，因數數量 imax
        for(int i=start; i<=end; i++) {  // 依序代入 start ~ end
            int fac = num_of_factor(i);  // 呼叫 num_of_factor 計算 i 的因數數量
            if (fac > imax) {  // 如果 fac 大於 imax，更新 ans 及 imax
                ans = i; imax = fac;
            }
        }
        printf("%d %d\n", ans, imax);
    }
    return 0;
}