List All Factors of a Number in Java – 在Java中列出一个数字的所有因数

最后修改: 2022年 8月 28日

中文/混合/英文(键盘快捷键:t)

1. Overview

1.概述

In this tutorial, we’ll write a Java program to find all the factors of a given integer.

在本教程中,我们将编写一个Java程序来寻找一个给定整数的所有因子。

2. Introduction to the Problem

2.对问题的介绍

Before we start writing the Java code, let’s understand what an integer’s factors are.

在我们开始编写Java代码之前,让我们了解一下什么是整数的因子。

Given an integer n, the integer i is n‘s factor if it can completely divide the number i. Completely divisible here means when we divide n by i, we get zero as the remainder.

给定一个整数n,如果整数i能够完全除以数字i,那么它就是n的因子。这里的完全可除意味着当我们用n除以i时,我们得到的余数为零。

A few examples may explain it quickly:

有几个例子可以快速解释。

  • n = 10, its factors: 1, 2, 5, and 10
  • n = 13, its factors: 1 and 13
  • n = 1, n has only one factor: 1
  • n = 0, zero has no factor

As the example shows, usually, an integer n‘s factors always contain 1 and n, even if n is a prime number, for example, 13. However, zero is a special integer. It has no factor.

如例子所示,通常,一个整数n的因子总是包含1n,即使n是一个质数,例如13。然而,零是一个特殊的整数。它没有因子。

Now that we understand the concept of factors, let’s create a Java program to find all the factors of a given integer.

现在我们理解了因子的概念,让我们创建一个Java程序来寻找一个给定的整数的所有因子。

For simplicity, we’ll use unit test assertions to verify if our solution works as expected.

为了简单起见,我们将使用单元测试断言来验证我们的解决方案是否按预期工作。

3. Creating a Method to Find All Factors of an Integer

3.创建一个寻找整数所有因数的方法

The most straightforward way to find all the factors of an integer n is by looping from 1 to n and testing which number can completely divide n. We can store those numbers that can completely divide n in a Set. When the looping finishes, this Set will hold all the factors of n.

要找到一个整数n的所有因子,最直接的方法是从1到n,测试哪个数字能完全除掉n。我们可以将那些可以完全除掉n的数字存储在一个Set中。循环结束后,这个Set将保存n的所有因子。

Implementing this idea in Java isn’t a challenging job for us:

对我们来说,在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;
}

Next, let’s write some tests to check if our method works as expected. First, let’s create a Map to prepare some numbers to test and their expected factors:

接下来,让我们写一些测试来检查我们的方法是否像预期的那样工作。首先,让我们创建一个Map来准备一些要测试的数字和它们的预期系数。

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)
);

Now, for each number in the FACTOR_MAP above, we call the getAllFactorsVer1() method that we’ve implemented to see if it can find the desired factors:

现在,对于上面FACTOR_MAP中的每个数字,我们调用我们实现的getAllFactorsVer1()方法,看看它是否能找到想要的因子。

FACTOR_MAP.forEach((number, expected) -> assertEquals(expected, FactorsOfInteger.getAllFactorsVer1(number)));

The test passes if we run it. So, the method solves the problem, great!

如果我们运行它,测试就会通过。所以,这个方法解决了问题,很好!

Sharp eyes may spot that we named the method with Ver1. Usually, it implies we’ll introduce different versions in the tutorial. In other words, the solution still has room for improvement.

眼尖的人可能会发现,我们用Ver1来命名这个方法。通常情况下,这意味着我们将在教程中介绍不同的版本。换句话说,这个解决方案仍有改进的余地。

Next, let’s see how to optimize the version 1 implementation.

接下来,让我们看看如何优化版本1的实现。

4. Optimization – Version 2

4.优化 – 第二版

Let’s review the primary logic in the method:

让我们回顾一下该方法中的主要逻辑。

for (int i = 1; i <= n; i++) {
   if (n % i == 0) {
       factors.add(i);
   }
}

As the code above shows, we’ll execute the n % i calculation n times. Now, if we examine the factors of an integer, we’ll see that factors always come in pairs. Let’s take n =100 as an example to understand this factor characteristic:

如上面的代码所示,我们将执行n % i计算n次。现在,如果我们研究一个整数的因子,我们会发现因子总是成对出现。让我们以n =100为例来理解这个因子的特点。

   1    2    4    5    10    20    25    50    100
   │    │    │    │    |      │     │     │     │
   │    │    │    │  [10,10]  │     │     │     │
   │    │    │    │           │     │     │     │
   │    │    │    └──[5, 20] ─┘     │     │     │
   │    │    │                      │     │     │
   │    │    └───────[4, 25]────────┘     │     │
   │    │                                 │     │
   │    └────────────[2, 50]──────────────┘     │
   │                                            │
   └─────────────────[1, 100]───────────────────┘

As we’ve seen, all factors of 100 are in pairs. Therefore, if we’ve found one factor i of n, we can get the paired one i’= n/i. That is to say, we don’t need to loop n times. Instead, we check from 1 to the square root of the number n and find all i and i’ pairs. In this way, given n=100, we loop only ten times.

正如我们所见,100的所有因子都是成对的。因此,如果我们已经找到了n的一个因子i,我们可以得到成对的那个i’=n/i。也就是说,我们不需要再循环n次。相反,我们从1到数字的平方根n进行检查,并找到所有ii’的配对。这样,给定n=100,我们只循环10次。

Next, let’s optimize our version 1 method:

接下来,让我们来优化我们的第一版方法。

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;
}

As the code above shows, we’ve used the Math.sqrt() method from the Java standard library to calculate the square root of n.

如上面的代码所示,我们使用了Java标准库中的Math.sqrt()方法来计算n的平方根。

Now, let’s test our second version’s implementation with the same testing data:

现在,让我们用同样的测试数据来测试我们第二个版本的实现。

FACTOR_MAP.forEach((number, expected) -> assertEquals(expected, FactorsOfInteger.getAllFactorsVer2(number)));

If we run the test, it passes. So the optimized version 2 works as expected.

如果我们运行测试,它通过了。因此,优化后的版本2如期工作。

We’ve successfully reduced the factor determination times from n to n‘s square root. It’s a significant improvement. However, there is still room for further optimization. So, next, let’s analyze it further.

我们已经成功地将因子确定时间从n减少到n的平方根。这是一个显著的改进。然而,仍有进一步优化的空间。所以,接下来,让我们进一步分析一下。

5. Further Optimization – Version 3

5.进一步优化 – 第3版

First, let’s do some simple math analysis.

首先,让我们做一些简单的数学分析。

As we know, the given integer n can be either even or odd. If n is an even number, we cannot predicate whether its factors are even or odd. For example, 20’s factors are 1, 2, 4, 5, 10, and 20. So there are even and odd numbers.

我们知道,给定的整数n可以是偶数或奇数。如果n是一个偶数,我们不能预言其因子是偶数还是奇数。例如,20的因子是1、2、4、5、10和20。所以有偶数和奇数之分。

However, if n is an odd number, all its factors must be odd numbers too. For example, 99’s factors are 1, 3, 9, 11, 33, and 99. Therefore, all of them are odd numbers.

然而,如果n是一个奇数,它的所有因子也必须是奇数。例如,99的因子是1、3、9、11、33和99,因此,它们都是奇数。

So, we can adjust the loop’s increment step depending on whether n is odd. As our loop begins from i = 1, if we’re given an odd number, we can set the increment step = 2 to skip checks on all even numbers.

因此,我们可以根据n是否为奇数来调整循环的增量步骤。由于我们的循环是从i = 1开始的,如果我们得到一个奇数,我们可以设置增量step = 2来跳过所有偶数的检查。

Next, let’s implement this idea in version 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;
}

With this optimization, if n is an even number, the loop gets executed sqrt(n) times, the same as version 2.

通过这种优化,如果n是偶数,循环会被执行sqrt(n)次,与版本2相同。

However, if is an odd integer, the loop gets executed sqrt(n)/2 times in total.

然而,如果n是一个奇数整数,那么该循环总共会被执行sqrt(n)/2次。

Finally, let’s test our version 3 solution:

最后,让我们测试一下我们的第三版解决方案。

FACTOR_MAP.forEach((number, expected) -> assertEquals(expected, FactorsOfInteger.getAllFactorsVer3(number)));

The test passes if we give it a run. So, it does the job correctly.

如果我们让它运行一下,测试就会通过。所以,它正确地完成了工作。

6. Conclusion

6.结语

In this article, we’ve created a Java method to find all factors of an integer. Further, we’ve discussed two optimizations to the initial solution.

在这篇文章中,我们创建了一个Java方法来寻找一个整数的所有因子。此外,我们还讨论了对初始解决方案的两项优化。

As usual, all code snippets presented here are available over on GitHub.

像往常一样,这里介绍的所有代码片段都可以在GitHub上找到