写个求因子

写个求因子

因子概念：假设整数n除以m，余数为0，我们就称m是n的因子，一个整数n的因子数包含它自身的所有因子个数。

本节从求一个数因子，延伸到求连续数的多个因子讲解。

从o(n) -> o(sqrt(n))算法 实现一个数因子。

o(nlog(n))实现连续数因子。

求一个数因子

O(n)

一次循环直接扫描，这种大家比较容易理解。

代码语言：javascript复制

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得到，这样扫描会快点，写出了如下的实现。

代码语言：javascript复制

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个连续数，求每个数的所有因子。

代码语言：javascript复制

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);
  }
 }
}

另一种优雅的实现是：

代码语言：javascript复制

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);
    }
}

本节完

nlog

0 人点赞