Java Programs›Numbers›Find Smallest Prime Factor

Find Smallest Prime Factor in Java

beginner· Numbers · Number Theory

Problem

The smallest prime factor of a number is the smallest prime that divides it evenly — every number's smallest prime factor is at most its own square root, unless the number is itself prime.

Given a number, find its smallest prime factor.

Input

91

Output

Smallest prime factor: 7

Java Program

Java

public class SmallestPrimeFactor {
    public static void main(String[] args) {
        int n = 91;
        int smallest = n; // covers the case where n itself is prime

        for (int i = 2; (long) i * i <= n; i++) {
            if (n % i == 0) {
                smallest = i;
                break; // the first divisor found is always the smallest prime factor
            }
        }

        System.out.println("Smallest prime factor: " + smallest);
    }
}

▶ Run Code

Output

Smallest prime factor: 7

Core Logic

Trying candidate divisors from smallest to largest and stopping at the very first one that divides evenly finds the smallest prime factor directly, without checking anything larger.

How It Works

1smallest starts out set to n itself, covering the case where n is prime and has no smaller factor.
2The loop tries every candidate i from 2 up to √n.
3The first candidate where n % i == 0 is the smallest prime factor — it's recorded and the loop breaks immediately.
4If no divisor is found by the time the loop ends, smallest keeps its initial value of n, since that means n is prime.

For 91, the candidates 2 through 6 all fail to divide it evenly, but 7 does — 91 / 7 = 13 — so 7 is reported as the smallest prime factor.

💡

Key Point: The very first divisor found while counting up from 2 is always prime — if it weren't, one of its own smaller factors would have already been found first.

Complexity

Time Complexity: O(√n)Space Complexity: O(1)

Why: The loop stops at the very first divisor found, so in the worst case it still only needs to try candidates up to √n before concluding n itself is prime.

Key Concepts

trial divisionsquare-root boundearly exit with break

Approach 2: Java 8

Java

import java.util.stream.IntStream;

public class SmallestPrimeFactorStream {
    public static void main(String[] args) {
        int n = 91;
        // Keeps only divisors of n, then takes the smallest one found
        int smallest = IntStream.rangeClosed(2, (int) Math.sqrt(n))
            .filter(i -> n % i == 0)
            .findFirst()
            .orElse(n);

        System.out.println("Smallest prime factor: " + smallest);
    }
}

▶ Run Code

Output

Smallest prime factor: 7

Core Logic

The same smallest-divisor search can be expressed as a stream — filter for divisors, then take the first one found.

How It Works

1IntStream.rangeClosed(2, (int) Math.sqrt(n)) generates every candidate divisor up to the square-root bound.
2.filter(i -> n % i == 0) keeps only the candidates that divide n evenly.
3.findFirst() returns the smallest surviving candidate, wrapped in an OptionalInt.
4.orElse(n) falls back to n itself if no divisor was found, meaning n is prime.

For 91, the filtered stream keeps only 7 and 13, and findFirst() returns the smaller one, 7.

💡

Key Point: findFirst() short-circuits at the first divisor found, the same early-exit behavior as the loop's break.

Complexity

Time Complexity: O(√n)Space Complexity: O(1)

Why: findFirst() short-circuits at the first divisor found, the same early-exit behavior as the loop's break.

Key Concepts

StreamIntStream.rangeClosed()findFirst()

← Previous

Find Nth Prime Number

Find Sum of Prime Numbers

Related Programs

Numbersintermediate

Calculate Combination (nCr)

Numbersintermediate

Calculate Permutation (nPr)

Numbersintermediate

Calculate Power Using Recursion

Numbersbeginner

Check Abundant Number

Numbersbeginner

Check Armstrong Number