因数算法完全指南
因数（Factor）是指整数a除以整数b(b≠0)的商正好是整数而没有余数，我们就说b是a的因数。理解因数的概念和掌握高效的因数寻找算法对于数论、密码学以及算法竞赛都具有重要意义。
在数学中，因数是一个重要的概念：如果整数A能被整数B整除（B ≠ 0），那么B就是A的因数。例如，6的因数有1, 2, 3, 6，因为6可以被这些数整除。
最直观的方法是遍历从1到n的所有整数，检查是否能整除n。但这种方法的时间复杂度为O(n)，对于大数效率很低。
我们可以使用更高效的算法：只需遍历从1到√n（n的平方根）的整数。对于每个找到的因数i，同时得到另一个因数n/i。
输出1（1总是因数）
从i=2开始遍历到√n（包含√n）
如果n能被i整除，则输出i和n/i
如果n是完全平方数，避免重复输出√n
该算法只需遍历从2到√n的整数，因此时间复杂度为O(√n)。这比O(n)的暴力方法高效得多，特别是对于大数。
// 打印一个数的所有因数 void printFactors(int n) { // 1 总是因数 cout << "1 "; // 处理特殊情况：n=1 if (n == 1) return; // 从2遍历到√n for (int i = 2; i * i <= n; i++) { if (n % i == 0) { // 输出因数i cout << i << " "; // 如果i不是平方根，则输出另一个因数n/i if (i * i != n) { cout << n / i << " "; } } } // 输出n本身 cout << n; }
#include <iostream> using namespace std; int main() { int num = 36; cout << "36的因数: "; printFactors(36); // 输出: 1 2 18 3 12 4 9 6 36 return 0; }
为什么寻找因数只需要遍历到√n（n的平方根）就可以找到所有因数？
假设 d 是 n 的一个因数，那么 n = d × q，其中 q 也是 n 的因数。此时有三种情况：
通过遍历从 1 到 √n 的所有整数，我们可以找到所有小于或等于 √n 的因数 d，同时通过计算 n/d 得到对应的较大因数 q。这样就能找到 n 的所有因数对，而无需遍历到 n 本身。
这种优化方法将时间复杂度从 O(n) 降低到 O(√n)，对于大数（如 10^12）效率提升非常显著：从 10^12 次操作减少到约 10^6 次操作。