題目連結: Perfect Number

題目描述為: 給定一個整數 n, 要判斷是否為完美數。
其中完美數定義為除了本身以外的所有因數和=自己本身。
題目有補充說明 n 的大小不超過 10^8。

例子 1: n=28,output=true。 (28=1+2+4+7+14)

思路 1: 按照定義判斷

設輸入的數字為 N，且 N>0。 我們可以求出所有 N 的因數，並累加起來，最後判斷是否滿足完美數要求。

• 複雜度評估
  當輸入的數為 N 時，我們至多需要判斷 $\sqrt{N}$ 次，時間複雜度為 $O(\sqrt{N})$。
  此方法只用了常數量變數，與 N 無關，空間複雜度為 O(1)。

參考程式碼

func checkPerfectNumber(num int) bool {
    
    if num<=1{
        return false
    }
    
    
    sum:=1
    tmp:=0
    
    for i:=2;i*i<num;i++{
        if num%i==0{
            
            sum+=i
            tmp=num/i
            if tmp!=i{
                 sum+=tmp
            }
           
            if sum>num{
                return false
            }
        }
        
    }
  
    
    if sum!=num{
        return false
    }
    
    return true
    
}

小結:

方法 1 按照完美數定義處理此問題。此外，要判斷一個數字是否為完美數尚可利用一些數學性質。
而在題目限定範圍內的完美數總共只有 6,8,496,8128,33550336 共 5 個。
我將解法加上簡單的測試，上傳程式碼到此。

補充:

數學上專門研究整數性質的分支為數論，關於質數的研究也非常豐富，在密碼學上也有諸多應用。
而質數定理描述了質數在自然數中的分布情形，而著名的黎曼猜想即是與質數分布相關的數學問題之一。

鐵人賽結語:

這系列挑選的題目偏向數學相關，是出自個人偏好，在此活動中我們也介紹了許多主題如: 複雜度/Hash法/遞迴/bit operation/tree/in-place/...等等，並安排了數道同類型的題目來練習。而最後一天選擇該主題做為一個 perfect ending，在過程中收穫很多，有機會也會繼續嘗試。