# 完全數

December 2, 2021

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 = (2⁰ + 2¹ + 2²) * (7⁰ + 7¹)

## 程式實作：

``````#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;
}
``````
``````// 使用 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)) {
}
return perfects;
}

public static boolean isPerfect(int num, List<Integer> primes) {
List<Integer> factors = Factor.factor(num, primes);

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);
}
}
}
``````
``````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))
``````
``````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 + " "))
``````
``````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)
``````
``````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
``````