說明
如果有一數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 = (20 + 21 + 22) * (70 + 71)
所以只要求出因式分解，就可以利用迴圈求得等式後面的值，將該值除以2就是真因數和了；等式後面第一眼看時可能想到使用等比級數公式來解，不過會使用到次方運算，可以在迴圈走訪因式分解陣列時，同時計算出等式後面的值，這在下面的實作中可以看到。
#include <stdio.h>
#include <stdlib.h>
#define N 1000
#define P 10000
int prime(int*); // 求質數表
int factor(int*, int, int*); // 求factor
int sum(int*, int); // sum ot proper factor
int main(void) {
int ptable[N+1] = {0}; // 儲存質數表
int fact[N+1] = {0}; // 儲存因式分解結果
int count1 = prime(ptable);
int i;
for(i = 0; i <= P; i++) {
int count2 = factor(ptable, i, fact);
if(i == sum(fact, count2))
printf("Perfect Number: %d\n", i);
}
printf("\n");
return 0;
}
int prime(int* pNum) {
int prime[N+1];
int i, j;
for(i = 2; i <= N; i++)
prime[i] = 1;
for(i = 2; i*i <= N; i++) {
if(prime[i] == 1) {
for(j = 2*i; j <= N; j++) {
if(j % i == 0)
prime[j] = 0;
}
}
}
int k;
for(i = 2, k = 0; i < N; i++) {
if(prime[i] == 1)
pNum[k++] = i;
}
return k;
}
int factor(int* table, int num, int* frecord) {
int i, k;
for(i = 0, k = 0; table[i] * table[i] <= num;) {
if(num % table[i] == 0) {
frecord[k] = table[i];
k++;
num /= table[i];
}
else
i++;
}
frecord[k] = num;
return k + 1;
}
int sum(int* farr, int c) {
int i = 0;
int r = 1;
int s = 1;
int q = 1;
while(i < c) {
do {
r *= farr[i];
q += r;
i++;
} while(i < c-1 && farr[i-1] == farr[i]);
s *= q;
r = 1;
q = 1;
}
return s / 2;
}
import java.util.*;
public class PerfectNumber {
public static List<Integer> lessThan(int number) {
List<Integer> primes = Prime.findPrimes(number);
List<Integer> list = new ArrayList<Integer>();
for(int i = 1; i <= number; i++) {
if(i == sum(factor(primes, i)))
list.add(i);
}
return list;
}
public static List<Integer> factor(List<Integer> primes, int n) {
int num = n;
List<Integer> list = new ArrayList<Integer>();
for(int i = 0; primes.get(i) <= Math.sqrt(num);) {
if(num % primes.get(i) == 0) {
list.add(primes.get(i));
num /= primes.get(i);
}
else {
i++;
}
}
list.add(num);
return list;
}
private static int sum(List<Integer> factors) {
int s = 1;
int i = 0;
while(i < factors.size()) {
int r = 1;
int q = 1;
do {
r *= factors.get(i);
q += r;
i++;
} while(i < factors.size() - 1 &&
factors.get(i - 1).equals(factors.get(i)));
s *= q;
}
return s / 2;
}
public static void main(String[] args) {
for(Integer number : PerfectNumber.lessThan(1000)) {
System.out.print(number + " ");
}
}
}
from functools import reduce # 未使用質數表
def perfectLessThan(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(perfectLessThan(1000))
def perfectLessThan(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
}
perfectLessThan(1000) foreach(p => print(p + " "))
class Range
def comprehend(&block)
return self if block.nil?
self.collect(&block).compact
end
end
def perfectLessThan(number)
(1..number - 1).comprehend { |i|
i if 2 * i == (1..i).reduce { |sum, k|
i % k == 0 ? sum + k : sum
}
}
end
p perfectLessThan(1000)
|