1. Overview
In this tutorial, we’ll write a Java program to find all the factors of a given integer.
2. Introduction to the Problem
Before we start writing the Java code, let’s understand what an integer’s factors are.
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.
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.
Now that we understand the concept of factors, let’s create a Java program to find all the factors of a given integer.
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
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.
Implementing this idea in Java isn’t a challenging job for us:
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:
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.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.
Next, let’s see how to optimize the version 1 implementation.
4. Optimization – Version 2
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:
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.
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.
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.
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.
5. Further Optimization – Version 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.
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.
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.
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.
However, if n is an odd integer, the loop gets executed sqrt(n)/2 times in total.
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
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.
As usual, all code snippets presented here are available over on GitHub.
