试除法求约数：深入分析与实践
在数学和算法领域，约数，也称因数，是一个非常基础的概念。给定一个整数，它的所有约数是能够整除它的数。例如，6 的约数包括 1、2、3 和 6。为了找到一个数的所有约数，一种常见的方法是试除法。本文将通过一个简单的 C++ 程序来探讨试除法如何工作。
代码分析
#include<bits/stdc++.h> using namespace std; vector<int> get_divisors(int n) { vector<int> res; for (int i = 1; i <= n / i; ++i) { if (n % i == 0) { res.push_back(i); if (i != n / i) res.push_back(n / i); } } stable_sort(res.begin(), res.end()); return res; }
核心思想:
- 遍历从 1 到 √n 的所有整数。这是因为如果 n 有一个大于 √n 的约数 d，那么必定存在一个小于或等于 √n 的约数 n/d。
- 检查当前整数 i 是否可以整除 n。如果可以，i 和 n/i 都是 n 的约数。
- 为了防止重复计数，当 i = n/i 时，只需要添加一次 i。这种情况只在 n 为完全平方数时发生。
程序继续…
int main() { int n; cin >> n; while (n --) { int a; cin >> a; auto res = get_divisors(a); for (auto t: res) cout << t << ' '; puts(""); } return 0; }
该 main 函数首先读入一个数字 n，表示需要求约数的数字的数量。然后，程序对每个数字调用 get_divisors 函数，并将结果打印出来。
优点和效率
试除法是求约数问题中最直接的方法。它的时间复杂度是 O(√n)。虽然在某些情况下可能存在更高效的方法，但试除法因其简单性和普适性而广受欢迎。
