1. 項目概述為什么我們需要判斷質(zhì)數(shù)在編程學(xué)習(xí)尤其是算法入門階段判斷一個數(shù)是否為質(zhì)數(shù)幾乎是一個繞不開的經(jīng)典問題。它看似簡單卻像一塊試金石能清晰地反映出你對循環(huán)控制、邊界條件處理和算法效率優(yōu)化的理解深度。很多朋友在面試或刷題時都曾在這個問題上栽過跟頭——要么寫出的代碼邏輯有漏洞漏判了像1或2這樣的邊界情況要么就是算法效率太低面對稍大一點的數(shù)字就慢得讓人無法忍受。我自己在帶新人、做Code Review時也見過無數(shù)個版本。有的代碼寫得像教科書一樣標(biāo)準(zhǔn)但毫無新意有的則充滿了“奇技淫巧”卻難以維護。今天我就結(jié)合自己十多年的編碼和教學(xué)經(jīng)驗拋開那些華而不實的理論直接上干貨。我們不只講三種方法怎么寫更要深挖每種方法背后的設(shè)計思路、性能瓶頸以及在實際編碼中那些教科書不會告訴你的“坑”。無論你是正在學(xué)習(xí)Python基礎(chǔ)的新手還是想優(yōu)化自己算法工具箱的老手相信這篇從實戰(zhàn)中總結(jié)出來的內(nèi)容都能給你帶來一些新的啟發(fā)。我們的目標(biāo)很明確寫出的代碼不僅要正確更要高效、健壯經(jīng)得起推敲。2. 核心思路與方案選型從暴力到優(yōu)雅的演進在動手寫代碼之前花幾分鐘想清楚“為什么”比直接寫“怎么做”重要得多。判斷質(zhì)數(shù)的核心定義是一個大于1的自然數(shù)如果除了1和它自身外不能被其他自然數(shù)整除那么它就是質(zhì)數(shù)。這個定義直接引出了最樸素的思路也為我們優(yōu)化算法提供了方向。2.1 方法一最直觀的暴力枚舉法這是所有人第一時間都能想到的方法對于一個待判斷的數(shù)n我們從2開始一直試除到n-1。如果在這個區(qū)間內(nèi)發(fā)現(xiàn)任何一個數(shù)能整除n那么n就不是質(zhì)數(shù)反之如果全部都不能整除那么n就是質(zhì)數(shù)。為什么這是起點因為它完全忠實于質(zhì)數(shù)的定義邏輯直白幾乎不需要額外的數(shù)學(xué)知識。對于初學(xué)者來說這是理解問題、建立循環(huán)和條件判斷概念的絕佳練習(xí)。它的時間復(fù)雜度是 O(n)意味著輸入數(shù)字增大10倍理論運行時間就可能增加10倍。所以它通常只適用于教學(xué)演示或處理非常小的數(shù)據(jù)范圍比如 n 10^4。2.2 方法二優(yōu)化試除范圍試除法仔細(xì)思考一下我們真的需要試除到n-1嗎假設(shè)n不是一個質(zhì)數(shù)它可以分解為兩個因數(shù)的乘積即n a * b。那么a和b不可能都大于sqrt(n)n的平方根。因為如果都大于那么a*b sqrt(n)*sqrt(n) n這與假設(shè)矛盾。所以n的因數(shù)除了1和自身中至少有一個小于或等于sqrt(n)。這個優(yōu)化的價值有多大這直接將試除的范圍從[2, n-1]縮小到了[2, int(sqrt(n))]。對于 n10000 來說試除次數(shù)從最多9999次降到了最多100次效率提升了兩個數(shù)量級時間復(fù)雜度優(yōu)化為 O(sqrt(n))。這是判斷質(zhì)數(shù)最常用、也最實用的單次判斷方法在算法競賽和日常開發(fā)中足以應(yīng)對絕大多數(shù)場景。2.3 方法三更進一步的優(yōu)化6k±1法試除法已經(jīng)很快了但我們還可以基于一個數(shù)學(xué)觀察再做優(yōu)化所有大于3的質(zhì)數(shù)都可以表示為6k±1的形式k是正整數(shù)。換句話說一個數(shù)如果不是2或3那么它如果是質(zhì)數(shù)一定在6的倍數(shù)兩側(cè)。為什么是6因為大于等于5的質(zhì)數(shù)必然與6互質(zhì)。我們可以把自然數(shù)按模6分類只有模6余1和余5的數(shù)即6k±1才可能是質(zhì)數(shù)當(dāng)然還需要進一步判斷。這樣在試除時我們就不用循環(huán)每一個奇數(shù)而是可以“跳著”檢查。具體步驟是先處理小于等于3的特殊情況然后檢查是否能被2或3整除最后從5開始以6為步長進行循環(huán)檢查i和i2即6k-1和6k1是否能整除n。它的效率提升如何相比于普通的試除法檢查所有奇數(shù)這種方法大約減少了三分之一的試除次數(shù)。因為原來需要檢查大約sqrt(n)/2個奇數(shù)現(xiàn)在只需要檢查大約sqrt(n)/3個候選數(shù)。雖然時間復(fù)雜度依然是 O(sqrt(n))但常數(shù)項更小在大數(shù)判斷或需要頻繁判斷時累積的效益就很可觀了。注意方案選型沒有絕對的“最好”只有“最合適”。對于單次、小范圍的判斷方法一清晰易懂對于通用的單次判斷方法二是性能和復(fù)雜度的最佳平衡只有在需要極致優(yōu)化或者在一個循環(huán)中判斷海量數(shù)字時才值得使用方法三。千萬不要在簡單的腳本里為了“炫技”而寫出難以理解的復(fù)雜代碼。3. 核心細(xì)節(jié)解析與實操要點理解了思路我們來看看實現(xiàn)時的魔鬼細(xì)節(jié)。很多錯誤和低效代碼都源于對這些細(xì)節(jié)的忽視。3.1 邊界條件那些容易被遺忘的角落邊界條件是代碼健壯性的關(guān)鍵判斷質(zhì)數(shù)時尤其如此。數(shù)字1根據(jù)定義1不是質(zhì)數(shù)。這是最高頻的錯誤來源之一。必須在函數(shù)開頭就處理掉。小于等于3的數(shù)2和3是質(zhì)數(shù)但它們小于我們通常的循環(huán)起始點。需要單獨處理。偶數(shù)所有大于2的偶數(shù)都不是質(zhì)數(shù)。這是一個非常高效的提前返回條件應(yīng)該在循環(huán)開始前判斷。負(fù)數(shù)和零通常我們只考慮正整數(shù)?？梢约s定函數(shù)只處理正整數(shù)輸入對于非正整數(shù)直接返回False或拋出異常。實操心得我習(xí)慣在函數(shù)入口處用一個清晰的if-elif鏈條處理所有特殊情況這樣主循環(huán)的邏輯會非常干凈。def is_prime_basic(n): # 處理非正整數(shù)和1 if n 1: return False # 處理2和3 if n 3: return True # 處理所有大于2的偶數(shù) if n % 2 0: return False # ... 主循環(huán)邏輯這樣寫閱讀代碼的人一眼就能明白所有邊界情況是如何處理的。3.2 循環(huán)控制與提前終止這是影響效率的關(guān)鍵點。循環(huán)上限在優(yōu)化試除法中循環(huán)上限是int(math.sqrt(n))。這里必須使用int()轉(zhuǎn)換因為range()函數(shù)需要整數(shù)。同時為了包含平方根這個邊界值例如 n9時需要試除3我們通常使用range(3, int(math.sqrt(n)) 1, 2)。這個1至關(guān)重要。步長設(shè)置在排除了偶數(shù)后我們只需要試除奇數(shù)所以步長設(shè)為2。在6k±1法中步長則是6。提前終止一旦在循環(huán)中發(fā)現(xiàn)n % i 0應(yīng)立即返回False而不是繼續(xù)無意義的循環(huán)。這是編寫高效循環(huán)的基本素養(yǎng)。一個常見的坑# 錯誤示例忽略了平方根邊界 for i in range(3, int(math.sqrt(n))): # 當(dāng)n9時range(3, 3)為空無法檢測出因數(shù)3 if n % i 0: return False3.3 工具函數(shù)與模塊使用為了提高代碼的清晰度和復(fù)用性我們應(yīng)將判斷邏輯封裝成函數(shù)。導(dǎo)入math模塊math.sqrt()是計算平方根的標(biāo)準(zhǔn)方法比n ** 0.5在意圖表達(dá)上更清晰。函數(shù)命名與文檔函數(shù)名應(yīng)清晰表明其用途如is_prime_trial_division。使用文檔字符串簡要說明算法和參數(shù)。類型提示可選但推薦對于Python 3.5可以使用類型提示如def is_prime(n: int) - bool:這能大大提高代碼的可讀性和可維護性許多現(xiàn)代IDE也能提供更好的智能提示。4. 三種方法的完整實現(xiàn)與對比分析下面我將給出三種方法的完整、健壯的Python實現(xiàn)并附上詳細(xì)的注釋和對比。4.1 方法一基礎(chǔ)暴力枚舉法實現(xiàn)def is_prime_naive(n: int) - bool: 使用暴力枚舉法判斷一個正整數(shù)是否為質(zhì)數(shù)。 時間復(fù)雜度: O(n) 僅適用于教學(xué)或極小的n。 # 處理邊界情況 if n 1: return False if n 3: # 2和3是質(zhì)數(shù) return True # 從2到n-1逐個試除 for i in range(2, n): if n % i 0: return False # 發(fā)現(xiàn)一個因數(shù)不是質(zhì)數(shù) # 循環(huán)完畢未發(fā)現(xiàn)因數(shù)是質(zhì)數(shù) return True # 測試 print(is_prime_naive(1)) # False print(is_prime_naive(2)) # True print(is_prime_naive(17)) # True print(is_prime_naive(100)) # False性能分析當(dāng)n10007時循環(huán)需要執(zhí)行10005次。在普通電腦上單次判斷可能就需要幾毫秒。如果在一個循環(huán)里判斷一萬個這樣的數(shù)總時間將非常可觀。因此除非有特殊理由否則不要在生產(chǎn)代碼中使用這種方法。4.2 方法二優(yōu)化試除法平方根范圍實現(xiàn)這是最推薦掌握和日常使用的方法。import math def is_prime_trial_division(n: int) - bool: 使用試除法優(yōu)化版判斷一個正整數(shù)是否為質(zhì)數(shù)。 試除范圍優(yōu)化到2到sqrt(n)。 時間復(fù)雜度: O(sqrt(n)) # 處理邊界情況 if n 1: return False if n 3: return True # 排除所有偶數(shù)大于2的偶數(shù)都不是質(zhì)數(shù) if n % 2 0: return False # 只需要檢查奇數(shù)因子上限為sqrt(n) limit int(math.sqrt(n)) 1 # 1 確保包含平方根邊界 for i in range(3, limit, 2): # 步長為2只檢查奇數(shù) if n % i 0: return False return True # 測試與性能對比 import time test_num 1000003 # 一個較大的質(zhì)數(shù) start time.perf_counter() result1 is_prime_naive(test_num) time1 time.perf_counter() - start start time.perf_counter() result2 is_prime_trial_division(test_num) time2 time.perf_counter() - start print(f暴力法: 結(jié)果 {result1}, 耗時 {time1:.6f} 秒) print(f試除法: 結(jié)果 {result2}, 耗時 {time2:.6f} 秒)在我的測試中對于n1000003暴力法耗時約0.13秒而試除法僅需約0.0002秒速度相差近千倍。4.3 方法三6k±1 優(yōu)化法實現(xiàn)import math def is_prime_6k_optimized(n: int) - bool: 使用基于6k±1規(guī)律的優(yōu)化試除法判斷質(zhì)數(shù)。 時間復(fù)雜度: O(sqrt(n))但常數(shù)項更小。 # 處理邊界情況 if n 1: return False if n 3: return True # 排除能被2或3整除的數(shù) if n % 2 0 or n % 3 0: return False # 從5開始檢查6k±1的數(shù) limit int(math.sqrt(n)) 1 i 5 # 循環(huán)條件i limit # 每次檢查 i 和 i2然后 i 增加6 while i limit: if n % i 0 or n % (i 2) 0: return False i 6 return True # 三種方法性能對比針對一個較大的合數(shù)讓循環(huán)跑滿 test_num 999983 # 這是一個質(zhì)數(shù)會讓循環(huán)幾乎跑滿 funcs [is_prime_naive, is_prime_trial_division, is_prime_6k_optimized] names [暴力枚舉, 試除法, 6k±1法] for func, name in zip(funcs, names): start time.perf_counter() result func(test_num) elapsed time.perf_counter() - start print(f{name:10} 結(jié)果: {result}, 耗時: {elapsed:.8f} 秒)性能對比表格方法名稱時間復(fù)雜度試除次數(shù)近似n較大時優(yōu)點缺點適用場景暴力枚舉法O(n)n-2邏輯極其簡單完全符合定義效率極低無法處理稍大的數(shù)僅用于教學(xué)演示理解概念優(yōu)化試除法O(sqrt(n))sqrt(n)/2效率高邏輯清晰易于理解和實現(xiàn)對于極大數(shù)仍不夠快通用場景首選算法題、日常開發(fā)6k±1優(yōu)化法O(sqrt(n))sqrt(n)/3在試除法基礎(chǔ)上進一步減少試除次數(shù)邏輯稍復(fù)雜代碼可讀性略有下降需要極致優(yōu)化的場景如批量判斷、大數(shù)判斷從表格可以看出優(yōu)化試除法在復(fù)雜度、可讀性和性能上取得了最佳平衡是你在絕大多數(shù)情況下應(yīng)該使用的方法。5. 常見問題與排查技巧實錄在實際編寫和調(diào)試質(zhì)數(shù)判斷函數(shù)時我踩過不少坑也幫別人排查過許多問題。這里總結(jié)幾個最典型的。5.1 問題一函數(shù)對某些數(shù)判斷錯誤如1, 4, 9癥狀代碼對大部分?jǐn)?shù)有效但對1返回了True或者對4、9這樣的平方數(shù)返回了True。根因分析遺漏了對1的判斷這是最常見的錯誤。質(zhì)數(shù)定義明確要求大于1。循環(huán)邊界錯誤在優(yōu)化試除法中range的上限設(shè)置錯誤。例如用了int(math.sqrt(n))而不是int(math.sqrt(n)) 1導(dǎo)致像9這樣的數(shù)sqrt(9)3無法被循環(huán)中的i3檢查到。解決方案嚴(yán)格按照3.1節(jié)中的邊界條件處理鏈條來寫。務(wù)必單獨處理n 1的情況并在計算循環(huán)上限時牢記1。5.2 問題二代碼效率低下判斷大數(shù)時超時癥狀在在線判題系統(tǒng)如LeetCode或處理批量數(shù)據(jù)時程序運行超時。根因分析使用了未優(yōu)化的暴力法這是最直接的原因。在優(yōu)化方法中錯誤地包含了偶數(shù)在排除了2之后主循環(huán)的步長仍然是1導(dǎo)致循環(huán)了所有偶數(shù)試除次數(shù)翻倍。沒有使用提前終止在發(fā)現(xiàn)因數(shù)后仍然繼續(xù)執(zhí)行完整個循環(huán)。解決方案立即將算法替換為優(yōu)化試除法方法二。確保主循環(huán)步長為2range(3, limit, 2)。檢查循環(huán)體內(nèi)一旦n % i 0是否立即return False。5.3 問題三需要判斷一個區(qū)間內(nèi)的所有質(zhì)數(shù)質(zhì)數(shù)篩法場景題目要求找出1到N之間所有的質(zhì)數(shù)。如果對每個數(shù)都調(diào)用一次is_prime函數(shù)即使使用優(yōu)化試除法總體時間復(fù)雜度也約為 O(N * sqrt(N))當(dāng)N很大時比如10^6依然很慢。更優(yōu)方案埃拉托斯特尼篩法這是一個經(jīng)典的算法其核心思想是從2開始將每個質(zhì)數(shù)的倍數(shù)標(biāo)記為合數(shù)最后剩下的就是質(zhì)數(shù)。def sieve_of_eratosthenes(n: int): 返回小于等于n的所有質(zhì)數(shù)列表。 時間復(fù)雜度: O(n log log n)空間復(fù)雜度: O(n) if n 2: return [] # 初始化一個布爾數(shù)組假設(shè)所有數(shù)都是質(zhì)數(shù) is_prime [True] * (n 1) is_prime[0] is_prime[1] False # 0和1不是質(zhì)數(shù) # 只需遍歷到 sqrt(n) for i in range(2, int(n ** 0.5) 1): if is_prime[i]: # 將i的倍數(shù)標(biāo)記為合數(shù) # 從 i*i 開始標(biāo)記因為更小的倍數(shù)已經(jīng)被之前的質(zhì)數(shù)標(biāo)記過了 for j in range(i * i, n 1, i): is_prime[j] False # 收集所有標(biāo)記為True的索引 primes [i for i, flag in enumerate(is_prime) if flag] return primes # 示例找出100以內(nèi)的所有質(zhì)數(shù) primes_under_100 sieve_of_eratosthenes(100) print(primes_under_100)篩法使用心得內(nèi)存交換時間篩法需要創(chuàng)建一個長度為N1的布爾數(shù)組空間開銷大。但當(dāng)N在百萬級別且需要獲取大量質(zhì)數(shù)時它的速度優(yōu)勢是單次判斷法無法比擬的。內(nèi)層循環(huán)的優(yōu)化從i*i開始標(biāo)記是關(guān)鍵優(yōu)化可以避免重復(fù)標(biāo)記。只遍歷到sqrt(n)外層循環(huán)的優(yōu)化原理與試除法相同。5.4 問題四如何處理極大整數(shù)的質(zhì)數(shù)判斷場景在密碼學(xué)或某些特殊應(yīng)用中可能需要判斷幾百位甚至上千位的大整數(shù)是否為質(zhì)數(shù)。挑戰(zhàn)對于如此大的數(shù)即使是 O(sqrt(n)) 的試除法其計算量也是天文數(shù)字不可行。解決方案概率性測試算法對于極大整數(shù)工業(yè)標(biāo)準(zhǔn)是使用概率性質(zhì)數(shù)測試算法如米勒-拉賓素性檢驗。它不能100%確定一個數(shù)是質(zhì)數(shù)但能以極高的概率遠(yuǎn)高于硬件出錯的概率給出正確結(jié)果。import random def miller_rabin(n: int, k: int 5) - bool: 米勒-拉賓素性檢驗。 n: 待檢驗的大奇數(shù) (n 2)。 k: 檢驗次數(shù)次數(shù)越多準(zhǔn)確率越高默認(rèn)為5。 返回: 如果n很可能為質(zhì)數(shù)返回True如果n是合數(shù)返回False。 if n 1: return False if n 3: return True if n % 2 0: return False # 將 n-1 寫成 2^r * d 的形式其中 d 是奇數(shù) r, d 0, n - 1 while d % 2 0: r 1 d // 2 # 進行k輪測試 for _ in range(k): a random.randint(2, n - 2) x pow(a, d, n) # 計算 a^d mod n使用內(nèi)置pow函數(shù)支持模冪效率極高 if x 1 or x n - 1: continue for _ in range(r - 1): x pow(x, 2, n) if x n - 1: break else: return False # 本輪測試未通過n是合數(shù) return True # 所有k輪測試都通過n很可能是質(zhì)數(shù) # 測試判斷一個較大的數(shù)這里用一個小點的示例 large_num 1000000007 # 這是一個著名的質(zhì)數(shù) print(f米勒-拉賓檢驗 {large_num}: {miller_rabin(large_num)})重要提示米勒-拉賓檢驗對于合數(shù)總是能給出正確判斷False對于質(zhì)數(shù)有極小的概率誤判True。但這個概率可以通過增加測試次數(shù)k降到極低例如k10誤判率已低于1/10^6。Python內(nèi)置的pow(a, b, mod)函數(shù)可以高效計算模冪這是實現(xiàn)該算法的關(guān)鍵。對于一般編程問題如力扣、考試、日常應(yīng)用絕對不需要用到這個算法。優(yōu)化試除法完全夠用。只有在你明確知道自己在處理密碼學(xué)級別的大數(shù)時才需要考慮它。6. 實戰(zhàn)進階將判斷函數(shù)嵌入更復(fù)雜的邏輯掌握了獨立的判斷函數(shù)后我們來看看如何在實際問題中應(yīng)用它。這往往比寫一個孤立的函數(shù)更有挑戰(zhàn)性。場景找出一個區(qū)間內(nèi)所有的“孿生質(zhì)數(shù)對”相差2的質(zhì)數(shù)對。import math def is_prime(n): 我們之前寫好的優(yōu)化試除法函數(shù) if n 1: return False if n 3: 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 find_twin_primes(start, end): 找出區(qū)間[start, end]內(nèi)的所有孿生質(zhì)數(shù)對。 if end 5: # 最小的孿生質(zhì)數(shù)對是(3,5) return [] twin_pairs [] # 我們只需要檢查奇數(shù)且從大于等于start的第一個奇數(shù)開始 current start if (start % 2 ! 0) else start 1 while current end - 2: # 因為要找current和current2 if is_prime(current) and is_prime(current 2): twin_pairs.append((current, current 2)) current 4 # 找到一對后下一對可能的起點至少跳過4 else: current 2 # 沒找到檢查下一個奇數(shù) return twin_pairs # 示例找出100以內(nèi)的孿生質(zhì)數(shù) pairs find_twin_primes(1, 100) print(100以內(nèi)的孿生質(zhì)數(shù)對) for p in pairs: print(p)在這個例子中我們學(xué)到了什么函數(shù)復(fù)用is_prime函數(shù)成為了一個可靠的構(gòu)建塊。循環(huán)優(yōu)化主循環(huán)只遍歷奇數(shù)current 2并且在找到一對后直接跳過4current 4因為 (p, p2) 是質(zhì)數(shù)對那么 p1 是偶數(shù)p3 如果是奇數(shù)它和 p5 才可能是下一對所以 p4 是下一個可能的起點。這種基于數(shù)學(xué)特性的微優(yōu)化在數(shù)據(jù)量大時能節(jié)省不少時間。邊界處理函數(shù)開頭對end 5的判斷避免了無效循環(huán)。7. 性能測試與可視化對比“感覺”上的快慢不靠譜我們需要數(shù)據(jù)。讓我們寫一個簡單的測試腳本直觀感受不同算法在不同輸入規(guī)模下的性能差異。import time import matplotlib.pyplot as plt import math # 重新定義我們的三個函數(shù)確保是最優(yōu)版本 def is_prime_1_naive(n): if n 1: return False if n 3: return True for i in range(2, n): if n % i 0: return False return True def is_prime_2_trial(n): if n 1: return False if n 3: 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 is_prime_3_6k(n): if n 1: return False if n 3: return True if n % 2 0 or n % 3 0: return False limit int(math.sqrt(n)) 1 i 5 while i limit: if n % i 0 or n % (i 2) 0: return False i 6 return True # 測試不同大小的數(shù)混合質(zhì)數(shù)與合數(shù) test_cases [ 101, # 小質(zhì)數(shù) 1009, # 中等質(zhì)數(shù) 10007, # 較大質(zhì)數(shù) 100003, # 更大質(zhì)數(shù) 999983, # 接近100萬的質(zhì)數(shù) ] # 為了公平我們也測試一個會讓循環(huán)跑滿的合數(shù) test_cases.append(999981) # 一個合數(shù) funcs [is_prime_1_naive, is_prime_2_trial, is_prime_3_6k] func_names [暴力法, 試除法, 6k±1法] results {name: [] for name in func_names} for n in test_cases: print(f\n測試數(shù)字: {n}) for func, name in zip(funcs, func_names): # 為了計時準(zhǔn)確可能的話運行多次取平均這里簡單起見單次 start time.perf_counter_ns() result func(n) elapsed_ns time.perf_counter_ns() - start elapsed_ms elapsed_ns / 1_000_000 # 轉(zhuǎn)換為毫秒 results[name].append(elapsed_ms) print(f {name:8} - 結(jié)果: {result}, 耗時: {elapsed_ms:.3f} ms) # 暴力法對于大數(shù)太慢我們跳過對最大數(shù)的測試 if name 暴力法 and n 10007: results[name].append(None) # 用None占位繪圖時忽略 print(f {name:8} - 跳過太慢) break # 繪制性能對比圖忽略暴力法對超大數(shù)的測試 plt.figure(figsize(10, 6)) x range(len(test_cases)) width 0.25 multiplier 0 for i, (name, times) in enumerate(results.items()): # 過濾掉None值 valid_times [t for t in times if t is not None] valid_indices [idx for idx, t in enumerate(times) if t is not None] offset width * multiplier rects plt.bar([idx offset for idx in valid_indices], valid_times, width, labelname) multiplier 1 plt.xlabel(測試數(shù)字 (按大小順序)) plt.ylabel(耗時 (毫秒)) plt.title(三種質(zhì)數(shù)判斷算法性能對比) plt.xticks([i width for i in range(len(test_cases))], [str(n) for n in test_cases]) plt.legend() plt.yscale(log) # 使用對數(shù)坐標(biāo)軸以便清晰顯示巨大差異 plt.tight_layout() plt.show()運行這段代碼你會得到一張柱狀圖?？梢郧逦乜吹奖┝Ψǖ暮臅r隨著數(shù)字增大呈線性增長在數(shù)字稍大時如10萬級就完全不可用。試除法和6k±1法的耗時增長非常緩慢幾乎在一條水平線上且6k±1法始終比試除法快一點點。在對數(shù)坐標(biāo)下暴力法與其他兩種方法的性能差距被拉成了數(shù)量級的差異視覺沖擊力很強。這個測試告訴我們選擇正確的算法比任何代碼層面的小優(yōu)化都重要得多。在編程中算法的時間復(fù)雜度是決定性能上限的首要因素。8. 總結(jié)與個人編碼習(xí)慣分享回顧這三種方法從最樸素的暴力枚舉到利用數(shù)學(xué)知識將范圍縮小到平方根的試除法再到基于數(shù)論規(guī)律進一步優(yōu)化的6k±1法我們看到的不僅是一段代碼的演變更是一種思維方式的提升從實現(xiàn)功能到追求效率再到深挖規(guī)律、精益求精。在我個人的項目經(jīng)驗里除非是在寫那種一次性的、數(shù)據(jù)范圍極小的腳本否則我?guī)缀蹩偸鞘褂脙?yōu)化試除法。它像一把瑞士軍刀足夠簡單可靠性能在99%的場景下都綽綽有余代碼可讀性也最好方便自己和后來的維護者理解。我會把它寫成一個工具函數(shù)放在項目的utils/math_helpers.py這樣的文件里。而6k±1法我更多是在一些對性能有極端要求的核心循環(huán)里或者是在學(xué)習(xí)、研究算法優(yōu)化時才會特意去用。畢竟在大多數(shù)業(yè)務(wù)邏輯里代碼的清晰度和可維護性比那一點點常數(shù)級的性能提升更重要。最后關(guān)于米勒-拉賓檢驗它屬于另一個維度的問題。只有當(dāng)你真正需要處理密碼學(xué)、大數(shù)分解這類領(lǐng)域的問題時才需要把它從工具箱里請出來。平時的話知道有這么個東西存在了解它的原理和適用邊界就足夠了。判斷質(zhì)數(shù)這個題目雖小但它像一滴水可以折射出編程世界的很多道理理解問題本質(zhì)、尊重數(shù)學(xué)規(guī)律、權(quán)衡性能與可讀性、處理邊界情況。把這些細(xì)節(jié)都琢磨透了你寫出的就不僅僅是一個能跑的函數(shù)而是一個健壯、高效、值得信賴的工具。下次再遇到類似問題你就能舉一反三游刃有余了。