查看“约数”的源代码

若整数n除以整数d的余数为0，即d能整除n，则称d是n的'''约数'''，n是d的'''倍数'''，记为 <math>d|n</math> 。

== 算数基本定理的推论 ==
在[[算数基本定理]]中，若正整数N被唯一分解为<math>N = \prod_{i=1}^m p_i^{c_i}</math>，其中 <math>c_i</math> 都是正整数，<math>p_i</math> 都是素数，且满足 <math>p_1<p_2<\cdots <p_m</math> ，则N的正约数集合可写作：<math>\{{p_1}^{b_1},{p_2}^{b_2},\cdots,{p_m}^{b_m}\}</math> , 其中 <math>0 \leq b_i \leq c_i</math>

N的正约数个数为 <math>\prod_{i=1}^m {c_i+1}</math>

N的所有正约数的和为<math>\prod_{i=1}^m {\sum_{j=0}^{c_i} {{p_i}^j}}</math>

== 实现 ==
求N的正约数集合，若 <math>d \geq \sqrt N</math> 是N的约数，则 <math>\frac{N}{d} \leq \sqrt N</math> 也是N的约数。

因此，只需要扫描 <math>d=1 \backsim \sqrt N</math> 尝试d能否整除N，若能整除，则 <math>\frac{N}{d}</math> 也是N的约数。时间复杂度为<math>O(\sqrt N)</math> 。

<syntaxhighlight lang="c" line>
int f[MAX_N];
int m;
void divisor_factor(int n) {
	for (int i = 0; i * i <= n; ++i) {
		if (n % i == 0) {
			f[++m] = i;
			if (i != n/i)
				f[++m] = n/i;
		}
	}
}
</syntaxhighlight>

== 参考资料 ==
# 算法竞赛进阶指南，李煜东，139页
[[Category:数学]]