如何編寫一個求一個數(shù)所有因子的程序呢??假設這個數(shù)是2000, 相信大家很快就可以寫出如下代碼:

上面程序可以正確地得出答案，該程序的時間復雜度為O(n), 2000次循環(huán)對cpu來說也只是幾毫秒的事情，但如果將 n 擴大為一個16位的整數(shù)， 計算機就可能要算上一天了。。。

如何進行優(yōu)化呢，這就要開始研究因子數(shù)的數(shù)學性質(zhì)了!?下面我們就來從0開始證明一個數(shù)與其因子數(shù)存在什么性質(zhì):

先假設自然數(shù)?, 我們要求出它所有因子的集合，我們需要證明兩個命題成立即可:

命題1: 因子是成對出現(xiàn)的： 如果?自然數(shù)??存在一個因子?, 那么必然存在另一個因子?使得??(注意這里如果 N 是平方數(shù)的話?可以等于)。

證明: 已知 , 要證明該命題成立我們只需證明 即可, 由 ?,?我們知?N 可以分解成一個數(shù)字 ?和另一個數(shù)字 , 又因為 , 所以 。?

題外話: 上述證明只是從直觀上來出發(fā)，如何用反證法來證明呢，可以先假設另一個數(shù)字 不能整除 N, 那么最后會推出 是不能整除 N 的,??而與條件?產(chǎn)生矛盾, 所以 一定會整除 ?.

(這個方法的證明思路就放在這里了，過程交給讀者了)

命題2:因數(shù)是成對出現(xiàn)的(上面已證明)，一個小于等于算數(shù)平方根，另外一個大于等于算數(shù)平方根

證明: 我們利用反證法證明簡單地這個命題，假設我們找到了一個因子 ?小于? , 如果存在另一個因子 ?也小于??, 那么?, 那么 因子 ?與其成對的因子必然不是 。假設我們找到了一個因子 ?大于??, 如果存在另一個因子??也大于??,?那么?, 那么因子 ?與其成對的因子必然不是 。 所以一對因子唯一的可能就是一個小于等于?，另外一個大于等于? 。?

最后我們來證明等于的情況,? 我們只需要找到?一個因子 x1 = x2,?使得?x1 * x2?= N,?這只有 N 是平方數(shù)的情況下成立。

那么我們就可以開始寫代碼了，由命題2可以得到，由于因子都是成對出現(xiàn)的我們只需要循環(huán)到? 就可以找到所有因子了!

那么我們就把該算法從時間復雜度O(n) 優(yōu)化到 O()了:

?