1.求一個整數的所有約數

對于一個整數x，他的其中一個約數若為i，那么x/i也是x的一個約數。而其中一個約數的大小一定小于等于根號x（完全平方數則兩個約數都為根號x），所以我們只需要遍歷到根號x，然后計算出另一個約數即可

代碼實現：
?

int a[N];
int cnt;
void getnum(int x)
{for(int i = 1; i <= x/i; i++){if(x%i == 0){a[++cnt] = i;if(x/i != i){ a[++cnt] = x/i;}}}
} 

時間復雜度為O(根號n)

2.求（1~n）的每個數的約數集合

如果我們對每個數都使用試除法會導致算法時間復雜度過高，為O（n*根號n）

所以我們使用正難則反的思想，遍歷1~n的所有數，然后將它作為約數給到所有他的倍數。

圖示：

這里我們演示了如何使用該方法將每個數的約數求出來。

這樣子時間復雜度就來到了nlogn

代碼實現：
?

int n;
vector<int> a[N];
void func()
{
for(int i = 1; i <= n; i++){for(int j = 1; i*j <= n; j++){a[i*j].push_back(i);}}
}      

3.約數個數定理

根據唯一分解定理我們可知：一個數可以被拆分成多個質數的任意次方相乘

而這些不同的質數經過組合就可以得到num的約數

圖示：

而總結出來的公式就是：

(次方加1）*(次方加1) *.......

補充：
試除法求單個數的約數個數

方法一：遍歷1~根號n的數將cnt返回

方法二：分解質因數后套用公式計算

4.約數和定理

計算方法：將每個質因數的所有分別種類相加，記為sum，然后不同的質因數的sum乘起來

右邊我們就是在計算約數之和的具體過程

?5.例題講解

審題：
本題需要我們求出一到n的數的所有約數的個數之和

思路：
方法一：暴力解法

我們可以用試除法計算1到n每個數的所有約數，然后將cnt累加起來，外層循環為遍歷1~n，內層為試除法，時間復雜度為O（n根號n）

運行次數為1e12，一定超時

方法二：正難則反

我們可以遍歷1~n，不過這里的i含義是約數，用n/i可以求出當前約數一共出現的次數，然后就累加起來。但是這樣就要運行n次，也就是1e8次，還是有可能超時

優化：由于當i小于等于n/2的時候，約數出現次數大于等于1，而i大于n/2的時候，約數次數一定為1，所以我們只用遍歷到n/2即可，后面的次數都為1，所以后面的約數的出現次數等于后面的約數個數（n-n/2）

解題：
?

#include<iostream>
using namespace std;
typedef long long ll;
ll n;
ll cnt;
int main()
{cin >> n;for(int i = 1; i <= n/2; i++){cnt += n/i;}cnt += n-n/2;cout << cnt << endl;return 0;
}