概述
在这个教程中，我们将编写一个Java程序来找出给定整数的所有因子。
2. 问题介绍
在开始编写Java代码之前，让我们理解一下整数因子的概念。
如果一个整数i能完全除尽给定的整数n，那么i就是n的因子。 这里的“完全除尽”意味着当我们用n除以i时，余数为0。
几个例子可以快速说明这一点：
- n = 10 的因子：1, 2, 5, 10
- n = 13 的因子：1 和 13
- n = 1，n 只有一个因子：1
- n = 0，零没有因子
如示例所示，通常情况下，一个整数n的因子总是包含1和n，即使n是质数，比如13。然而，零是一个特殊的整数，它没有因子。
现在我们了解了因子的概念，接下来我们将创建一个Java程序来找出给定整数的所有因子。为了简单起见，我们将使用单元测试断言来验证我们的解决方案是否按预期工作。
3. 创建一个查找整数所有因子的方法
找到一个整数n的所有因子最直接的方法是通过循环从1到n，测试哪些数字能完全除尽n。我们可以将这些能完全除尽n的数字存储在一个集合中。当循环结束时，这个集合将包含n的所有因子。
在Java中实现这个想法并不困难：
static Set<Integer> getAllFactorsVer1(int n) {
Set<Integer> factors = new HashSet<>();
for (int i = 1; i <= n; i++) {
if (n % i == 0) {
factors.add(i);
}
}
return factors;
}
接下来，让我们编写一些测试来检查我们的方法是否按预期工作。首先，我们创建一个映射来准备一些测试数字及其预期的因子：
final static Map<Integer, Set<Integer>> FACTOR_MAP = ImmutableMap.of(
0, ImmutableSet.of(),
1, ImmutableSet.of(1),
20, ImmutableSet.of(1, 2, 4, 5, 10, 20),
24, ImmutableSet.of(1, 2, 3, 4, 6, 8, 12, 24),
97, ImmutableSet.of(1, 97),
99, ImmutableSet.of(1, 3, 9, 11, 33, 99),
100, ImmutableSet.of(1, 2, 4, 5, 10, 20, 25, 50, 100)
);
现在，对于上面的FACTOR_MAP中的每个数字，我们调用getAllFactorsVer1()方法，看它能否找到期望的因子：
FACTOR_MAP.forEach((number, expected) -> assertEquals(expected, FactorsOfInteger.getAllFactorsVer1(number)));
如果运行测试，它会通过。所以，该方法解决了问题，太棒了！
细心的人可能会注意到我们方法的名字带有Ver1. 这通常意味着在教程中我们会引入不同的版本。换句话说，解决方案仍有改进的空间。
接下来，让我们看看如何优化版本1的实现。
4. 优化 - 版本2
让我们回顾一下方法的主要逻辑：
for (int i = 1; i <= n; i++) {
if (n % i == 0) {
factors.add(i);
}
}
如上代码所示，我们将执行n % i的计算n次。如果我们观察一个整数的因子，我们会发现因子总是成对出现。以n = 100为例来理解这个因子特性：
1 2 4 5 10 20 25 50 100
│ │ │ │ | │ │ │ │
│ │ │ │ [10,10] │ │ │ │
│ │ │ │ │ │ │ │
│ │ │ └──[5, 20] ─┘ │ │ │
│ │ │ │ │ │
│ │ └───────[4, 25]────────┘ │ │
│ │ │ │
│ └────────────[2, 50]──────────────┘ │
│ │
└─────────────────[1, 100]───────────────────┘
正如我们所看到的，100的所有因子成对存在。因此，如果我们找到了一个因子i，我们可以得到配对的另一个因子i’= n/i。也就是说，我们不需要循环n次。相反，我们从1检查到数字n的平方根，并找到所有的i和i’对。这样，对于n=100，我们只需要循环十次。
接下来，让我们优化版本1的方法：
static Set<Integer> getAllFactorsVer2(int n) {
Set<Integer> factors = new HashSet<>();
for (int i = 1; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
factors.add(i);
factors.add(n / i);
}
}
return factors;
}
如上所示，我们使用了Java标准库中的Math.sqrt()方法来计算n的平方根。
现在，让我们用相同的测试数据测试我们第二版本的实现：
FACTOR_MAP.forEach((number, expected) -> assertEquals(expected, FactorsOfInteger.getAllFactorsVer2(number)));
如果运行测试，它会通过。所以，优化后的版本2按预期工作。
我们成功地将因子确定的时间从n减少到了n的平方根。这是一个显著的改进。然而，还有进一步的优化空间。所以，接下来，我们进一步分析它。
5. 更进一步的优化 - 版本3
首先，做一些简单的数学分析。
我们知道，给定的整数n可能是偶数或奇数。如果n是偶数，我们无法预测其因子是奇数还是偶数。例如，20的因子有1, 2, 4, 5, 10, 和 20，既有偶数也有奇数。
然而，如果n是奇数，它的所有因子也必须是奇数。例如，99的因子是1, 3, 9, 11, 33, 和 99，都是奇数。
因此，我们可以根据n是否为奇数调整循环的增量步长。由于我们的循环从i = 1开始，如果给定的是奇数，我们可以设置增量step = 2，跳过所有偶数的检查。
接下来，我们在版本3中实现这个想法：
static Set<Integer> getAllFactorsVer3(int n) {
Set<Integer> factors = new HashSet<>();
int step = n % 2 == 0 ? 1 : 2;
for (int i = 1; i <= Math.sqrt(n); i += step) {
if (n % i == 0) {
factors.add(i);
factors.add(n / i);
}
}
return factors;
}
有了这个优化，如果n是偶数，循环执行次数与版本2相同，即执行sqrt(n)次。
但是，如果n是一个奇数整数，总共有sqrt(n)/2次循环执行。
最后，让我们测试我们的版本3解决方案：
FACTOR_MAP.forEach((number, expected) -> assertEquals(expected, FactorsOfInteger.getAllFactorsVer3(number)));
如果运行测试，它会通过。所以，它正确地完成了工作。
6. 结论
在这篇文章中，我们创建了一个Java方法来找出一个整数的所有因子。此外，我们讨论了对初始解决方案的两种优化。
如往常一样，这里展示的所有代码片段都在GitHub上可用。