公式只需3步，別用循環(huán)跑1000次：一道幼兒園算術(shù)題給程序員的思維考題

周三晚上十一點(diǎn)，工程師陳卓擰開第三瓶無糖可樂，點(diǎn)開了歐拉計(jì)劃的第一題。那個(gè)問題安靜地躺在屏幕上，像所有經(jīng)典的初學(xué)者陷阱一樣，外表溫柔、內(nèi)核鋒利。“把1000以下所有3或5的倍數(shù)加在一起。” 他下意識(shí)地敲出了一個(gè) for 循環(huán)，一行行代碼像肌肉記憶般流出。跑出結(jié)果233168只用了半秒，他正想關(guān)掉頁(yè)面，突然被一句話拽住了：“如果上限是一個(gè)億呢？”

不是性能不夠，是腦袋里那根“先跑循環(huán)再說”的弦繃得太久了。陳卓盯著剛剛寫完的代碼，心里開始了一場(chǎng)辯論，正方和反方都來自他自己。正方說：?jiǎn)栴}這么小，直接遍歷最簡(jiǎn)單，可讀性滿分，同事半夜接手也能看懂。反方反駁：可讀性不是懶惰的借口，一千、一萬你遍歷，一億、十億也遍歷嗎？養(yǎng)成習(xí)慣再想改就難了。他看著那一行 if number % 3 == 0 or number % 5 == 0，突然意識(shí)到，這其實(shí)是在問一個(gè)數(shù)學(xué)問題，而自己一直在用物理方式回答。

暴力解法確實(shí)直白：從1數(shù)到999，每個(gè)數(shù)都用取余運(yùn)算符 % 驗(yàn)一下，能被3或5整除就累加。Python 里 number % 3 返回余數(shù)，余數(shù)為零便說明沒有余數(shù)——整除成立。代碼就是一套機(jī)械流水線，送進(jìn)數(shù)字，流出判斷，統(tǒng)計(jì)求和。對(duì)于1000，這不過一千次檢查，現(xiàn)代處理器眼皮都不眨。但陳卓慢慢看穿了它的真面目：這是一個(gè) O(n) 的方案，工作量跟輸入量成正比。上限翻倍，循環(huán)次數(shù)翻倍；上限膨脹到十億，就要做十億次整除判斷。跑得動(dòng)不代表跑得好——你讓銀行把每一筆歷史交易都循環(huán)一遍來算利息，數(shù)據(jù)中心會(huì)直接拉警報(bào)。

反方立場(chǎng)開始亮出底牌：?jiǎn)栴}的本質(zhì)不是“數(shù)字的逐一篩查”，而是“3和5的倍數(shù)構(gòu)成的等差數(shù)列”。3的倍數(shù)就是3, 6, 9, 12…… 每一項(xiàng)都比前一項(xiàng)固定多出3，這正是算術(shù)級(jí)數(shù)的定義。高斯小學(xué)時(shí)就算出了1加到100的和，公式簡(jiǎn)潔得像一句詩(shī)：和 = 首項(xiàng)加末項(xiàng)的和除以2再乘以項(xiàng)數(shù)，也就是 n×(n+1)/2。對(duì)于3的倍數(shù)，只不過每一項(xiàng)都帶著公因子3，只要把3提到外面，括號(hào)里還是連續(xù)自然數(shù)的和。所以，3的所有倍數(shù)求和，等價(jià)于 3 × [ (項(xiàng)數(shù))×(項(xiàng)數(shù)+1)/2 ]。這里的項(xiàng)數(shù)等于 (上限?1) 整除3，也就是 floor((limit?1)/3)。同理可得5的倍數(shù)總和。

到這里，正方又開口了：“等等，這兩個(gè)集合有重疊——15既是3的倍數(shù)又是5的倍數(shù)，你把兩筆錢加起來的時(shí)候，15、30、45就被數(shù)了兩次，等于重復(fù)報(bào)銷。”這恰好引出了容斥原理：要把多算的部分減掉。于是最終答案變成三個(gè)等差數(shù)列之和的加減法：sum(3的倍數(shù)) + sum(5的倍數(shù)) ? sum(15的倍數(shù))。寫成代碼，一個(gè)通用的輔助函數(shù) sum_of_multiples 接收參數(shù) x 和 limit，先用整數(shù)除法“//”算出項(xiàng)數(shù) n（它自動(dòng)向下取整，恰好給出完整倍數(shù)的個(gè)數(shù)），然后直接套 x * n * (n+1) // 2。主函數(shù) project_euler_1 就變成一行組合返回。陳卓把代碼跑了一遍，還是那個(gè)結(jié)果233168，但他知道事情已經(jīng)完全不一樣了。

他用幾分鐘畫了一張對(duì)比表，把兩種思路的內(nèi)核赤裸裸擺在面前。上限1000時(shí)，暴力法大約做1000次運(yùn)算，公式法只需幾十次簡(jiǎn)單乘法加法；上限100萬，暴力法約百萬次工作，公式法還是幾十次；上限10億，暴力逼近十億次，公式仍是兩位數(shù)級(jí)別的常量計(jì)算。從算法復(fù)雜度看，這就是 O(n) 與 O(1) 的距離。O(1) 意味著不管輸入量多大，核心計(jì)算成本幾乎不變——它不是在數(shù)數(shù)，是在計(jì)算。循環(huán)在那里一個(gè)個(gè)敲門，公式卻直接砸開了保險(xiǎn)柜。

這不僅僅是歐拉計(jì)劃第一題的花邊。陳卓立刻想到了數(shù)據(jù)庫(kù)里 B+樹索引為什么能瞬間定位數(shù)據(jù)，而不是一行行掃描全表；想到了現(xiàn)代密碼學(xué)里大數(shù)取模運(yùn)算其實(shí)依賴數(shù)學(xué)性質(zhì)，而不是循環(huán)試除；想到了機(jī)器學(xué)習(xí)里向量化操作把循環(huán)壓進(jìn)底層線性代數(shù)庫(kù)，用矩陣公式替代逐元素計(jì)算。哪怕是電商的計(jì)費(fèi)系統(tǒng)，需要實(shí)時(shí)刻劃賬單總額，也不可能逐筆交易遍歷，一定是預(yù)先按規(guī)則算好了公式模型。所有場(chǎng)景指向同一句問話，這也就是反方最終獲勝的原因：“我需要檢查每一個(gè)案例嗎，還是可以直接算出答案？”

那晚，陳卓沒有再去刷題，而是把那個(gè)輔助函數(shù)又看了一遍。它干的活極少，只負(fù)責(zé)一個(gè)數(shù)列的求和，但它像一面鏡子：同樣的需求，既可以演成一出遍歷每一個(gè)數(shù)字的冗長(zhǎng)戲劇，也可以壓縮成三個(gè)乘法。差別不在數(shù)學(xué)本身，在于開工之前的那一秒停頓——你是在寫循環(huán)，還是在找結(jié)構(gòu)。數(shù)學(xué)家早就把3的倍數(shù)求和封裝成了高斯求和公式，把重復(fù)計(jì)數(shù)問題抽象成了容斥原理，而程序員要做的，只是把它們翻譯成可復(fù)用的函數(shù)。用一次是取巧，每次都這么想才是工程素養(yǎng)。

回頭再看那行最初的代碼，陳卓沒有覺得它錯(cuò)，只是覺得它漏掉了一個(gè)更早的步驟。暴力循環(huán)是最后的保底手段，而不是第一反應(yīng)。任何工程師面對(duì)“把符合條件的都算一遍”這種需求時(shí)，都應(yīng)該先做三件事：認(rèn)清模式（這里就是等差數(shù)列），抽取通用公式（高斯求和），再用組合法則消除重復(fù)（容斥原理）。順序?qū)α耍瑥?fù)雜度可能就從 O(n) 跳變到 O(1)。這跟背更多算法無關(guān)，跟“計(jì)算代替計(jì)數(shù)”的思維有關(guān)。那一句“能不能算出來”比具體某個(gè)算法更值錢，它背后藏著一整套讓軟件快起來、讓架構(gòu)輕下來的直覺。

整個(gè)復(fù)盤最后凝結(jié)成了一條樸素的提醒：當(dāng)你要遍歷整個(gè)世界之前，先看一眼世界是不是早就把自己排列成了公式。如果是，就用乘法和除法回答它，別再用加法慢吞吞地走完每一步。