因数与倍数

如果 $a$ 除以 $b$ 余数是 0，就说 $b$ 是 $a$ 的因数，$a$ 是 $b$ 的倍数。判断方法只有一条：看余数是不是 0，也就是 a % b == 0。

列出一个数的所有因数，最朴素的写法是从 1 试到 $n$：

for (int i = 1; i <= n; i++)
    if (n % i == 0)
        cout << i << " ";   // i 是 n 的因数

例如 $12$ 的因数是 $1,2,3,4,6,12$。

复杂度 $O(n)$。常见坑：% 的除数不能是 0，n % 0 会运行时崩溃，所以循环从 1 开始而不是从 0；判断"整除"要用 == 0，别漏写等号；如果 $n$ 很大（比如 $10^{12}$），这种 $O(n)$ 枚举会超时，下一节会用"因数成对"把它优化到 $O(\sqrt{n})$。