ZeroJudge 解題筆記：d120. 10699 - Count the factors

作者：王一哲
日期：2026年4月14日


ZeroJudge 題目連結：d120. 10699 - Count the factors

解題想法

這題可以事先計算 1 到 1000000 對應的最小質因數，在找特定數字 $n$ 的質因數個數時會比較快，可以從目前的值跳到下一個質因數。如果直接用除的，逐一測試比目前數值 $x$ 還小的質因數，這樣也會過，只是速度慢一點。

Python 程式碼

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

def solve():
    import sys

    # 建表，1 ~ 1000000 之間每個數對應的最小質因數 smallest prime factor
    max_num = 1000000
    spf = [0]*(max_num + 1)
    for i in range(2, max_num + 1):
        if spf[i] == 0:  # i 是質數
            spf[i] = i
            if i*i <= max_num:
                for j in range(i*i, max_num + 1, i):
                    if spf[j] == 0:  # 如果 j 還沒有最小質因數，設定成 i
                        spf[j] = i
    # 主要的解題過程
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        if n == 0: break  # 停止的條件
        if n == 1:  # 特例
            result.append("1 : 0\n")
            continue
        cnt = 0  # 質因數數量
        x = n  # n 的值存到 x
        while x > 1:  # 如果 x 還能分解繼續執行
            p = spf[x]  # 取出 x 的最小質因數
            cnt += 1
            while x%p == 0:  # 如果 p 可以整除 x 繼續執行
                x //= p  # x 除以 p
        result.append(f"{n:d} : {cnt:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

使用時間約為 0.5 s，記憶體約為 8.5 MB，通過測試。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        if n == 0: break  # 停止的條件
        if n == 1:  # 特例
            result.append("1 : 0\n")
            continue
        cnt = 0  # 質因數數量
        x = n  # n 的值存到 x
        p = 2  # 質因數，從 2 開始測試
        while p <= x:  # 如果 p 小於等於 x，p 可能是因數，繼續執行
            if x%p == 0:  # 如果 p 是因數
                cnt += 1
                while x%p == 0:  # 如果 p 可以整除 x 繼續執行
                    x //= p  # x 除以 p
            p += 1
        result.append(f"{n:d} : {cnt:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

C++ 程式碼

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

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

int main() {
    /* 建表，1 ~ 1000000 之間每個數對應的最小質因數 smallest prime factor */
    const int max_num = 1000000;
    vector<int> spf (max_num + 1, 0);
    for(int i=2; i<=max_num; i++) {
        if (spf[i] == 0) {  // i 是質數
            spf[i] = i;
            if (i <= max_num/i) {
                for(int j=i*i; j<=max_num; j+=i) {
                    if (spf[j] == 0) {  // 如果 j 還沒有最小質因數，設定成 i
                        spf[j] = i;
                    }
                }
            }
        }
    }
    /* 主要的解題過程 */
    int n;
    while(scanf("%d", &n) != EOF && n != 0) {
        if (n == 1) {  // 特例
            puts("1 : 0");
            continue;
        }
        int cnt = 0, x = n;  // 質因數數量，n 的值存到 x
        while(x > 1) {  // 如果 x 還能分解繼續執行
            int p = spf[x];  // 取出 x 的最小質因數
            cnt++;
            while(x%p == 0) {  // 如果 p 可以整除 x 繼續執行
                x /= p;  // x 除以 p
            }
        }
        printf("%d : %d\n", n, cnt);
    }
    return 0;
}

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

#include <cstdio>

int main() {
    int n;
    while(scanf("%d", &n) != EOF && n != 0) {
        if (n == 1) {  // 特例
            puts("1 : 0");
            continue;
        }
        int cnt = 0, x = n, p = 2;  // 質因數數量，n 存到 x，p 從 2 開始測試
        while(p <= x) {
            if (x%p == 0) {
                cnt++;
                while(x%p == 0) {  // 如果 p 可以整除 x 繼續執行
                    x /= p;  // x 除以 p
                }
            }
            p++;
        }
        printf("%d : %d\n", n, cnt);
    }
    return 0;
}