Working on getting your persistence layer right with Spring?

# List All Factors of a Number in Java

Last updated: August 28, 2022

## 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**In this way, given

*n*and find all*i*and*i’*pairs.*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.