ZeroJudge 解題筆記：i025. 真因數和 (小 n)

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


ZeroJudge 題目連結：i025. 真因數和 (小 n)

解題想法

因為測資不太，用試除法測試 $i = 2$ 到 $i = floor(\sqrt{n})$ 之間的整數是否為因數，如果 $i$ 是因數，則答案要加上 $i$ 及 $n/i$，最後再檢查 $n$ 是否為平方數，如果是平方數則答案要再減去 $\sqrt{n}$。

Python 程式碼

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

n = int(input())
if n == 1: print(0)  # 特例
else:
    root = int(n**0.5)
    isum = 1  # 所有真因數的合，找到真因數直接加起來就好
    for i in range(2, root+1):
        if n%i == 0:
            isum += i + (n//i)
    if root*root == n: isum -= root  # 完全平方數會多加一個 root，要扣掉
    print(isum)

C++ 程式碼

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

#include <cstdio>
#include <cmath>

int main() {
    int n; scanf("%d", &n);
    if (n == 1) {  // 特例
        printf("0\n"); 
    } else {
        int root = (int)sqrt(n);
        int isum = 1;  // 所有真因數的合，找到真因數直接加起來就好
        for(int i=2; i<= root; i++) {
            if (n%i == 0) isum += i + (n/i);
        }
        if (root*root == n) isum -= root;  // 完全平方數會多加一個 root，要扣掉
        printf("%d\n", isum);
    }
    return 0;
}