如何檢查號碼完美度

一、簡介

完美數是一種特殊類型的正整數，它具有獨特的屬性，因為它等於其真因數之和，不包括數字本身。

完美數最有趣的方面之一是它們的稀有性。完美數在整數領域內並不常見。事實上，縱觀歷史，只有少數完美數被確定。人類已知的前四個完全數是 6、28、496 和 8128。

在本文中，我們將深入研究完美數的概念，並探索各種方法來檢查給定的數字是否屬於這個有趣的類別。

2. 理解完美數

讓我們檢查前幾個例子來掌握完全數的概念。例如，數字 6 的真因數為 1、2 和 3。將這些因數相加得出 1 + 2 + 3 = 6，使 6 成為完美數。同樣，數字 28 有真因數 1、2、4、7 和 14，它們的和等於 1 + 2 + 4 + 7 + 14 = 28。因此，28 是另一個完全數。

我們可以採用不同的方法來確定給定的數字是否完美。讓我們探討三種常見的方法。

3. 暴力法

檢查完美性的一種方法是迭代該數字的所有可能的除數並對它們求和。如果總和等於數字本身，我們就有一個完美的數字。此方法可以使用從1遍歷到n/2的循環來實現，其中n是給定的數字。對於找到的每個除數，我們累加總和。最後，我們將總和與原始數字進行比較以確定是否完美：

public static boolean isPerfectBruteForce(int number) {
 int sum = 0;
 for (int i = 1; i <= number / 2; i++) {
 if (number % i == 0) {
 sum += i;
 }
 }
 return sum == number;
 }

選擇迭代到n/2是基於這樣的觀察：數字 n 的最大可能真因數（不包括 n 本身）是n/2 。大於n/2除數將導致商數小於2 ，這不被視為真除數。這種方法確保我們有效地覆蓋所有必要的除數。

暴力法迭代從1到n/2的所有可能的除數併計算總和。時間複雜度與輸入數量成線性關係。

4. 基於流的方法

我們也可以利用 Java Streams 來檢查完美數。在此方法中，我們產生從2到被測試數字的平方根（向下捨去）的除數流，過濾整除該數字的除數，然後透過將每個除數及其對應的對（ number/test相加來計算總和number/test ）。最後，我們將總和與原始數字進行比較以確定是否完美：

public static boolean isPerfectStream(int number) {
 int sum = IntStream.rangeClosed(2, (int) Math.sqrt(number))
 .filter(test -> number % test == 0)
 .reduce(1, (s, test) -> s + test + (number / test));
 return sum == number;
 }

當搜尋一個數字的約數時，一旦達到該數字的平方根，我們就可以停止迭代。這是因為因素總是成對出現的。例如，如果a是number的約數，則b = number/a也是約數。如果a小於或等於該number的平方根，則b將大於或等於該number的平方根。因此，透過求除數到平方根，我們已經涵蓋了所有可能的因素。

基於流的方法使用 Java Streams 來過濾除數並將其求和至number的平方根。透過只循環到平方根，我們可以減少求除數所需的工作量並提高效率。與先前的嘗試相比，這種最佳化方法顯著減少了執行時間，使其成為檢查完美數字的更有效的解決方案。

5.歐幾裡得-歐拉定理

一種基於歐幾里德-歐拉定理的更有效方法使我們能夠識別完美數，而無需迭代所有可能的除數。根據定理，若2^(p-1) * (2^p – 1)是質數，則(2^p – 1) * 2^(p-1)是完全數。這裡，p必須是質數。透過利用該定理，我們可以專注於根據公式計算完美數。這種方法使我們能夠有效地識別完美數，而無需迭代所有可能的除數或明確查找質數：

public static boolean isPerfectEuclidEuler(int number) {
 int p = 2;
 int perfectNumber = (int) (Math.pow(2, p - 1) * (Math.pow(2, p) - 1));
 while (perfectNumber <= number) {
 if (perfectNumber == number) {
 return true;
 }
 p++;
 perfectNumber = (int) (Math.pow(2, p - 1) * (Math.pow(2, p) - 1));
 }
 return false;
 }

歐幾里德-歐拉定理方法利用質數並根據該定理計算完美數。 Euclid-Euler 方法的時間複雜度優於暴力破解和基於流的方法，因為它只需要檢查log n.

雖然時間複雜度比暴力破解和基於Stream的方法要好，但是我們提供的Euclid-Euler方法的執行時間可能達不到預期。造成這種性能不佳的原因之一是使用了Math.pow() ，它以其速度慢而聞名。考慮到我們只計算以2為底的冪，我們可以透過使用二進位移位運算而不是Math.pow()來提高效率：

public static boolean isPerfectEuclidEulerUsingShift(int number) {
 int p = 2;
 int perfectNumber = (2 << (p - 1)) * ((2 << p) - 1);
 while (perfectNumber <= number) {
 if (perfectNumber == number) {
 return true;
 }
 p++;
 perfectNumber = (2 << (p - 1)) * ((2 << p) - 1);
 }
 return false;
 }

用二進位移位運算(2 << p)取代Math.pow()來計算2的冪，我們可以實現更快、更有效率的計算。這種最佳化顯著提高了 Euclid-Euler 方法的效能。

六、分析比較

讓我們分析和比較我們提供的三種不同的檢查完美數的方法。

暴力法雖然簡單，但會迭代所有可能的除數並將總和與原始數字進行比較。它適用於較小的數字，但隨著輸入大小的增加，效率會降低。此方法的時間複雜度與輸入數字成線性關係，導致較大數字的執行時間較慢。

基於流的方法透過利用 Java Streams 有效地過濾和求和除數，提供了更簡潔和更具表現力的實作。透過將迭代限制為數字的平方根，減少了不必要的計算和迭代，提高了效率並減少了執行時間。基於流的方法在簡單性和效率之間取得了平衡。

歐幾裡得-歐拉定理方法提供了這三種方法中最有效的方法。利用該定理的公式，我們可以直接計算完美數，而無需檢查所有可能的除數。該方法顯著減少了計算量並實現了顯著的效率。它對於大數特別有效，因為它避免了迭代多個除數。

為了比較這些方法的效能，我們使用 JMH 進行了基準測試，JMH 是 Java 程式微基準測試的常用工具。此基準測試是使用已知的完美數（特別是33550336執行的。基準測試的結果是：

Benchmark Mode Cnt Score Error Units
 PerfectNumberBenchmark.bruteForceBenchmark thrpt 5 55.070 ± 2.674 ops/s
 PerfectNumberBenchmark.streamBenchmark thrpt 5 96114.246 ± 3666.451 ops/s
 PerfectNumberBenchmark.euclidEulerBenchmark thrpt 5 144639.676 ± 3409.540 ops/s
 PerfectNumberBenchmark.euclidEulerUsingShiftBenchmark thrpt 5 99191865.954 ± 5924410.475 ops/s

“Cnt”列表示每個基準模式執行的迭代次數。 “分數”列表示每個基準測試實現的吞吐量或每秒操作數。它指示特定操作或演算法在一秒鐘內執行的頻率。 「誤差」欄位表示與基準測試結果相關的統計誤差。它提供了測量值的變異性或不確定性的估計。誤差越小表示結果越一致可靠。

歐幾裡得-歐拉方法是最有效的方法，其次是基於流的方法。蠻力方法雖然簡單，但效率較低，更適合較小的數量。當處理較大的數字時，建議使用 Euclid-Euler 或基於流的方法以獲得最佳性能。

七、結論

在本文中，我們探討了完美數的迷人概念，並研究了確定給定數字是否屬於此類別的各種方法。

與往常一樣，原始碼可以在 GitHub 上取得。