題目敘述

 

對一個正整數 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 與數本身。

 

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

edisonx 發表在 痞客邦 PIXNET 留言(0) 人氣()