主題

LeetCode - 507. Perfect Number 解題心得

Not In My Back Yard | 2020-11-08 00:00:02

題目連結:


題目意譯:
一個完美數為一個正整數滿足自身的因數(除了自己本身的值以外)之和等於自身之值。整數 x 的一個因數為可以整除 x 的一個整數。

給定一整數 n ,如果 n 是一個完美數則回傳真(True);反之,回傳假(False)。

限制:
1 ≦ num ≦ 10 ^ 8



範例測資:
範例 1:
輸入: num = 28
輸出: true
解釋: 28 = 1 + 2 + 4 + 7 + 14
1, 2, 4, 7, and 14 are all divisors of 28.

範例 2:
輸入: num = 6
輸出: true

範例 3:
輸入: num = 496
輸出: true

範例 4:
輸入: num = 8128
輸出: true

範例 5:
輸入: num = 2
輸出: false


解題思維:
定義一個變數 sums (初始值為 0)代表因數和。而我們有至少以下兩個方式可以在 O(sqrt(num)) 之內求得因數和,其中 sqrt() 代表取平方根。

一:
從 i = 1 開始,一路跑到 i = floor(sqrt(num)) (即 num 的平方根取整數部分),期間判斷每個 i 值是否可以整除 num 。如果可以的話,代表 i 和 num ÷ i 是 num 的因數,則 sums 要加上 i 值以及 num ÷ i 之值(除非 i = sqrt(num),此時只需要加 i 值)。

二:
i 從 2 跑到 floor(sqrt(num)) ,沿途判斷 i 能否整除 num 。但是這次我們要將 num 一直除以 i ,除到無法被 i 整除為止(所以可以看到此時 i 值應為一個質數),期間統計我們除了多少次。因此我們可以將 num 轉為 P1 ^ C1 × P2 ^ C2 × …… 的質因數分解表達式,其中 P1 、 P2 、…… 為質數,C1 、 C2 、 …… 為非負整數純量。

而因數和 sums 即為
(1 + P1 + P1 ^ 2 + …… + P1 ^ C1)(1 + P2 + P2 ^ 2 + …… + P2 ^ C2)……
因為上式展開後可以得到所有的因數。


求得因數和 sums 後,判斷 sums 是否等於 2 × num (因為完美數是自己之外的因數和等於自己,其等價於因數和等於兩倍的自己)。如果是就代表 num 是完美數;反之則不是。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
50 巴幣: 2

相關創作

更多創作