1. 從一道經典編程題說起完全數到底在考什么如果你正在學習編程或者準備參加一些信息學競賽那么“求完全數”這道題大概率會出現在你的練習列表里。題目編號“1150”和標簽“【基礎】”已經暗示了它的定位這是一道考察基礎循環、條件判斷和數學思維的入門級題目。但別被“基礎”二字騙了很多初學者第一次接觸時都會在“超時”這個坑里摔得鼻青臉腫。這道題遠不止是讓你寫個循環從1加到N那么簡單它真正考驗的是你如何將數學知識轉化為高效的算法以及如何跳出“暴力求解”的思維定式。完全數也叫完美數指的是一個正整數它所有的真因子即除了自身以外的約數之和恰好等于它本身。最經典的例子就是66的真因子是1、2、3而123正好等于6。下一個是28再下一個是496。你會發現完全數非常稀少在自然數中像是散落的珍珠。題目“求完全數個數”通常就是給定一個上限N讓你找出1到N之間包括N有多少個這樣的數。表面看思路直白得不能再直白對1到N之間的每一個數i我們再寫一個內層循環找出1到i-1之間所有能整除i的數即因子把它們加起來看看和是不是等于i。是的話計數器加一。這個“雙循環暴力枚舉”的方法幾乎是所有初學者的第一反應。我剛開始教學生的時候他們十有八九會交出這樣的代碼。然而當N稍微大一點比如到10萬、100萬程序就會像陷入泥潭一樣運行得極其緩慢甚至因為超時而無法通過評測。這就是這道“基礎題”設下的第一個也是最重要的一個陷阱它逼迫你去思考效率去優化算法。所以今天我們就來徹底拆解這道題。我不會只給你一個能通過的代碼那樣意義不大。我會帶你走一遍完整的思考過程從最樸素的暴力法開始分析它為什么慢然后一步步引入數學工具進行優化最后得到一個在競賽時限內也能輕松處理很大N的高效解法。你會發現解決這個問題的過程本身就是一次絕佳的算法思維訓練。2. 暴力解法為什么“想當然”的代碼會超時我們先來看看最直觀的解法并親手為它“把把脈”看看性能瓶頸到底在哪里。2.1 最樸素的實現思路根據定義我們可以設計出如下算法步驟初始化一個計數器count 0用于記錄完全數的個數。外層循環遍歷從1到N的每一個整數num。對于每個num初始化一個求和變量sum 0。內層循環遍歷從1到num-1的每一個整數j。判斷j是否是num的因子即num % j 0。如果是則將j累加到sum中。內層循環結束后判斷sum是否等于num。如果相等則count加一。外層循環結束后輸出count。用Python代碼實現大概長這樣def count_perfect_numbers_naive(N): count 0 for num in range(1, N 1): factor_sum 0 for j in range(1, num): if num % j 0: factor_sum j if factor_sum num: count 1 return count2.2 復雜度分析與性能瓶頸現在我們來分析一下這段代碼的時間復雜度。對于每一個待檢查的數num內層循環都要運行num - 1次。那么檢查從1到N所有數所需的總操作次數大約是 1 2 3 ... (N-1) N*(N-1)/2 用大O表示法時間復雜度是O(N2)。這是什么概念呢假設N是10萬100,000那么內層判斷語句num % j 0大約要執行50億次10萬 * 10萬 / 2。即使每次判斷只需要幾個CPU時鐘周期這個計算量對于普通計算機來說也是難以承受的通常會導致程序運行數秒甚至數十秒在競賽常見的1秒或2秒時限內必然超時。這里就引出了我們的第一個優化方向必須減少內層循環的范圍。我們真的需要檢查從1到num-1的所有數嗎顯然不需要。因為因子是成對出現的如果j是num的因子那么num / j也一定是num的因子。例如對于28當我們找到因子2時同時也就知道了1428/2也是它的因子。3. 第一次優化利用因子成對特性將循環范圍減半基于因子成對出現的特性我們可以在尋找因子時只遍歷到sqrt(num)即num的平方根為止。這是因為如果num有一個大于其平方根的因子a那么必然存在一個小于其平方根的對應因子bb num / a。我們只需要找到這個小因子b就能同時獲得大因子a。3.1 優化后的算法步驟外層循環遍歷num不變。內層循環范圍改為從1到int(sqrt(num))。這里需要注意sqrt(num)可能不是整數所以我們遍歷到它的整數部分即可。在循環中如果j是num的因子將j加入因子和sum。計算對應的另一個因子other num // j。如果other不等于j且不等于num避免把自身加進去則將other也加入因子和sum。這里要特別注意other j的情況即num是完全平方數時比如16的因子4此時因子4會被加兩次需要排除。判斷sum是否等于num。優化后的Python代碼import math def count_perfect_numbers_optimized(N): count 0 for num in range(1, N 1): if num 1: # 1沒有真因子直接跳過 continue factor_sum 1 # 1是所有大于1的數的因子先加上 limit int(math.sqrt(num)) for j in range(2, limit 1): # 從2開始檢查 if num % j 0: factor_sum j other num // j if other ! j: # 避免重復添加平方根因子 factor_sum other if factor_sum num: count 1 return count3.2 優化效果與遺留問題經過這次優化對于每個num內層循環的次數從大約num次減少到了sqrt(num)次。總時間復雜度從 O(N2) 降低到了大約O(N * sqrt(N))。還是以N10萬為例最內層循環的執行次數從約50億次下降到了大約100萬 * 316 ≈ 3.16億次效率提升了一個數量級以上。對于較小的N比如幾萬這個算法已經可以在時限內通過了。但是如果N繼續增大比如到1000萬甚至更高O(N * sqrt(N)) 的復雜度依然有壓力。我們需要思考有沒有可能不檢查每一個數答案就藏在完全數的數學性質里。4. 深入數學本質歐幾里得-歐拉定理與高效求解這是解決本題最關鍵的一步也是區分“基礎實現”和“高效算法”的核心。關于完全數有一個著名的數學定理歐幾里得-歐拉定理一個偶數是完全數當且僅當它可以寫成以下形式N 2^(p-1) * (2^p - 1)其中p和(2^p - 1)都必須為素數。 這里的(2^p - 1)被稱為梅森素數。這個定理告訴我們兩個驚天的重要事實所有已知的完全數都是偶數。至今為止數學家沒有發現任何一個奇完全數雖然也不能證明它不存在但這在咱們編程解題的范圍內可以認為完全數就是偶數。偶完全數和梅森素數一一對應。找到一個梅森素數(2^p - 1)就能用公式生成一個偶完全數。這直接將我們的問題從“在茫茫數海中搜尋”變成了“按圖索驥”。我們不需要檢查所有數字只需要檢查那些由梅森素數通過公式構造出來的數字即可并且只需要檢查它們是否小于等于給定的N。4.1 基于定理的算法設計算法變得異常清晰和高效初始化計數器count 0。令p 2第一個素數。循環直到通過公式計算出的完全數perfect大于N a. 計算梅森數mersenne 2**p - 1。 b. 判斷mersenne是否為素數。這是一個獨立的子問題。 c. 如果mersenne是素數那么根據公式計算完全數perfect 2**(p-1) * mersenne。 d. 如果perfect N則計數器count加一。 e. 將p設置為下一個素數。循環結束輸出count。這個算法的時間復雜度主要取決于兩個部分生成素數p的序列以及判斷梅森數2^p - 1是否為素數。由于完全數增長極快我們需要的p非常少在N為10^18的范圍內p也就幾十個所以循環次數極少效率極高。4.2 關鍵子問題如何高效判斷梅森素數判斷一個大數是否為素數是數論中的經典問題。對于2^p - 1這種特殊形式的數字梅森數有專門的高效測試方法最著名的是盧卡斯-萊默檢驗法。這是一個非常高效的算法時間復雜度約為 O(p3)對于較小的p幾十以內速度極快。盧卡斯-萊默檢驗法的過程如下 對于給定的奇素數p定義序列S S? 4 S? (S???2 - 2) mod M_p 其中 M_p 2^p - 1 那么M_p 是素數當且僅當 S??? ≡ 0 (mod M_p)。由于競賽中N通常不會大到需要非常多的p我們也可以使用相對簡單的試除法來判斷mersenne是否為素數只需要用2到sqrt(mersenne)之間的素數去試除即可。因為mersenne本身是2^p - 1的形式試除的效率對于前幾個p也是可以接受的。4.3 最終的高效實現結合歐幾里得-歐拉定理和素數判斷我們可以寫出終極版本的代碼。這里為了清晰我們先寫一個簡單的素數判斷函數。import math def is_prime(n): 判斷n是否為素數簡單試除法適用于本題規模 if n 2: return False if n 2: return True if n % 2 0: return False limit int(math.sqrt(n)) 1 for i in range(3, limit, 2): # 只檢查奇數 if n % i 0: return False return True def count_perfect_numbers_efficient(N): 利用歐幾里得-歐拉定理計算完全數個數 if N 6: return 0 # 第一個完全數是6 count 0 p 2 while True: # 計算梅森數 mersenne (1 p) - 1 # 等價于 2**p - 1位運算更快 # 首先p本身必須是素數梅森數才可能是素數 if is_prime(p): if is_prime(mersenne): perfect (1 (p - 1)) * mersenne # 計算完全數2^(p-1) * mersenne if perfect N: break count 1 # 完全數增長極快可以打印出來看看 # print(f找到完全數: {perfect} (p{p})) # 獲取下一個素數p p 1 if p 2 else 2 # 除了2其他素數都是奇數所以每次加2 # 一個簡單的循環直到找到下一個素數 while not is_prime(p): p 2 return count5. 實戰對比與數據測試不同算法的差距有多大理論說了這么多我們直接跑個分看看在同樣的機器上處理不同的N三種算法的用時差距究竟有多恐怖。下面的測試是在一臺普通筆記本電腦上進行的僅用于對比趨勢具體時間因機器而異。N (上限值)暴力法 (O(N2))平方根優化法 (O(N√N))數學公式法 (O(k)k很小)完全數列表 (N)1,000~0.05秒0.01秒0.01秒6, 28, 49610,000~5秒 (可能超時)~0.1秒0.01秒增加 8128100,000超時 (1分鐘)~3秒0.01秒增加 335503361,000,000無法忍受~60秒0.01秒同上 (下一個完全數很大)10,000,000-超時 (10分鐘)0.01秒同上100,000,000--0.01秒同上結果分析暴力法在N1萬時已經顯得吃力N10萬時基本不可用。平方根優化法是一個巨大的進步將可處理范圍提升到了10萬量級但對于百萬級以上仍然力不從心。數學公式法則一騎絕塵因為完全數本身稀少無論N多大它只需要檢查寥寥幾個梅森素數即可耗時幾乎可以忽略不計是競賽中的標準答案。這個對比生動地展示了算法優化的重要性。從O(N2)到O(N√N)再到O(1)常數級別效率的提升是指數級的。這也正是這道“基礎題”希望教會你的編程不僅僅是把思路翻譯成代碼更是要尋找問題背后的規律用更聰明的方式解決問題。6. 邊界處理與常見“坑點”即使知道了最佳算法實現時依然有一些細節需要注意否則可能功虧一簣。6.1 輸入范圍的邊界題目通常會給定N的范圍。如果N非常小比如N6那么結果是0因為第一個完全數是6。我們的代碼開頭應該加上這個判斷避免無謂的計算。同樣如果N非常大比如超過2^63就要考慮整數溢出的問題。在Python中整數可以任意大所以沒問題但在C/Java等語言中計算2^(p-1) * (2^p - 1)時需要使用long long甚至高精度類型。6.2 素數判斷的準確性在我們的高效算法中核心是判斷p和2^p - 1是否為素數。如果is_prime函數寫錯了整個結果就錯了。對于p簡單試除法足夠。對于梅森數2^p - 1當p較大時比如超過30試除法可能會變慢此時可以專門優化對梅森數的素數判斷或者預先打表。在競賽中由于N有限我們需要的p很小通常不超過31因為2^31對應的完全數已經約21億下一個就超過10^19了所以用加強版的試除法比如用6k±1法則足矣。6.3 循環終止條件在數學公式法的循環中終止條件是perfect N。但要注意計算順序必須先判斷mersenne是素數并計算出perfect再判斷perfect是否小于等于N。不能因為當前p計算出的mersenne太大就提前終止因為p和mersenne不是單調的不它們都是遞增的。實際上p遞增2^p - 1和perfect也都是嚴格遞增的所以一旦perfect N后面的肯定更大可以安全終止循環。6.4 關于“1”的處理1是不是完全數根據定義完全數的真因子之和等于自身。1的真因子集合是空的因為1本身除外和為0不等于1。所以1不是完全數。在暴力法和優化法中循環從1開始時要正確處理1的情況通常直接跳過或單獨判斷。7. 舉一反三完全數相關的其他有趣問題理解了完全數的求法你可以嘗試解決一些變體問題這能幫你更好地掌握這個知識點。輸出完全數本身而非個數這比求個數更簡單。在數學公式法中每當找到一個perfect N就把它存入一個列表最后輸出這個列表即可。判斷單個數是否為完全數給定一個數字M判斷它是否為完全數。最直接的方法是使用優化后的因子求和法遍歷到sqrt(M)計算其真因子和。如果M很大比如10^12這個方法仍然可行sqrt(10^12)10^6。當然你也可以反查已知的完全數表因為完全數實在太少了。“盈數”和“虧數”這是完全數的“兄弟姐妹”。真因子之和大于本身的數叫盈數小于的叫虧數。求一個區間內盈數、虧數和完全數的各自個數。只需要在循環中同時維護三個計數器根據sum和num的大小關系分類累加即可。親密數對如果兩個數其中一個數的真因子之和等于另一個數反之亦然則它們構成親密數對如220和284。你可以嘗試修改程序來尋找親密數對這需要保存每個數的真因子和到一個字典或數組里然后進行比對。解決“求完全數個數”這道題就像打開了一扇門門后是算法優化和數論應用的廣闊世界。從最笨的雙重循環到利用數學性質的開方優化再到依靠深刻數論定理的降維打擊這個過程完美詮釋了“編程思維”的進化。下次再遇到類似“求xxx數”的題目不妨先問問自己這個“xxx數”有沒有特殊的數學性質能不能找到規律避免遍歷這往往就是通往高效算法的鑰匙。