写个求因子
写个求因子
因子概念：假设整数n除以m，余数为0，我们就称m是n的因子，一个整数n的因子数包含它自身的所有因子个数。
本节从求一个数因子，延伸到求连续数的多个因子讲解。
从o(n) -> o(sqrt(n))算法 实现一个数因子。
o(nlog(n))实现连续数因子。
求一个数因子
O(n)
一次循环直接扫描，这种大家比较容易理解。
int x;
cin >> x;
vector<int> fs;
for (int i = 1; i <= x; ++i) {
if (x % i == 0) {
fs.push_back(i);
}
}
O(sqrt(n))
例如：40的因子有如下，除了红色部分。
1 2 4 5 sqrt(40) 8 10 20 40
对于前半部分我们可以扫描，后半部分通过40/i得到，这样扫描会快点，写出了如下的实现。
int x;
cin >> x;
vector<int> fs;
for (int i = 1; i * i <= x; ++i) {
if (x % i == 0) {
fs.push_back(i);
if (i * i != x) fs.push_back(x / i);
}
}
求连续数的对应因子
假设有n个连续数，求每个数的所有因子。
int n = 10;
vector<int> divisors[n + 1];
// n个数 对应的各自因子
for (int j = 1; j <= n; j++) {
for (int i = 1; i * i <= j; ++i) {
if (j % i == 0) {
divisors[j].push_back(i);
if (i * i != j) divisors[j].push_back(j / i);
}
}
}
另一种优雅的实现是：
vector<int> divisors[mx + 1]; // 每个数有哪些因子
for (int i = 1; i <= mx; i++) {
for (int j = i; j <= mx; j += i) {
divisors[j].push_back(i);
}
}
本节完
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2022-02-26，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录