Find Factors of a Number in Java: Brute Force vs Optimized

Introduction

Finding the factors of a number is one of the most fundamental problems in number theory and programming. It builds directly on concepts you've already encountered while solving prime number, perfect number, GCD, and LCM problems because all of them rely on identifying a number's divisors.

A straightforward solution simply checks every number from 1 to the given number. While this is easy to understand, it performs unnecessary work. A much faster solution uses the same square-root divisor pair optimization you've already seen in prime-number checking. The only additional challenge is maintaining the factors in sorted order, since divisor pairs are naturally discovered out of sequence.

In this guide, you'll learn the brute-force approach, the optimized square-root method, how to print factors in sorted order efficiently, and the related—but different—problem of finding the prime factors of a number.

What Are Factors of a Number?

A factor (or divisor) of a number is any positive integer that divides the number exactly without leaving a remainder.

For example, the factors of 36 are:

1 2 3 4 6 9 12 18 36

Each of these numbers divides 36 evenly.

Examples:

• 36 ÷ 4 = 9

• 36 ÷ 6 = 6

• 36 ÷ 18 = 2

Every positive number always has at least two factors:

• 1

• The number itself

Prime numbers have exactly these two factors.

Method 1: Brute Force Approach

The simplest solution checks every number from 1 to the given number.

Java Program

public class FactorsBruteForce {

    public static void main(String[] args) {

        int num = 36;

        System.out.println("Factors of " + num + ":");

        for (int i = 1; i <= num; i++) {

            if (num % i == 0) {
                System.out.print(i + " ");
            }

        }
    }
}

Output

Factors of 36:
1 2 3 4 6 9 12 18 36

How It Works

The program checks every integer between 1 and 36.

If the remainder is zero:

num % i == 0

then i is a factor and gets printed.

Because the loop moves from small to large numbers, the output is automatically sorted.

Drawback

This solution performs:

36 checks

for the number 36.

For very large numbers, this becomes inefficient.

Method 2: Optimized Using Square Root (Divisor Pairs)

Factors always occur in pairs.

For example:

36

1 × 36

2 × 18

3 × 12

4 × 9

6 × 6

Once you reach √36 = 6, every remaining factor has already appeared as a partner.

Therefore, you only need to check numbers up to the square root.

Java Program

public class FactorsOptimized {

    public static void main(String[] args) {

        int num = 36;

        System.out.println("Factors of " + num + ":");

        for (int i = 1; i <= Math.sqrt(num); i++) {

            if (num % i == 0) {

                System.out.print(i + " ");

                int pairedFactor = num / i;

                if (pairedFactor != i) {
                    System.out.print(pairedFactor + " ");
                }
            }
        }
    }
}

Output

Factors of 36:
1 36 2 18 3 12 4 9 6

Why the Output Is Unsorted

The algorithm prints factor pairs together.

Instead of:

1 2 3 4 6 9 12 18 36

it prints:

1 36

2 18

3 12

4 9

6

The optimization improves performance but sacrifices ordering.

Method 3: Printing Factors in Sorted Order

To keep the square-root optimization while producing sorted output:

• Store the smaller factors separately.

• Store the larger paired factors separately.

• Reverse the larger list.

• Combine both lists.

Java Program

import java.util.ArrayList;
import java.util.Collections;

public class FactorsSorted {

    public static void main(String[] args) {

        int num = 36;

        ArrayList<Integer> smallerFactors = new ArrayList<>();
        ArrayList<Integer> largerFactors = new ArrayList<>();

        for (int i = 1; i <= Math.sqrt(num); i++) {

            if (num % i == 0) {

                smallerFactors.add(i);

                int pairedFactor = num / i;

                if (pairedFactor != i) {
                    largerFactors.add(pairedFactor);
                }
            }
        }

        Collections.reverse(largerFactors);

        smallerFactors.addAll(largerFactors);

        System.out.println(smallerFactors);
    }
}

Output

[1, 2, 3, 4, 6, 9, 12, 18, 36]

How It Works

During the loop:

Small factors are collected as:

1 2 3 4 6

Large factors are collected as:

36 18 12 9

Reversing the second list gives:

9 12 18 36

Appending both lists produces perfectly sorted output.

Method 4: Finding Prime Factors

Finding all factors and finding prime factors are different problems.

Instead of listing every divisor, prime factorization repeatedly divides the number by its smallest prime factor.

Example:

36

=

2 × 2 × 3 × 3

Java Program

public class PrimeFactors {

    public static void main(String[] args) {

        int num = 36;

        System.out.println("Prime factors of " + num + ":");

        for (int i = 2; i <= num; i++) {

            while (num % i == 0) {

                System.out.print(i + " ");

                num /= i;
            }
        }
    }
}

Output

Prime factors of 36:
2 2 3 3

How It Works

Starting from 2, whenever a divisor is found:

• Print it.

• Divide the number.

• Continue dividing until it no longer divides evenly.

Then move to the next possible factor.

How Java Handles This Internally

Methods 1, 2 and 4

Variables like:

• num

• i

• pairedFactor

are primitive integers stored on the stack.

Math.sqrt() performs a floating-point calculation internally.

Method 3

ArrayList<Integer> objects are allocated on the heap.

Each primitive int is automatically converted into an Integer object (autoboxing).

Collections.reverse() rearranges the existing list in place without creating another list.

Real-Life Analogy

Imagine you have 36 square tiles.

You want every possible rectangular arrangement.

Possible dimensions are:

1 × 36

2 × 18

3 × 12

4 × 9

6 × 6

Each pair represents one pair of factors of 36.

Finding factors is simply finding every possible rectangle whose area equals the original number.

Comparison Table

Best Practices

• Prefer the square-root optimization over brute force.

• Avoid double-counting when the number is a perfect square.

• Understand the difference between factors and prime factors.

• Consider using TreeSet<Integer> if automatic sorting is preferred.

• In performance-sensitive code, use:

i * i <= num

instead of

i <= Math.sqrt(num)

to avoid repeated floating-point calculations.

Common Mistakes

Assuming the Optimized Method Prints Sorted Factors

It does not.

Divisor pairs naturally appear in mixed order.

Double-Counting the Square Root

For perfect squares like:

36

49

64

the square root should only appear once.

Always check:

pairedFactor != i

before printing the second factor.

Confusing Factors with Prime Factors

These are different problems.

Example:

All factors of 36:

1 2 3 4 6 9 12 18 36

Prime factors:

2 2 3 3

Ignoring Autoboxing

Using ArrayList<Integer> converts primitive integers into wrapper objects.

This is usually acceptable but introduces a small overhead.

Not Testing Perfect Squares

Perfect squares reveal bugs related to duplicate factors.

Always test values like:

• 25

• 36

• 49

• 64

Expert Tips

A strong interview answer is:

"To find all factors efficiently, I only check numbers up to the square root because every divisor below the square root has a corresponding paired divisor above it. This reduces the complexity from O(n) to O(√n). If sorted output is required, I store the smaller and larger divisor pairs separately, reverse the larger list, and then combine both lists. If the requirement changes to prime factorization, I'd use repeated division instead, since that's a different problem."

Mentioning both the square-root optimization and the sorting challenge demonstrates a deeper understanding of factor-related problems.

Pros and Cons

Frequently Asked Questions

What is the fastest way to find all factors of a number?

Use the square-root optimization, checking divisors only up to √n and adding both divisor pairs.

Why does the optimized method produce unsorted output?

Because divisor pairs are printed together:

1 36

2 18

3 12

rather than strictly in ascending order.

How can I keep the factors sorted?

Store:

• smaller factors

• larger factors

Reverse the larger list and append it to the smaller list.

What is the difference between factors and prime factors?

Factors include every divisor.

Prime factors include only the prime numbers whose product equals the original number.

How do I find prime factors?

Repeatedly divide the number by increasing candidate values beginning with 2 until the number becomes 1.

What is the time complexity of the optimized method?

O(√n)

Why check whether the paired factor equals the loop variable?

To avoid printing the square root twice for perfect squares.

Can I use a TreeSet instead of ArrayLists?

Yes.

A TreeSet automatically stores elements in sorted order.

Is finding factors a common interview question?

Yes.

It is commonly used to test whether candidates know the square-root divisor-pair optimization.

What are the factors of a prime number?

Exactly two:

• 1

• The number itself

Can factors be negative?

Mathematically, yes.

For example:

-6

is also a divisor of 36.

However, programming problems almost always consider only positive factors.

How are factors related to GCD and LCM?

Factors form the foundation of both concepts:

• GCD is the largest common factor.

• LCM is closely related through the factorization of numbers and the formula involving GCD.