完美數

說明

如果有一數n，其真因數（Proper factor）的總和等於n，則稱之為完美數（Perfect Number），例如以下幾個數都是完美數：

6 = 1 + 2 + 3
28 = 1 + 2 + 4 + 7 + 14
496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248

程式基本上不難，第一眼看到時會想到使用迴圈求出所有真因數，再進一步求因數和，不過若n值很大，則此法會花費許多時間在迴圈測試上，十分沒有效率，例如求小於10000的所有完美數。

解法

如何求小於10000的所有完美數？並將程式寫的有效率？基本上有三個步驟：

求出一定數目的質數表
利用質數表求指定數的因式分解
利用因式分解求所有真因數和，並檢查是否為完美數

步驟一與步驟二在之前討論過了，問題在步驟三，如何求真因數和？方法很簡單，要先知道將所有真因數和加上該數本身，會等於該數的兩倍，例如：

2 * 28 = 1 + 2 + 4 + 7 + 14 + 28

等式後面可以化為：

2 * 28 = (2⁰ + 2¹ + 2²) * (7⁰ + 7¹)

所以只要求出因式分解，就可以利用迴圈求得等式後面的值，將該值除以2就是真因數和了；等式後面第一眼看時可能想到使用等比級數公式來解，不過會使用到次方運算，可以在迴圈走訪因式分解陣列時，同時計算出等式後面的值，這在下面的實作中可以看到。

實作：C Java Python Scala Ruby JavaScript Haskell

#include <stdio.h> 
#include <stdlib.h> 

#define P 10000
#define N 5000

void create(int*);             // 建立質數表
void filter(int*, int);
void factor(int, int*, int*);  // 因數分解
int isPerfect(int, int*);      // 判斷完美數

int main(void) { 
    int primes[N + 1] = {0};
    create(primes);
    
    int i;
    for(i = 2; i <= P; i++) if(isPerfect(i, primes)) {
        printf("Perfect Number%5d\n", i);         
    }

    return 0; 
} 

void create(int* primes) {
    primes[2] = primes[3] = primes[5] = 1;
    
    int i;
    for(i = 1;6 * i + 5 <= N; i++) {
        primes[6 * i + 1] = primes[6 * i + 5] = 1; 
    }
    if(6 * i + 1 <= N) { primes[6 * i + 1] = 1; }
    
    int n;
    for(n = 0;(6 * n + 5) * (6 * n + 5) <= N; n++) {
        filter(primes, 6 * n + 1);
        filter(primes, 6 * n + 5);
    }     
    if((6 * n + 1) * (6 * n + 1) <= N) { filter(primes, 6 * n + 1); }  
}

void filter(int* primes, int i) {
    if(primes[i]) { 
        int j;
        for(j = 2; j * i <= N; j++) {
            primes[j * i] = 0; 
        }
    }
}

void factor(int num, int* factors, int* primes) { 
    int i, j;
    for(i = 2, j = 0; i * i <= num;) if(primes[i] && num % i == 0) {
        factors[j++] = i;
        num /= i;
    } else { i++; }
    factors[j] = num;
}

int isPerfect(int num, int* primes) {  
    int factors[N / 2 + 1] = {0};
    factor(num, factors, primes); 

    int s = 1; 
    int i = 0;
    while(factors[i] != 0) { 
        int r = 1; 
        int q = 1;
        do { 
            r *= factors[i]; 
            q += r; 
            i++; 
        } while(factors[i - 1] == factors[i]); 
        s *= q;
    } 
    
    return s / 2 == num; 
}

Java

// 使用 Eratosthenes 篩選求質數 中的 Prime
// 使用 因數分解 中的 Factor 

import java.util.*;

public class Perfect {
    public static List<Integer> perfectLe(int n) {
         List<Integer> primes = Prime.create(n / 2);
         List<Integer> perfects = new ArrayList<>();
         for(int i = 2; i <= n; i++) if(isPerfect(i, primes)) {
             perfects.add(i);
         }
         return perfects;
    }
    
    public static boolean isPerfect(int num, List<Integer> primes) {  
        List<Integer> factors = Factor.factor(num, primes);
        factors.add(0);
        
        int s = 1; 
        int i = 0;
        while(factors.get(i) != 0) { 
            int r = 1; 
            int q = 1;
            do { 
                r *= factors.get(i); 
                q += r; 
                i++;
            } while(factors.get(i - 1).equals(factors.get(i))); 
            s *= q; 
        }   

        return s / 2 == num; 
    }

    
    public static void main(String[] args) {
        for(Integer n : perfectLe(100000)) {
            System.out.printf("Perfect number %5d%n", n);
        }
    }
}

Python

from functools import reduce # 未使用質數表
def perfectLe(number):
    return [i for i in range(1, number) if 2 * i == reduce( \
            lambda sum, k: sum + k if i % k == 0 else sum, range(1, i + 1))]
print(perfectLe(10000))

Scala

def perfectLe(number: Int) = { // 未使用質數表
  for(
    i <- 1 to number
    if 2 * i == (0 /: (1 to i)){(sum, k) => if(i % k == 0) sum + k else sum}
  ) yield i
}
perfectLe(10000) foreach(p => print(p + " "))

Ruby

class Range
    def comprehend(&block)
        return self if block.nil?
        self.collect(&block).compact
    end
end

def perfectLe(number)
    (1..number - 1).comprehend { |i|
        i if 2 * i == (1..i).reduce { |sum, k| i % k == 0 ? sum + k : sum }
    }
end

p perfectLe(10000)

JavaScript

function range(start, end) {
    var r = [];
    var n = start;
    for(var i = 0; n < end; i++, n++) { r[i] = n; }
    return r;
}

function perfectLe(number) {
    return range(1, number).map(function(i) {
        var r = range(1, i + 1);
        var sum = r[0];
        for(var j = 1; j < r.length; j++) {
            sum = i % r[j] === 0 ? sum + r[j] : sum;
        }
        if(2 * i === sum) { return i; }
    }).filter(function(elem) { return elem !== undefined; });
}

print(perfectLe(10000));

Haskell

perfectLe number = 
    [i | i <- [1..number - 1], (2 * i) == 
        (foldl1 (\s k -> if i `mod` k == 0 then s + k else s) [1..i])]

main = print \$ perfectLe 10000