Edison.X. Blog

題目敘述

對一個正整數 N 而言，將它除了本身以外所有的因數加起來的總和為 S，如果 S>N，則 N 為盈數，如果 S<N，則 N 為虧數，
而如果 S=N，則 N 為完全數(Perfect Number)。

通解 ?

完全數為質因數應用之一範例，給初學者之 code 是以暴力方式完成，且不少 judge 使用這方法也可 AC，不會 time out。

#include <stdio.h>
int main()
{
    int n, i, s;
    while(scanf("%d",&n)==1){
        for(s=0, i=1; i<n; ++i)
            if(n%i==0) s+=i;
        if(s>n) puts("盈數");
        else if(s<n) puts("虧數");
        else puts("完全數");
    }
    return 0;
}

一點點思考

我們以 28 為例，在前面用 2 判斷是其因數時，實際上一定也會有另一個因數存在 < 因數必是成對 >，

像 28 便可拆成 (1, 28) , (2, 14) , (4, 7) ，這方法只要拆到 28 之根號即可。

這方法有二個地方要注意，1本身是虧數，要額外判斷；

還有若為完全平方數時，也要再額外考量。

#include <stdio.h>
#include <math.h>
int main()
{
    int n, i, s, end;
    while(scanf("%d",&n)==1){
        if(n==1) {
            puts("虧數");
            continue;
        }

        end = ceil(sqrt(n));
        for(s=1, i=2; i<end; ++i)
            if(n%i==0) s+=i, s+=(n/i);
        if(end*end==n) s+=end;

        if(s>n) puts("盈數");
        else if(s<n) puts("虧數");
        else puts("完全數");
    }
    return 0;
}

一點點數學

這些題目可經由數學推導出來 < 聽說是小六數學 ，但筆者沒印象 >，

假設質因數分解出來結果為  N = a^x * b^y * c^z

(1) 正因數個數 = (x+1) * (y+1) * (z+1)

(2) 正因數總合 = ( a^0 + a^1 + .... + a^x) * (b^0 + b^1 + ... + b^y) * (c^0 + c^1 + ... + c^z)。

以 28 為例，

28 = 2^2 * 7^1

(1) 正因數個數 = (2+1) * (1+1) = 6 。

(2) 正因數總合 = (2^0 + 2^1 + 2^2) * (7^0 + 7^1) = 7 * 8 = 56。

注意到上面的「個數」和「總合」，都是含 0 與數本身。

若拿來應用於完全數之判斷，程式上會在數字較大時稍佔上風。