1952 三除數(shù)

方法一：暴力枚舉

由于此題的數(shù)據(jù)量為 1e4，可以考慮統(tǒng)計 1 ~ n 以內(nèi)所有 n 的正除數(shù)，最后判斷即可；

Python版本

C++版本

復雜度分析

• 時間復雜度：O(N)。

• 空間復雜度：O(1)。

方法二：枚舉 + 質(zhì)因數(shù)判斷

對于除了1以外的任意正整數(shù)而言，它至少有自身和1兩個正除數(shù)，此外，對于一個數(shù)開平方根，增多一個因數(shù)，但此因數(shù)必須是質(zhì)數(shù)，否則還可以再拆分因數(shù)；

枚舉 2 ~ sqrt(n) 的所有數(shù)字，判斷其是否為平方根且為質(zhì)數(shù)即可；

Python版本

C++版本

復雜度分析

• 時間復雜度：。

• 空間復雜度: O(1)。

方法三：枚舉 + 貢獻度累加

任意一個正整數(shù)，如果能作為 n 的一個除數(shù)，n 與這個除數(shù)的商也是一個除數(shù)。因此我們只需要枚舉 1 ~ sqrt(n)以內(nèi)的數(shù)字即可。如果能被n整除且是平方根，則除數(shù)和商相同，貢獻度為1，不是平方根則說明同時選中了它以及將它作為除數(shù)得到的商，貢獻度為2；最后判斷計數(shù)器的值是否為3即可；

Python版本

C++版本

復雜度分析

• 時間復雜度：O(logn)。

• 空間復雜度：O(1)。

備注

1. 方法二實際上是驗證 n 是否存在一個質(zhì)數(shù)的平方根，如果有，則說明至少有三個整除數(shù)。這種假設構(gòu)建在這個數(shù)已經(jīng)有兩個除數(shù)的情況下，因此可以從2開始遍歷；

2. 方法三計算貢獻度時，需要分別驗證能夠整除n的除式中，較大數(shù)，較小數(shù)，以及是否存在平方根，本質(zhì)上還是統(tǒng)計正除數(shù)的個數(shù)，因此要從1開始遍歷；如果從2開始，那么就少統(tǒng)計了1作為任意大于1的數(shù)字的整除數(shù)的情況；