#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;
}