版本1：求n的所有质因子，时间复杂度O(sqrt(n))。
// 例如：12=2*2*3，那么
// factor(12, 1) => {2,3}
// factor(12, 0) => {2,2,3}
std::vector<int> factor(int n, int removeDup) {
std::vector<int> ans;
for (int i = 2; i <= n/i; i++) {
while (n % i == 0) {
ans.push_back(i);
n /= i;
}
}
if (n > 1) ans.push_back(n);
if (removeDup)
ans.erase(std::unique(ans.begin(), ans.end()), ans.end());
return ans;
}
版本2：求n的所有因子，时间复杂度O(sqrt(n))。
// 例如：12的因子有：1,2,3,4,6,12
std::vector<int> factor(int n) {
std::set<int> ans;
for (int i = 1; i <= n/i; i++) {
if (n % i == 0) {
ans.insert(i);
ans.insert(n/i);
}
}
return std::vector<int>(ans.begin(), ans.end());
}
版本3：质因子分解，返回质因子及其出现次数，时间复杂度O(sqrt(n))。
// 例如：60 = 2^2 * 3^1 * 5^1，对应[{2,2}, {3,1}, {5,1}]
std::vector<std::pair<int,int>> factor(int n) {
std::vector<std::pair<int,int>> ans;
for (int i = 2; i <= n/i; i++) {
if (n % i == 0) {
int p = i, q = 0;
while (n % i == 0) {
n /= i;
q += 1;
}
ans.push_back({p, q});
}
}
if (n > 1) ans.push_back({n, 1});
return ans;
}
版本4：对n!做质因子分解，时间复杂度：初始化O(n)，单次查询O(logn*logn)。
// 使用方法：
// 1. 先调init(n)筛选出n以内的质数；
// 2. 调factor(n)返回n!的因子分解结果；比如factor(5)=[(2,3)(3,1)(5,1)]
struct ProductFactor {
std::vector<int> prime;
void init(int maxn) {
std::vector<int> p(maxn+1, 1);
for (int i = 2; i <= maxn; i++) {
if (p[i]) prime.push_back(i);
for (auto j : prime) {
if (i * j > maxn) break;
p[i*j] = 0;
if (i % j == 0) break;
}
}
}
std::vector<pair<int,int>> factor(int n) {
std::vector<pair<int,int>> ans;
for (auto p : prime) {
if (p > n) break;
int cnt = 0;
for (int nn = n; nn; nn /= p) {
cnt += nn / p;
}
ans.push_back({p, cnt});
}
return ans;
}
};