A perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. A divisor of an integer x is an integer that can divide x evenly.
Given an integer n, return true if n is a perfect number, otherwise return false.
public class Solution {
public bool CheckPerfectNumber(int num) {
if(num == 1) //數字本身不能當作因數
{
return false;
}
int sum = 0;
for(int i =1; i<num;i++)
{
if(num%i ==0) //餘數為0,即為因數
{
sum+=i;
}
}
return num == sum;
}
}
看起來確實挺簡單的,一路從 1 跑到 num-1的地方,要是有就加入sum
測試範例執行起來也都沒有問題,那我們提交看看
天啊!居然跑得超過時間限制了
看了看數字 : 99999997 ,總共幾個9我都數不清了
方案2 – 修正版 ➡ 跑到根號 num 就好
這時讓我們倒退一下,回來思考一下概念
一個數字 x 要是有因數,一定可以寫成 a * b ➔ 因數 * 另一個數
就題目看來 1 也算的話,應該任意正整數都能寫成 a * b
這時候我們來想一下如何找到距離最近的a 跟 b呢
直接 x 除2嗎 ?
以 36 為例 ➔ 因數可得到 : 1、2、3、4、6、9、12、18
1 跟 36 ➔ 差為 35,36 甚至不能算在因數裡
2 跟 18 ➔ 差為 16
…
6 跟 6 ➔ 差為 0
省略列出每一個,大家可以得到 6
以此類推,大家應該可以得到任意數 x 距離最近的因數 a 跟 b ,就會是 x1/2 ,也就是根號 x
這時,大家疑惑的點可能變成,這個數字可以做什麼呢?
大家這時來想想
要是 a 小於等於 根號 x , b是不是就一定會大於等於 根號 x 呢?
好像是的吧?
那這時候要是我們的遞迴只跑到 根號 x 如何
反正我們能得到 a的時候,也可以用 x / a 得到 對應的 b
事不遲疑,我們把遞迴的限制改一下
public class Solution {
public bool CheckPerfectNumber(int num) {
if(num == 1)
{
return false;
}
int sum = 1;
//int max = (int)Math.Sqrt(num); //上下兩句都是取根號的方法,開心用哪個都可以
int max = (int)Math.Pow(num,0.5);
for(int i =2; i<=max;i++)
{
if(num%i ==0)
{
sum+= i + num/i; //文中提到的 a 跟 b
}
}
return num == sum;
}
}
程式碼幾乎相同,只有改了兩個小地方
i 的Limit (本來要跑到 num-1,現在只要跑到 num1/2)
加總的多加了 【num ÷ i】
這時我們提交看看改過的程式
可以看到運行時間還算不錯,超過了7成左右的C# 提交
Java解決方案
方案1 – 遞迴跑到根號 num 就好
class Solution {
public boolean checkPerfectNumber(int num) {
if(num == 1)
{
return false;
}
int sum = 1;
//int max = (int)Math.sqrt(num); //上下兩句都是取根號的方法,開心用哪個都可以
int max = (int)Math.pow(num,0.5);
for(int i =2; i<=max;i++)
{
if(num%i ==0)
{
sum+= i + num/i;
}
}
return num == sum;
}
}
Python3 解決方案
方案1 – 遞迴跑到根號 num 就好
class Solution:
def checkPerfectNumber(self, num: int) -> bool:
if num == 1:
return False
sum = 1;
#max = math.ceil(math.sqrt(num)) #上下兩句都是取根號的方法,開心用哪個都可以
max = math.ceil(num**0.5)
for i in range(2,max):
if num%i ==0:
sum+= i + num/i
return num == sum
JavaScript 解決方案
方案1
/**
* @param {number} num
* @return {boolean}
*/
var checkPerfectNumber = function(num) {
if(num == 1)
{
return false;
}
var sum = 1;
//var max = parseInt(Math.sqrt(num)); //上下兩句都是取根號的方法,開心用哪個都可以
var max = parseInt(Math.pow(num,0.5));
for(let i =2; i<=max;i++)
{
if(num%i ==0)
{
sum+= i + num/i;
}
}
return num == sum;
};
結論
這一題的兩個答案,相當明確的指出就算是相同的寫法,要是建立在不同的前提上會有多少的差別
故寫程式除了對程式本身的優化外,邏輯也是非常重要的
"If everything was perfect, you would never learn and you would never grow."
Beyonce Knowles
ai_front = {"insertion_before":"BEFORE","insertion_after":"AFTER","insertion_prepend":"PREPEND CONTENT","insertion_append":"APPEND CONTENT","insertion_replace_content":"REPLACE CONTENT","insertion_replace_element":"REPLACE ELEMENT","visible":"VISIBLE","hidden":"HIDDEN","fallback":"FALLBACK","automatically_placed":"Automatically placed by AdSense Auto ads code","cancel":"Cancel","use":"Use","add":"Add","parent":"Parent","cancel_element_selection":"Cancel element selection","select_parent_element":"Select parent element","css_selector":"CSS selector","use_current_selector":"Use current selector","element":"ELEMENT","path":"PATH","selector":"SELECTOR"};