C 經典演算法題完美數 - w3c學習教程

C 經典演算法題完美數,如果有一數n，其真因數proper factor 的總和等於n，則稱之為完美數perfect number ， 例如以下幾個數都是完美數. C經典演算法題完美數 2021-10-0206:18:13字數1759閱讀1398 如果有一數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值很大，則此法會花費許多時間在迴圈測試上，十分沒有效率，例如求小於10000的所有完美數。

如何求小於10000的所有完美數？並將程式寫的有效率？基本上有三個步驟： 求出一定數目的質數表 利用質數表求指定數的因式分解 利用因式分解求所有真因數和，並檢查是否為完美數 步驟一與步驟二在之前討論過了，問題在步驟三，如何求真因數和？方法很簡單，要先知道將所有真因數和加上該數本身，會等於該數的兩倍，例如： 2*28=1+2+4+7+14+28 等式後面可以化為： 2*28=(20+21+22)*(70+71) 所以只要求出因式分解，就可以利用迴圈求得等式後面的值，將該值除以2就是真因數和了；等式後面第一眼看時可能想到使用等比級數公式來解，不過會使用到次方運算，可以在迴圈走訪因式分解陣列時，同時計算出等式後面的值，這在下面的實作中可以看到。

#include #include #definen1000 #definep10000 intprime (int*) ;//求質數表 intfactor (int*, int, int*); //求factor intfsum (int*, int) ;//sumotproperfactor intmain (void); //儲存質數表 intfact[n+1] =;//儲存因式分解結果 intcount1,count2,i;count1= prime (ptable) ;for (i= 0;i<=p;i++ )printf ("\n"); return0; }int prime (int *pnum)}} for(i= 2,j= 0;i