完美數. December 2, 2021. 如果數字n，真因數（Proper factor）的總和等於n，稱為完美數（Perfect Number），例如以下幾個數都是完美數：. 6 = 1 + 2 + 3.
OPENHOME.CC
常見程式演算
|老掉牙
河內塔
費式數列
巴斯卡三角形
三色旗
老鼠走迷宮
騎士走棋盤
八皇后
八銀幣
康威生命遊戲
字串比對
背包問題
雙色、三色河內塔
得分排行
|「數」
最大訪客數
Eratosthenes篩選求質數
完美數
阿姆斯壯數
大數運算
指定位數的圓周率
|隨機
蒙地卡羅法求PI
洗牌
Craps賭博遊戲
約瑟夫問題
|組構
排列
格雷碼
子集
k組合
因數分解
加法因子
|排序
選擇、插入、氣泡排序
Heap排序-改良的選擇排序
Shell排序-改良的插入排序
Shaker排序-改良的氣泡排序
快速排序（一）
快速排序（二）
合併排序
基數排序
|搜尋
線性搜尋
二分搜尋
插補搜尋
費氏搜尋
|矩陣
稀疏矩陣
多維矩陣降維
上／下三角、對稱矩陣
奇數魔方陣
4N魔方陣
2(2N+1)魔方陣
|運算
中序式轉後序式
後序式運算
Quine
GitHub
Twitter
Facebook
LinkedIn
Designs
Tags
BuiltwithbyHugo
HOME>
常見程式演算>
「數」>
完美數
解法思路
程式實作：
perfectnumber
primenumber
factoring
C
Java
Python
Scala
Ruby
JavaScript
Haskell
完美數
December2,2021
如果數字n，真因數（Properfactor）的總和等於n，稱為完美數（PerfectNumber），例如以下幾個數都是完美數：
6=1+2+3
28=1+2+4+7+14
496=1+2+4+8+16+31+62+124+248
第一眼看到時，會想到使用迴圈求出全部真因數，再進一步求因數和，不過若n值很大，會花費許多時間在迴圈測試上，十分沒有效率。
解法思路
如何求小於n的全部完美數？並將程式寫的有效率？基本上有三個步驟：
建立質數表。
利用質數表求指定數的因式分解。
利用因式分解求全部真因數和，並檢查是否為完美數。
步驟1與2在〈Eratosthenes篩選求質數〉與〈因數分解〉已經討論過，問題在步驟3，如何求真因數和？首先要知道將全部真因數和加上該數本身，會等於該數的兩倍，例如：
2*28=1+2+4+7+14+28
等式後面可以化為：
2*28=(2⁰+2¹+2²)*(7⁰+7¹)
只要求出因式分解，就可以利用迴圈求得等式後面的值，將該值除以2就是真因數和；等式後面第一眼看時可能想到使用等比級數公式來解，不過會使用到次方運算，可以在迴圈走訪因式分解陣列時，同時計算出等式後面的值。
程式實作：
C
Java
Python
Scala
Ruby
JavaScript
Haskell
#include
#include
#defineP10000
#defineN5000
voidcreate(int*);//建立質數表
voidfilter(int*,int);
voidfactor(int,int*,int*);//因數分解
intisPerfect(int,int*);//判斷完美數
intmain(void){
intprimes[N+1]={0};
create(primes);
inti;
for(i=2;i<=P;i++)if(isPerfect(i,primes)){
printf("PerfectNumber%5d\n",i);
}
return0;
}
voidcreate(int*primes){
primes[2]=primes[3]=primes[5]=1;
inti;
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;}
intn;
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);}
}
voidfilter(int*primes,inti){
if(primes[i]){
intj;
for(j=2;j*i<=N;j++){
primes[j*i]=0;
}
}
}
voidfactor(intnum,int*factors,int*primes){
inti,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;
}
intisPerfect(intnum,int*primes){
intfactors[N/2+1]={0};
factor(num,factors,primes);
ints=1;
inti=0;
while(factors[i]!=0){
intr=1;
intq=1;
do{
r*=factors[i];
q+=r;
i++;
}while(factors[i-1]==factors[i]);
s*=q;
}
returns/2==num;
}
//使用Eratosthenes篩選求質數中的Prime
//使用因數分解中的Factor
importjava.util.*;
publicclassPerfect{
publicstaticListperfectLe(intn){
Listprimes=Prime.create(n/2);
Listperfects=newArrayList<>();
for(inti=2;i<=n;i++)if(isPerfect(i,primes)){
perfects.add(i);
}
returnperfects;
}
publicstaticbooleanisPerfect(intnum,Listprimes){
Listfactors=Factor.factor(num,primes);
factors.add(0);
ints=1;
inti=0;
while(factors.get(i)!=0){
intr=1;
intq=1;
do{
r*=factors.get(i);
q+=r;
i++;
}while(factors.get(i-1).equals(factors.get(i)));
s*=q;
}
returns/2==num;
}
publicstaticvoidmain(String[]args){
for(Integern:perfectLe(100000)){
System.out.printf("Perfectnumber%5d%n",n);
}
}
}
fromfunctoolsimportreduce#未使用質數表
defperfectLe(number):
return[iforiinrange(1,number)if2*i==reduce(\
lambdasum,k:sum+kifi%k==0elsesum,range(1,i+1))]
print(perfectLe(10000))
defperfectLe(number:Int)={//未使用質數表
for(
iif(i%k==0)sum+kelsesum}
)yieldi
}
perfectLe(10000)foreach(p=>print(p+""))
classRange
defcomprehend(&block)
returnselfifblock.nil?
self.collect(&block).compact
end
end
defperfectLe(number)
(1..number-1).comprehend{|i|
iif2*i==(1..i).reduce{|sum,k|i%k==0?sum+k:sum}
}
end
pperfectLe(10000)
functionrange(start,end){
varr=[];
varn=start;
for(vari=0;nifi`mod`k==0thens+kelses)[1..i])]
main=print$perfectLe10000
