# 完美數

## 說明

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

## 解法

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

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

2 * 28 = (20 + 21 + 22) * (70 + 71)

• C
``#include <stdio.h> #include <stdlib.h> #define P 10000#define N 5000void 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    endenddef perfectLe(number)    (1..number - 1).comprehend { |i|        i if 2 * i == (1..i).reduce { |sum, k| i % k == 0 ? sum + k : sum }    }endp 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));``

``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``