[C/C++ 演算法]- 完美數

[C/C++ 演算法]- 完美數

剛才找資料時發現一個C/C++的教學網站，趕快發揮(C/P)的長才將它備份來，有需要的同好，歡迎來(C/P)一下^^。

拷貝來源：
http://openhome.cc/Gossip/AlgorithmGossip/
http://openhome.cc/Gossip/AlgorithmGossip/PerfectNumber.htm

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