熱門文章

2025年7月15日 星期二

ZeroJudge 解題筆記:a740. 质因数之和

作者:王一哲
日期:2025年7月15日


ZeroJudge 題目連結:a740. 质因数之和

解題想法


測試 i = 2 ~ 根號 x 是否為 x 的因數,如果 i 是因數就繼續將 x 縮小為 1/i,直到 i 不是因數為止。最後如果 x 不等於 1,代表此時 x 是某一個質數,答案再加上 x。

Python 程式碼


使用時間約為 35 ms,記憶體約為 3.3 MB,通過測試。
import sys

for line in sys.stdin:
    x = int(line)
    ans = 0
    for i in range(2, int(x**0.5)+1):  # 測試 2 ~ 根號 x
        while x%i == 0:  # 如果 i 可以整除 x
            ans += i  # 加上 i
            x //= i  # x 變為 1/i
    if x != 1: ans += x  # 如果 x 不是 1,x 為質數
    sys.stdout.write(f"{ans:d}\n")


C++ 程式碼


使用時間約為 2 ms,記憶體約為 132 kB,通過測試。
#include <cstdio>
#include <cmath>
using namespace std;

int main() {
    int x;
    while(scanf("%d", &x) != EOF) {
        int ans = 0;
        for(int i=2; i<=(int)sqrt(x); i++) {
            while(x%i == 0) {
                ans += i;
                x /= i;
            }
        }
        if (x != 1) ans += x;
        printf("%d\n", ans);
    }
    return 0;
}


沒有留言:

張貼留言