如何证明一个数是素数-试除到平方根能大幅缩减计算量

上周线下刷题碰到一道奥数题，拿着草稿纸闷头算四十多分钟，全程卡在如何证明一个数是素数这件事上，手里的铅笔划满半张演算纸，到最后都没摸透省力的路子。

一开始盯着数字137死磕，脑子里只记得课本模糊的说法，只要找不到除了1和它本身之外的因数，这个数就是素数。顺着这个思路从2开始挨个试除，2、3、5、7一路往后带，算到31的时候笔尖都发涩，草稿纸上写满余数，反复核对三遍依旧没找到能整除137的数字，当时笃定这数一定是素数，还顺手把验算步骤抄在了练习本空白处。

隔天同桌过来借草稿纸，扫了一眼我密密麻麻的计算步骤，直接指出来我白算了大半数字。他随手在空白区域画了个短横线，算出137的平方根大约是11.7，说根本不用试到三十多，只要把小于这个平方根的全部质数挨个试一遍就够。

当时整个人愣在原位，完全没想起课本里这条隐藏规则，之前做题总习惯顺着自然数挨个排查，压根没琢磨过数字大小和试除范围的关联。低头重新演算一遍，只需要验算2、3、5、7、11这五个质数，每一个除完都留存余数，短短两行计算就敲定137是素数，前后耗时还不到五分钟。

后来翻出之前做过的数论习题，随手挑了个数字223复盘。先算出它的平方根数值，落纸的瞬间就反应过来之前浪费的大量时间，早年遇到偏大的奇数，总想着把所有小数字全部验算一遍，明明多出来的计算步骤没有任何参考意义，纯粹是自己死板套用基础定义。

有次晚自习在家写拓展题，碰到数字199，下意识先算出平方根，锁定只需要核验到13以内的质数，算完所有数字依旧没有可以整除的因子，落笔写下结论的时候，忽然明白之前的计算误区到底在哪。

不少初学数论的人都会掉进同一个圈套，只死记素数基础判定标准，完全忽略开平方缩小试除区间的技巧。碰到两位数还好，三位数四位数要是硬从头试除，纸面计算量会成倍往上叠加，遇到考场限时答题的场景，光是验算就能耗掉大半做题时间。

那天收拾作业本的时候，翻到当初写满137验算过程的草稿纸，看着纸上密密麻麻作废的算式，指尖轻轻划过那些多余的计算数字，心里只觉得当初完全没必要耗费那么多精力做无用运算。

台灯的光晕落在纸面的根号计算式上，合上练习册之后再也没试过完整遍历自然数去判定素数。