C++ 数论相关题目（约数）

1、试除法求约数

主要还是可以成对的求约数进行优化，不然会超时。
时间复杂度根号n

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int n;vector<int> solve(int a)
{vector<int> res;for(int i = 1; i <= a / i; i ++ ){if(a % i == 0){res.push_back(i);if(a / i != i)res.push_back(a / i);}}sort(res.begin(), res.end());return res;
}int main ()
{cin>>n;while(n -- ){int a;cin>>a;auto t = solve(a);for(auto x : t)cout<<x<<' ';cout<<endl;}return 0;
}

2、约数个数

主要是要理解算术基本定理：

约数个数：（a1+1）(a2+2)…