c184: 盈虧互補

內容

畢達哥拉斯及其門徒稱 6 及 28 為完全數 (或稱為完美數)，因為它們都等於其真因數的和：

6 的真因數：1、2、3 其和為 1+2+3 = 6

28 的真因數：1、2、4、7、14 其和為 1+2+4+7+14 = 28

所以，一個正整數的真因數和等於它本身時，我們就稱它為完全數！

但是「人有悲歡離合，月有陰晴圓缺，此事古難全」，完全數也一樣。2016 年 1 月所發現的第 49 個完全數已經是 44,677,235 位數了。因此絕大多數的整數不是「盈數」就是「虧數」。

盈數：真因數和大於整數本身。例如 12 的真因數和 1+2+3+4+6 = 16，大於 12 本身。

虧數：真因數和小於整數本身。例如 15 的真因數和 1+3+5 = 9，小於 15 本身。

雖然大多數的整數都不是完全數，但是如果我們可以找到一對盈數與虧數，彼此互為對方的真因數和，那麼它們就可以透過互補而成為完美。我們稱這樣的一對盈數與虧數為「友好數」。

例如：
220 的真因數和 1+2+4+5+10+11+20+22+44+55+110 = 284
284 的真因數和 1+2+4+71+142 = 220

畢達哥拉斯曾說：「朋友是你靈魂的倩影，要像 220 與 284 一樣親密。」

輸入

輸入檔中有許多行，每行有一個數字 n (2 ≤ n ≤ 1000000)，n = 0 代表檔案結束，不需要對這個 0 輸出任何東西。

6
220
12
0

輸出

對輸入的每個數 n，如果 n 是完全數，請輸出 =n。否則請找出是否存在某個數 m，使得 n 和 m 是友好數。如果有，請輸出 m，，否則輸出 0。每個輸出都佔一行

=6
284
0

解題思路

求出除了自己的因數和，判斷該值是否為完美數，若是輸出、若否則再取該值除了自己的因數和，如果該因數和與輸入相同則為友好數。

求因數和時可以用開根號減少判斷次數。

完整程式碼

AC (2ms, 128KB)

#include <stdio.h>
#include <math.h>

int factorSum(int src)
{
    int end = sqrt(src), res = end * end == src ? 1 - end : 1;
    for (int i = 2; i <= end; i++)
    {
        if (!(src % i))
            res += i + src / i;
    }
    return res;
}

int main()
{
    int n, fs;
    while (scanf(" %d", &n) == 1 && n)
    {
        fs = factorSum(n);
        if (fs == n)
            printf("=%d\n", n);
        else
            printf("%d\n", factorSum(fs) == n ? fs : 0);
    }
    return 0;
}