發表新討論
#45093: 同為新手的解答


kingdom0987123@gmail.com (Alex Cheng)

學校 : 不指定學校
編號 : 196345
來源 : [140.117.194.238]
最後登入時間 ：
2024-10-06 02:13:07
a740. 质因数之和 -- 海豚原创 | From: [140.117.194.238] | 發表日期 : 2025-01-06 17:23

一開始要判斷n是否為質數, 如果是就直接輸出不用進行後續的判斷, 不然會超時。

否則: 外迴圈用變數 i 找出 n 可能的因數, 內迴圈用變數 j 判斷 i 是否為質數, 如果是則讓 n 不斷除以該質因數並加總。

要注意for迴圈的臨界條件: i*i <= n 而不是 i*i < n

 

#include <stdio.h>

int main()
{
    int n, sum, i, j;

    while (scanf("%d", &n) != EOF)
    {
        sum = 0;
        int isPrime = 1;

        // check if n is prime
        for (i = 2; i*i <= n; i++)
        {
            if (n % i == 0)
            {
                isPrime = 0;
                break;
            }
        }
        if (isPrime)
        {
            printf("%d\n", n);
            continue;
        }

        for (i = 2; i <= n; i++)
        {
            // check if i is prime
            isPrime = 1;

            for (j = 2; j*j <= i; j++)
            {
                if (i % j == 0)
                {
                    isPrime = 0;
                    break;
                }
            }

            // calculate sum
            if (isPrime)
            {
                while (n % i == 0)
                {
                    sum += i;
                    n /= i;
                }
            }
        }
        printf("%d\n", sum);
    }

    return 0;
}




 
ZeroJudge Forum