Java Programs›Numbers›Check Co-Prime Numbers

Check Co-Prime Numbers in Java

beginner· Numbers · Number Theory

Problem

Two numbers are co-prime (or relatively prime) when the only positive integer that divides both of them evenly is 1 — they don't need to be prime themselves, just share no other common factor.

Given two integers, determine whether they are co-prime.

Input

8, 15

Output

Co-prime: true

Java Program

Java

public class CoPrimeCheck {
    public static void main(String[] args) {
        int a = 8, b = 15;
        boolean isCoPrime = true;

        for (int i = 2; i <= Math.min(a, b); i++) {
            if (a % i == 0 && b % i == 0) {
                isCoPrime = false;
                break; // found a shared factor besides 1, no need to check further
            }
        }

        System.out.println("Co-prime: " + isCoPrime);
    }
}

▶ Run Code

Output

Co-prime: true

Core Logic

Checking every possible common divisor from 2 up to the smaller number, and stopping the instant one is found, confirms whether the numbers share any factor besides 1.

How It Works

1isCoPrime starts as true, assuming no common factor exists until proven otherwise.
2The loop tries every candidate i from 2 up to Math.min(a, b) — 1 is skipped, since every pair of numbers trivially shares it.
3a % i == 0 && b % i == 0 checks whether i divides both numbers evenly.
4The first shared factor found sets isCoPrime to false and exits the loop immediately with break.

For 8 and 15, no number from 2 to 8 divides both evenly, so isCoPrime stays true.

💡

Key Point: Starting the search at 2 instead of 1 is what makes this meaningful — every pair of integers shares 1 as a divisor, so co-primality is really about whether anything larger is also shared.

Complexity

Time Complexity: O(min(a, b))Space Complexity: O(1)

Why: In the worst case the loop checks every candidate from 2 up to the smaller number, using only a single boolean flag regardless of the numbers' size.

Key Concepts

for loopmodulo operatorearly exit with break

Approach 2: Using GCD

Java

public class CoPrimeCheckGCD {
    static int gcd(int a, int b) {
        if (b == 0) return a; // base case: a is the GCD once b runs out
        return gcd(b, a % b);
    }

    public static void main(String[] args) {
        int a = 8, b = 15;
        // Two numbers are co-prime exactly when their GCD is 1
        boolean isCoPrime = gcd(a, b) == 1;
        System.out.println("Co-prime: " + isCoPrime);
    }
}

▶ Run Code

Output

Co-prime: true

Core Logic

Two numbers are co-prime exactly when their greatest common divisor is 1 — computing the GCD directly skips checking individual candidate factors altogether.

How It Works

1gcd(a, b) computes the greatest common divisor using the Euclidean algorithm.
2gcd(a, b) == 1 checks whether that GCD is exactly 1, which is the definition of co-primality.
3No candidate factors are tried one by one — the Euclidean algorithm reaches the GCD directly.

For 8 and 15, gcd(8, 15) reduces to 1, so isCoPrime is true.

💡

Key Point: This reaches the answer in a handful of steps regardless of how large the numbers are, unlike the brute-force version whose cost grows with the smaller number.

Complexity

Time Complexity: O(log(min(a, b)))Space Complexity: O(log(min(a, b)))

Why: Computing gcd() via the Euclidean algorithm takes logarithmic time and recursion depth in the smaller number, much faster than trying every candidate factor.

Key Concepts

GCDEuclidean algorithm

Approach 3: Java 8

Java

import java.util.stream.IntStream;

public class CoPrimeCheckStream {
    public static void main(String[] args) {
        int a = 8, b = 15;

        // No candidate from 2 up to the smaller number divides both evenly
        boolean isCoPrime = IntStream.rangeClosed(2, Math.min(a, b))
            .noneMatch(i -> a % i == 0 && b % i == 0);

        System.out.println("Co-prime: " + isCoPrime);
    }
}

▶ Run Code

Output

Co-prime: true

Core Logic

Streaming every candidate from 2 up to the smaller number and confirming none divides both evenly expresses the same brute-force search as the primary approach, without an explicit loop or break.

How It Works

1IntStream.rangeClosed(2, Math.min(a, b)) generates the same candidate range the manual loop iterated over.
2.noneMatch(i -> a % i == 0 && b % i == 0) checks that no candidate in that range divides both a and b evenly.
3noneMatch() short-circuits the instant it finds a shared factor, the same early exit the manual break provided.

For 8 and 15, streaming candidates 2 through 8 finds none that divide both numbers, so noneMatch() returns true.

💡

Key Point: This is the stream equivalent of the brute-force primary approach, not the GCD alternate — it still checks every candidate factor, just declaratively instead of with a manual loop and flag.

Complexity

Time Complexity: O(min(a, b))Space Complexity: O(1)

Why: The stream still tests every candidate from 2 up to the smaller number in the worst case and short-circuits on the first shared factor, the same bound as the manual loop.

Key Concepts

IntStreamnoneMatch()lambda expression

← Previous

Check Circular Prime

Check Deficient Number

Related Programs

Numbersintermediate

Calculate Combination (nCr)

Numbersintermediate

Calculate Permutation (nPr)

Numbersintermediate

Calculate Power Using Recursion

Numbersbeginner

Check Abundant Number

Numbersbeginner

Check Armstrong Number