Find Prime Factors in Java

Beginner
⏱️ 12 min read
📚 Updated: Aug 2026
🎯 3 Code Examples
🚀 Live Preview
Number Theory
Overview

What You’ll Learn

Prime factors are the prime numbers that multiply to make n. For example, 56 = 2 × 2 × 2 × 7. This tutorial covers trial division (simple and sqrt-optimized), a live factorizer, worked Java examples, edge cases, and complexity.

Definition

Prime ÷ n

Primes that divide n evenly.

Trial Division

Peel factors

Divide out each i while it fits.

Repeats

Inner while

Capture 2, 2, 2 in 56.

Sqrt Speedup

Fewer checks

Stop near sqrt; print leftover.

Live Preview

Try 56 / 360

See factors and product check.

n >= 2

Domain

Factorization starts at 2.

Introduction

Prime factorization rewrites an integer n >= 2 as a product of primes. By the fundamental theorem of arithmetic, that product is unique up to order.

Interviews usually want trial division: try candidate divisors in increasing order, divide out each one completely, then move on. A faster variant peels 2s first, then odd candidates up to sqrt(x), and prints any leftover prime.

Why it matters?

It is a core number-theory skill that feeds prime checks, GCD tricks, and many coding-interview warm-ups.

Key Highlights

Unique Product

One prime multiset per n > 1.

Peel Completely

Inner while for repeats.

n >= 2

Reject 0, 1, negatives.

Sorted Output

Factors rise naturally.

In short: for each candidate i, divide out every copy of i; leftovers are primes.

Foundation

📝 Problem & Approach

Given an integer n >= 2, print (or return) its prime factors in non-decreasing order.

java
// 56  -> 2 2 2 7
// 17  -> 17          (already prime)
// 360 -> 2 2 2 3 3 5
// 1   -> invalid for this tutorial

Inputs & Outputs

ItemTypeDescription
nintInteger to factor (n >= 2).
Printed factorsintsPrime multiset in ascending order.
Optional listList<Integer>Same factors as a returned collection.

Minimal workflow

Pseudocode
procedure display_prime_factors(n):
    if n < 2:
        stop
    x = n
    for i from 2 while i <= x:
        while x mod i == 0:
            output i
            x = x / i

Method comparison

MethodIdeaNotes
Naive trialTry i = 2, 3, … while i <= xClearest for beginners
Sqrt trialPeel 2s; odds while i*i <= xFewer checks; leftover prime
Sieve helpersPrecompute primes for many nBetter for bulk queries
Cheat Sheet

⚡ Quick Reference

GoalPattern
Validateif (n < 2) return;
Divide out iwhile (x % i == 0) { …; x /= i; }
Peel twoswhile (x % 2 == 0)
Odd candidatesi = 3; i += 2
Sqrt boundwhile ((long) i * i <= x)
Leftover primeif (x > 1) System.out.print(x);
Compare

📋 Naive vs Fast vs Return List

Same factorization — different packaging.

Naive
i <= x

Easiest to dry-run

Fast
i*i <= x

Interview upgrade path

List return
factors.add(i)

Reuse factors later

No is_prime?
order peels

Composites never survive

Context

When This Problem Shows Up

Reach for factorization whenever you need the prime building blocks of n.

  1. Interview warm-ups

    Classic trial-division prompt.

  2. Bridge to primes

    Same divisor mindset as prime checks.

  3. GCD / LCM prep

    Factors explain shared primes.

  4. Teaching uniqueness

    Show the fundamental theorem live.

  5. Not for n < 2

    Reject 0, 1, and negatives here.

Key benefit: one nested-loop pattern that explains why composites never need an explicit is_prime helper.

Interactive

🔮 Live Preview

Uses optimized factorization (2s first, then odd divisors) and verifies the product.

Use numbers between 2 and 1000000.

Live result
Press “Factorize” to list prime factors.
Hands-On

Examples Gallery

Three complete Java programs — simple trial division for 56, a faster sqrt-style version, and a helper that returns factors as a list. Click View Output to reveal sample console results.

📚 Getting Started

Readable nested loops that peel every factor.

Example 1 — Straightforward Trial Division

Simple readable method using nested loops.

java
public class PrimeFactors {
    static boolean dividesEvenly(int a, int b) {
        return a % b == 0;
    }

    static void displayPrimeFactors(int n) {
        if (n < 2) {
            System.out.println("Enter an integer n >= 2 (got " + n + ").");
            return;
        }

        System.out.print("Prime factors of " + n + " are: ");
        int x = n;

        int i = 2;
        while (i <= x) {
            while (dividesEvenly(x, i)) {
                System.out.print(i + " ");
                x /= i;
            }
            i++;
        }

        System.out.println();
    }

    public static void main(String[] args) {
        displayPrimeFactors(56);
    }
}

How It Works

Starting at i = 2, the inner while removes three factors of 2, leaving 7. Then i reaches 7, which divides once, and x becomes 1.

⚡ Faster Trial Division

Fewer candidates with a sqrt bound and a leftover prime.

Example 2 — Faster Trial (2 Then Odd Up to Sqrt)

Fewer divisor checks by handling 2 separately and testing odd candidates only.

java
public class PrimeFactorsFast {
    static void displayPrimeFactorsFast(int n) {
        if (n < 2) {
            System.out.println("Enter an integer n >= 2 (got " + n + ").");
            return;
        }

        System.out.print("Prime factors of " + n + " are: ");
        int x = n;

        while (x % 2 == 0) {
            System.out.print("2 ");
            x /= 2;
        }

        int i = 3;
        while ((long) i * i <= x) {
            while (x % i == 0) {
                System.out.print(i + " ");
                x /= i;
            }
            i += 2;
        }

        if (x > 1) {
            System.out.print(x + " ");
        }

        System.out.println();
    }

    public static void main(String[] args) {
        displayPrimeFactorsFast(56);
    }
}

How It Works

After removing factors of 2, x is 7. Because 3 * 3 > 7, the odd loop stops and the leftover 7 is printed.

Example 3 — Return Factors as a List

Collect factors for reuse instead of only printing them.

java
import java.util.ArrayList;
import java.util.List;

public class PrimeFactorsList {
    static List<Integer> primeFactors(int n) {
        List<Integer> factors = new ArrayList<>();
        if (n < 2) {
            return factors;
        }
        int x = n;

        while (x % 2 == 0) {
            factors.add(2);
            x /= 2;
        }

        int i = 3;
        while ((long) i * i <= x) {
            while (x % i == 0) {
                factors.add(i);
                x /= i;
            }
            i += 2;
        }

        if (x > 1) {
            factors.add(x);
        }
        return factors;
    }

    public static void main(String[] args) {
        int[] values = { 56, 17, 360 };
        for (int value : values) {
            System.out.println(value + " -> " + primeFactors(value));
        }
    }
}

How It Works

Same peeling logic as Example 2, but factors land in a list you can product-check, count, or pass to other helpers.

🧠 How the Algorithm Decides

1

Require n >= 2

Factorization is undefined for smaller values here.

Guard
2

Try candidate i

Start at 2 (or peel 2s, then odds).

Search
3

Divide while divisible

Print/append i and shrink x each time.

Peel
=

Finish when x is 1

(Or print leftover prime in the fast version.)

Trace

🔎 Worked Walkthrough — 56

Trace the naive peel for n = 56.

ix beforeActionx after
256print 2 three times7
3 … 67no division7
77print 7 once1

Result: 2 2 2 7. Product check: 2×2×2×7 = 56.

Use Cases

Where prime factorization shows up beyond the interview prompt.

1. Interview Classics

Trial division and nested loops.

Example: factor 56.

2. Teaching Uniqueness

One prime product per n > 1.

Example: facts callout.

3. Bridge to Primes

Same divisor thinking as is_prime.

Example: next page.

4. GCD / LCM Prep

Shared primes explain GCD.

Example: related GCD.

5. Reusable Lists

Return factors for later math.

Example: Example 3.

6. Bulk Queries

Sieve primes when factoring many n.

Example: notes tip.

Pro Tip: say “I’ll peel smallest factors completely so composites never need an is_prime call” before coding.

Advantages

Why trial division works well for beginners and interviews.

  1. 1. Easy to Trace

    Dry-run 56 on paper and watch x shrink.

  2. 2. No Extra is_prime

    Ascending order keeps composites from sticking.

  3. 3. Clear Upgrade Path

    Move from naive to sqrt when asked.

  4. 4. Sorted Naturally

    Factors emerge in non-decreasing order.

Pro Tip: start with the naive version in interviews, then offer the sqrt optimization unprompted.

Usage Tips

Small habits that keep factorization interview-ready.

  1. 1. Guard n >= 2

    Reject invalid domains early.

  2. 2. Peel Completely

    Inner while captures repeated primes.

  3. 3. Product-Check

    Multiply factors back to n for confidence.

  4. 4. Remember Leftover

    Fast version must print x if x > 1.

  5. 5. Return Lists When Useful

    Printing alone is fine; lists compose better.

Pro Tip: sanity-check 56, 17, and 360 — if those three match, your peel logic is solid.

Common Pitfalls

Mistakes that commonly break prime-factor programs.

  1. 1. Skipping the Inner While

    Printing each divisor only once.

    → Keep dividing while x % i == 0.

  2. 2. Forgetting Leftover Prime

    Sqrt version stops and drops the last prime.

    → if x > 1: print/append x.

  3. 3. Factoring 1 or 0

    Undefined domain for this tutorial.

    → Require n >= 2.

  4. 4. Mixing In Floating-Point Division

    Casting to double can leave non-integers and break later checks.

    → Keep x and i as int/long so /= is integer division.

  5. 5. Unnecessary is_prime

    Extra prime tests slow and complicate the code.

    → Rely on ordered peeling.

Edge Cases

Handle these before claiming factorization is complete.

n < 2

Reject

0, 1, and negatives are out of scope.

Prime n

Single factor

Output is just n itself (e.g. 17).

Powers of 2

Repeated peels

Inner while must run many times.

56

Classic yes

2 2 2 7.

360

Mixed primes

2 2 2 3 3 5.

Large prime leftover

Fast path care

Remember if x > 1 after the loop.

Theory

⚖️ Facts Worth Knowing

Handy follow-ups interviewers sometimes ask.

  • Fundamental theorem. Every n > 1 has a unique prime factorization (order ignored).
  • Why no is_prime. Smaller primes are removed first, so composite i never divides what remains.
  • Sqrt bound. Any composite leftover would have a factor <= sqrt(x).
  • Java ints. Prefer long for large n so i * i does not overflow.
Drill

🎯 Practice Problems

Try these variations to lock in the pattern.

1. Factor 56

  • Expect 2 2 2 7
  • Product-check

2. Factor 17

  • Single prime
  • Leftover path

3. Factor 360

  • 2 2 2 3 3 5
  • Match Example 3

4. Reject 1

  • Guard n >= 2
  • No empty loop tricks
Important

Notes

  • Definition: prime factors are primes that multiply to n.
  • Loop: for each i, while x % i == 0, emit i and divide.
  • Fast path: peel 2s, then odds while i*i <= x, then leftover.
  • If factoring many numbers, precomputed primes are faster. Related topics: prime check, composite numbers, and GCD use similar divisor logic.

Quick Takeaway: peel candidate factors completely in ascending order; the product of printed primes is n.

Analysis

⏱️ Time and Space Complexity

ApproachTimeExtra space
Naive trial (i <= x)O(n) worstO(1) (+ output)
Sqrt trialO(sqrt(n))O(1) (+ output)
Many queries + sieveamortized betterdepends on bound

For interview demos, start naive; upgrade to sqrt when asked about speed.

Wrap Up

🎉 Conclusion

Prime factorization rewrites n >= 2 as a unique product of primes. Peel candidates with an inner while, upgrade to a sqrt bound when needed, and always handle leftover primes in the fast path.

Practice the three examples above, then continue to checking prime numbers.

Divide out every copy of each i; the remaining primes multiply back to n.

View Examples Gallery Continue to Prime Number
Pro Tips

💡 Best Practices

✅ Do

  • Require n >= 2
  • Peel each factor completely
  • Use integer division /=
  • Handle leftover in sqrt version
  • Product-check sample cases

❌ Don’t

  • Factor 0 or 1 here
  • Skip repeated peels
  • Forget leftover primes
  • Use float division
  • Add needless isPrime calls
Summary

Key Takeaways

Knowledge Unlocked

Five things to remember about prime factors

Factor n the interview-friendly way.

5
Core concepts
× 01

Rule

primes of n

Definition
/ 02

Peel

while % i

Loop
√ 03

Fast

i*i <= x

Optimize
2 04

Domain

n >= 2

Guard
O 05

Cost

O(√n)

Analysis
🎯 You’re ready to find prime factors in Java
Review Quick Reference →

❓ Frequently Asked Questions

A prime factor is a prime number that divides the given number evenly.
Trying factors in order and dividing repeatedly ensures composite candidates stop dividing after smaller primes are removed.
To capture repeated factors like 2, 2, 2 in 56.
Prime factorization here is defined for n >= 2.
Yes, factors print in non-decreasing order.
It tests fewer candidates by stopping around sqrt(x) and handling leftover prime at the end.
2 × 2 × 2 × 7.
The algorithm prints n itself as the only factor.
If factoring many numbers, precomputed primes are faster.

Did you Know? 🔊

Every integer greater than 1 can be written as a product of primes in exactly one way (ignoring order).

Continue to Prime Number

Learn how to check whether a number is prime in Java.

Prime number tutorial →

About the author

Mari Selvan M P
Mari Selvan M P 🔗

Developer, cloud engineer, and technical writer

  • Experience 12 years building web and cloud systems
  • Focus Full Stack Development, AWS, and Developer Education

I write practical tutorials so students and working developers can learn by doing—from databases and APIs to deployment on AWS.

AWS Certified Developer – Associate (Credly)

8 people found this page helpful

Java Program to Check Power of 3 Java Program to Check Prime Number