Python Program to Check Coprime Numbers

To check if two numbers are coprime in Python, use math.gcd(a, b) == 1 where a and b are the numbers; if the greatest common divisor is 1, they are coprime.

Examples

Inputa=14, b=15

Output14 and 15 are coprime numbers

Inputa=12, b=18

Output12 and 18 are not coprime numbers

Inputa=17, b=4

Output17 and 4 are coprime numbers

How to Think About It

To check if two numbers are coprime, find their greatest common divisor (gcd). If the gcd is 1, it means they share no common factors other than 1, so they are coprime. Otherwise, they are not.

Algorithm

1

Get two numbers as input.

2

Calculate the gcd of the two numbers.

3

If gcd equals 1, return that the numbers are coprime.

4

Otherwise, return that the numbers are not coprime.

Code

python

import math

def are_coprime(a, b):
    return math.gcd(a, b) == 1

# Example usage
num1 = 14
num2 = 15
if are_coprime(num1, num2):
    print(f"{num1} and {num2} are coprime numbers")
else:
    print(f"{num1} and {num2} are not coprime numbers")

Output

14 and 15 are coprime numbers

Dry Run

Let's trace the example where a=14 and b=15 through the code.

1

Input numbers

a = 14, b = 15

2

Calculate gcd

math.gcd(14, 15) returns 1

3

Check gcd value

Since gcd is 1, numbers are coprime

4

Print result

"14 and 15 are coprime numbers"

Iteration	a	b	gcd(a,b)
Final	14	15	1

Why This Works

Step 1: Using gcd to find common factors

The math.gcd function finds the greatest common divisor of two numbers, which is the largest number that divides both without remainder.

Step 2: Coprime condition

If the gcd is 1, it means the numbers have no other common factors except 1, so they are coprime.

Step 3: Return result

The program returns True if gcd is 1, otherwise False, and prints the appropriate message.

Alternative Approaches

Using Euclid's algorithm manually

python

def gcd_manual(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def are_coprime_manual(a, b):
    return gcd_manual(a, b) == 1

num1, num2 = 14, 15
if are_coprime_manual(num1, num2):
    print(f"{num1} and {num2} are coprime numbers")
else:
    print(f"{num1} and {num2} are not coprime numbers")

This method manually implements gcd calculation without importing math, useful for learning or restricted environments.

Check common factors by trial division

python

def are_coprime_trial(a, b):
    for i in range(2, min(a, b) + 1):
        if a % i == 0 and b % i == 0:
            return False
    return True

num1, num2 = 14, 15
if are_coprime_trial(num1, num2):
    print(f"{num1} and {num2} are coprime numbers")
else:
    print(f"{num1} and {num2} are not coprime numbers")

This method checks all possible common factors but is slower for large numbers.

Complexity: O(log(min(a, b))) time, O(1) space

Time Complexity

Calculating gcd using Euclid's algorithm takes O(log(min(a, b))) time because it reduces the problem size quickly each step.

Space Complexity

The algorithm uses constant extra space O(1) as it only stores a few variables.

Which Approach is Fastest?

Using math.gcd is fastest and most readable; manual Euclid's algorithm is similar in speed but requires more code; trial division is slower for large inputs.

Approach	Time	Space	Best For
math.gcd	O(log(min(a,b)))	O(1)	Fast and simple for all inputs
Manual Euclid's algorithm	O(log(min(a,b)))	O(1)	Learning gcd implementation
Trial division	O(min(a,b))	O(1)	Small numbers or educational purposes