为何相近大素数的乘积比一大一小素数的乘积分解耗时更长？

咱们来掰扯清楚这个事儿，核心原因其实就藏在你用的试除法逻辑里——不管是你写的第一个factorize函数（试所有奇数）还是第二个factorize_sieve函数（试预生成的素数），本质都是靠“挨个试除数，直到找到能整除n的数”来分解的，而两种情况的试除步数差了十万八千里。

先给你拆解两种场景的区别：

• 当n是小素数+大素数的乘积时（比如12345679=37×333667），n的平方根大概是3653。但试除法根本不用走到平方根——刚试到37的时候，就发现它能整除n，直接把n分解成37和333667，剩下的只要判断333667是不是素数就行（而因为37已经小于sqrt(n)了，剩下的数肯定是素数）。整个过程只需要试几十个以内的数（或者素数），步子迈得特别小就搞定了。
• 当n是两个相近大素数的乘积时（比如13717421=3607×3803），n的平方根大概是3703，刚好卡在两个素数中间。这时候试除法必须一路试到接近平方根的那个素数（也就是3607）才能找到第一个因子，中间要试几百个奇数（或者素数）。比如你用factorize函数的时候，要从3开始每次加2，试到3607，这中间有近1800次循环；而用factorize_sieve的时候，素数列表里到3700左右有500多个素数，得挨个试到3607才停下，步数比前者多了几十上百倍，时间自然就长了。

再看你的测试数据，完全符合这个逻辑：

• 比如factorize_sieve分解12345679只需要12.6μs，因为它只需要遍历素数列表到第12个素数（37）就搞定了；
• 分解13717421需要64.1μs，因为得遍历到素数列表里第500多个素数（3607）；
• 而分解65415743=8087×8089时，平方根接近8088，得遍历到第1000多个素数（8087），所以耗时直接涨到130μs，比前者又翻了一倍。

说白了，试除法的效率完全取决于“找到第一个因子需要试多少个数”——碰到小因子的时候直接躺赢，碰到两个都很大且接近的因子，就得熬到接近平方根才能找到突破口，耗时自然就上去了。这也是为啥RSA加密会用两个大素数的乘积——这种数用普通试除法分解起来特别费劲，刚好适合做加密的核心~

备注：内容来源于stack exchange，提问作者Ξένη Γήινος