藍影

// ============================================

每次在一些程式語言的討論版上都有人請教怎麼寫完美數(也有人翻譯成完全數)

然後接下來就是一堆副函式，其中包含了

(1) 判斷該數 N 的因數有哪些
(2) 將該數所有的因數全都加總起來，看結果是不是 = N

例如:第一個完美數是6，它有因數1、2、3、6，除去它本身6外，其餘3個數相加，1＋2＋3＝6。
       第二個完美數是28，它有因數1、2、4、7、14、28，除去它本身28外，其餘5個數相加，1＋2＋4+7+ 14＝28。

目前完全數仍沒有找到一個通用的已經有一些公式可以去求，
所以，要求完全數，大致上還是要用暴力的方式去解，
能改善的，大概也只是求質數上的效率..

// ============================================

古希臘數學家歐幾里得是通過 2ⁿ⁻¹(2ⁿ − 1) 的表達式發現頭四個完全數的。

當 n = 2:   2¹(2² − 1) = 6

當 n = 3:   2²(2³ − 1) = 28

當 n = 5:   2⁴(2⁵ − 1) = 496

當 n = 7:   2⁶(2⁷ − 1) = 8128

歐幾里得證明了：一個偶數是完美數，當且僅當它具有如下形式：2^{n − 1}(2ⁿ − 1)。儘管沒有發現奇完全數，但是當代數學家奧斯丁·歐爾證明，若有奇完全數，則其形式必然是12p + 1或36p + 9的形式，其中p是素數。在10¹⁸以下的自然數中奇完全數是不存在的。

首十個完全數是： 6，28, 496, 8128, 33550336(8位), 8589869056(10位), 137438691328(12位), 2305843008139952128(19位),2658455991569831744654692615953842176(38位)及 191561942608236107294793378084303638130997321548169216(55位)

(以上節錄自 wiki 百科  )
// ============================================

注意，以上的說明是指 "前四個" 完美數，並不代表所有的完美數都可以這麼帶，

如果你把 n 從 2 帶到 10 的話，你得到的結果會是

6
28
120
496
2016
8128
32640
130816
523776

但裡面有一狗票都不屬於完美數

以下的 code 是使用 "暴力破解法" 找完美數的方法

// ====================================
// FileName: PerfectNumber1.cpp
// Author  : Edison.Shih.
// Complier: VC 2008

#include <stdio.h>
#include <time.h>
#define FACTOR_MAX        100
#define FIND_MAX        (unsigned long)(~0x00)

unsigned long factor[FACTOR_MAX]; // 存放因數

// ====================================
// IsPerfectNumber()
unsigned IsPerfectNumber(unsigned long n){
        unsigned long i=0;
       
        unsigned long factor_cnt = 0;
        unsigned long sum=0;

        for(i=1; i<n; i++){
                if(n%i==0) factor[factor_cnt++] = i; //, printf("%lu:%lu\n", n, i);
        }
        for(i=0; i<factor_cnt; i++){
                sum += factor[i];       
        }

        if(sum == n) return factor_cnt; // 是完美數，傳回因數個數
        else return -1; // 不是完美數，傳回 -1
}

// ====================================
// main function
int main(int argc, char **argv)
{
        unsigned long i=2;
        unsigned long j=0;
        unsigned factor_cnt = 0;

        clock_t t1, t2;

        t1 = clock();
        for(i=2; i!=FIND_MAX; i++){
                factor_cnt = IsPerfectNumber(i);
                if(factor_cnt!=-1){
                        printf("%lu:", i);
                        for(j=0; j<factor_cnt; j++) printf("%lu ", factor[j]);
                        printf("\n");
                }
        }
        t2 = clock();
        printf("total: %lf secs\n", (double)(t2-t1)/(double)(CLK_TCK));
        return 0;
}
// ====================================

由於我的 FIND_MAX 把它調到最大
所以程式跑起來很久是正常的
有多久？ 我等了二十分鐘就沒耐心等下去了
如果你比我還沒耐心的話，那就把 FIND_MAX 調到小一些吧..

有更快的方式嗎？
有！！   請期待下集吧...