標籤：

如何用 C/C++ 求 1 到 1000 內的所有完全數？

01-28

完全數，即該數所有不包括其本身的因子和為該數本身。

這是個小題目，按定義窮舉算是基本的練習，並太多特別值得說的地方。選個合適的語言，也就是一兩行代碼按定義表示出來，比如 Python：

[n for n in range(1, 1000)
if sum(k for k in range(1, n) if n%k == 0) == n]

另一方面這又是個數學題目。可以想見會有人想出一些辦法去做「優化」，卻輕視編程碼代碼之前的數學與演算法上的分析。實際上，如果未經深思熟慮，這類優化能起到的效果甚微，在本質上不能減少多少運算。因此，倒不如仔細從數學角度好好看看這個問題，給出一個完全不一樣的演算法，或許會讓這個原本不起眼的小題目吃起來更有嚼頭一些。

---

由 Euclid-Euler 定理，一個數 n 是偶完全數，當且僅當n = 2^{k-1} (2^k - 1)，其中 2^k - 1 是一個梅森素數。

奇完全數是否存在，是當今數論中未解決的問題。但已有文獻指出，奇完全數即使存在，則不小於 10^{1500}，因此在合理範圍內無須考慮。

於是現在問題歸結到求一組較小的 k 使 2^k -1 是梅森素數，然後套用 Euclid-Euler 定理公式計算。

驗證梅森素數的方法，較為有效的是 Lucas–Lehmer 檢驗法。即定義

s_k = egin{cases} 4, k = 0, \ s_{k-1}^2 - 2, k > 0.<br /> end{cases}

從而 M_k = 2^k - 1 是素數當且僅當

s_{k-2} equiv 0 pmod {M_k}

其中 k 是奇數，由梅森素數的性質，等價於 k 是奇素數。k 為偶數 2 則是特殊情形，M_2 = 3 是素數。

為方便計算，事實上並不需要求出所有的 s_k，只要求得餘數即可（否則中間結果會很大）。而這個條件用計算機非常容易驗證。

由於只要求 1000 以內的完全數，因此用 n 的表達式粗略地估計，最多只要求出 1000 以內的梅森素數。注意到 2 的 10 次方即超出 1000，因此只需要考慮 k 小於 10 的情形進行驗證。因此這也是很有效的演算法，遠好於用定義試除計算。

下面是代碼：

#include &

inline long mersenne(int k)
{
return (1L &<&< k) - 1L; } // euclid_euler(k) is perfect if mersenne(k) is prime // http://en.wikipedia.org/wiki/Euclid%E2%80%93Euler_theorem inline long euclid_euler(int k) { return ((1L&<&

根據 @劉海洋的答案里提到的 Euclid-Euler 定理寫的:

具體定理可看他的答案

運算將在編譯時完成(真要說也算是優化吧...):

#include &

#define MAXN_NUM 1000

template & class COND&>
struct WHILE;

template & class COND&>
struct WHILE{
template & class F&>
struct BODY{
inline static void EXECUTE(){
struct DO_NOTING{
inline static void EXECUTE(){}
};
IF&::VALUE, F&, DO_NOTING&>::VALUETYPE::EXECUTE();
IF&::VALUE, WHILE&::BODY&, DO_NOTING&>::VALUETYPE::EXECUTE();
}
};
};

template &
struct IF;

template &
struct IF &< true, THEN, ELSE &> {
typedef THEN VALUETYPE;
};

template &
struct IF &< false, THEN, ELSE &> {
typedef ELSE VALUETYPE;
};

template &
struct INTEGER{
static const int VALUE = N;
};

template &
struct BOOL{
static const bool VALUE = N;
};

template &
struct MERSENNE{
static const int VALUE = (1 &<&< N)-1; }; template &
struct EUCLID_EULER{
static const int VALUE = ((1 &<&< N) - 1)&<&<(N-1); }; template &
struct EUCLID_EULER_LESS_THAN{
template &
struct BODY{
static const bool VALUE = EUCLID_EULER&::VALUE &< N; }; }; template &
struct LUCAS_LEHMER_TEST;

template &<&>
struct LUCAS_LEHMER_TEST &< 2 &> {
static const bool VALUE = true;
};

template &
struct LUCAS_LEHMER_TEST{
template &
struct _LUCAS_LEHMER_TEST;

template &<&>
struct _LUCAS_LEHMER_TEST&<0&>{
static const int VALUE = 4;
};

template &
struct _LUCAS_LEHMER_TEST{
static const int VALUE = (_LUCAS_LEHMER_TEST&::VALUE*_LUCAS_LEHMER_TEST&::VALUE - 2) % MERSENNE &< N &>::VALUE;
};
static const bool VALUE = IF&::VALUE == 0&>, BOOL&&>::VALUETYPE::VALUE;
};

template &