Skip to main content

Math Basics

Check if two numbers are co-prime or not Solution In C++/Java/Python/JS

Description

Two numbers A and B are said to be Co-Prime or mutually prime if the Greatest Common Divisor of them is 1. You have been given two numbers A and B, find if they are Co-prime or not.
check-if-two-numbers-are-co-prime-or-not-problem-description

Example

Input : 2 3
Output : Co-Prime

Input : 4 8
Output : Not Co-Prime

Constraints

  • -231 <= A,B <= 231-1
The problem description given to us wants us to check if two numbers A,B are co-primes or not. Figuring out the algorithm requires taking examples and figure out the solution in pen and paper. We will try every possible approach and learn how to solve the mathematical problem.

What do we mean when we say two numbers are co-prime? It means they don’t have any common factors?

Exactly! Two numbers are considered co-prime (or relatively prime) if their only common factor is 1. For example, 8 and 9 are co-prime because their common factors are just {1}, but 8 and 12 are not because they have a common factor of 4.

Now, before we dive into an approach, let's take a moment to think about how we can determine if two numbers are co-prime. How do we generally find common factors of two numbers?

We can list out all the divisors of both numbers and check if they have any in common besides 1.
That’s correct, but it’s not very efficient for larger numbers. Imagine checking all the divisors for two numbers like 123456 and 789012. That would take a lot of time! Instead, can we come up with a more systematic way?

Maybe we can check if their greatest common divisor (GCD) is 1?
That’s a great observation! If two numbers are co-prime, their GCD must be 1. This leads us to our core idea: instead of listing out divisors, we can simply compute the GCD and check if it’s 1.

Understanding GCD

Before we go ahead and implement a solution, let’s understand what GCD is. The greatest common divisor (GCD) of two numbers is the largest number that divides both of them. For example:

  • GCD(8, 12) = 4 because 4 is the largest number that divides both.
  • GCD(7, 13) = 1 because 7 and 13 have no common factors other than 1.

From this, we can conclude that if GCD(a, b) = 1, then a and b are co-prime!

Finding GCD: Recursive Approach

Since, we are breaking down the numbers,we can solve this using recursion, known as Euclid’s Algorithm.

The Euclidean theorem states that for any two integers a and b (where a≥b), their Greatest Common Divisor (GCD) can be determined using the following recursive relation:

GCD(a,b)=GCD(b,a mod  b)

This means that instead of directly finding the GCD, we keep reducing the problem by replacing a with b and b with a mod  b becomes zero. At that point, a is the GCD.

This recursive function keeps reducing the numbers until we reach GCD(x, 0) = x.

For example, let’s compute GCD(48, 18) recursively:

  • GCD(48, 18) → call
    GCD(18, 48 % 18) = GCD(18, 12)
  • GCD(18, 12) → call
    GCD(12, 18 % 12) = GCD(12, 6)
  • GCD(12, 6) → call
    GCD(6, 12 % 6) = GCD(6, 0)
  • Since the second number is now 0, we return 6.

Again, since 6 is not 1, we conclude that 48 and 18 are not co-prime.

Checking Co-Primality
Now that we understand GCD, we can conclude that two numbers a and b are co-prime if and only if GCD(a, b) = 1. Let’s check a few examples:

  • Are 15 and 28 co-prime?
    • GCD(15, 28) = 1 → Yes, they are co-prime!
  • Are 30 and 42 co-prime?
    • GCD(30, 42) = 6 → No, they are not co-prime.
  • Are 17 and 19 co-prime?
    • GCD(17, 19) = 1 → Yes, they are co-prime!

Solution

Let's see the "check if two numbers are co-prime or not code" in C++, Java, Python and JavaScript.

"check if two numbers are co-prime or not" Code in all Languages.
1. check if two numbers are co-prime or not solution in C++ Try on Compiler 
#include <iostream>

using namespace std;

class Solution {
public:
    static int gcdRecursive(int a, int b) {
        // Base case: If 'b' is 0, return 'a' as the GCD.
        if (b == 0) {
            return a;
        }

        // Recursively call the function with 'b' and the remainder of 'a' divided by 'b'.
        return gcdRecursive(b, a % b);
    }
};

int main() {
    int num1, num2;

    // Read two integers from the user.
    cout << "Enter the first number: ";
    cin >> num1;

    cout << "Enter the second number: ";
    cin >> num2;

    // Compute the GCD using the recursive method.
    int result = Solution::gcdRecursive(num1, num2);

    // Print the result.
    cout << result << endl;

    return 0;
}

2. check if two numbers are co-prime or not Solution in Java Try on Compiler 
import java.util.Scanner;

class Solution {
    public static int gcdRecursive(int a, int b) {
        // Base case: If 'b' is 0, return 'a' as the GCD.
        if (b == 0) {
            return a;
        }

        // Recursively call the function with 'b' and the remainder of 'a' divided by 'b'.
        return gcdRecursive(b, a % b);
    }

    /**
     * Main method to read user input and compute GCD.
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Read two integers from the user.
        System.out.print("Enter the first number: ");
        int num1 = scanner.nextInt();

        System.out.print("Enter the second number: ");
        int num2 = scanner.nextInt();

        // Compute the GCD using the recursive method.
        int result = gcdRecursive(num1, num2);

        // Print the result.
        System.out.println("The GCD of " + num1 + " and " + num2 + " is: " + result);

        scanner.close();
    }
}

3. check if two numbers are co-prime or not Solution in Python Try on Compiler 
class Solution:
    @staticmethod
    def gcdRecursive(a, b):
        # Base case: If 'b' is 0, return 'a' as the GCD.
        if b == 0:
            return a

        # Recursively call the function with 'b' and the remainder of 'a' divided by 'b'.
        return Solution.gcdRecursive(b, a % b)

# Main function to take input and execute
def main():
    # Read two integers from the user.
    num1 = int(input("Enter the first number: "))
    num2 = int(input("Enter the second number: "))

    # Compute the GCD using the recursive method.
    result = Solution.gcdRecursive(num1, num2)

    # Print the result.
    print(f"The GCD of {num1} and {num2} is: {result}")

# Run the main function
if __name__ == "__main__":
    main()

4. check if two numbers are co-prime or not solution in JavaScript Try on Compiler 
class Solution {
    static gcdRecursive(a, b) {
        // Base case: If 'b' is 0, return 'a' as the GCD.
        if (b === 0) {
            return a;
        }

        // Recursively call the function with 'b' and the remainder of 'a' divided by 'b'.
        return Solution.gcdRecursive(b, a % b);
    }
}

// Main function to take input and execute
function main() {
    const readline = require("readline").createInterface({
        input: process.stdin,
        output: process.stdout
    });

    readline.question("Enter the first number: ", (num1) => {
        readline.question("Enter the second number: ", (num2) => {
            // Convert input strings to numbers.
            num1 = parseInt(num1);
            num2 = parseInt(num2);

            // Compute the GCD using the recursive method.
            const result = Solution.gcdRecursive(num1, num2);

            // Print the result.
            console.log(`The GCD of ${num1} and ${num2} is: ${result}`);

            readline.close();
        });
    });
}

// Run the main function
main();

Check if two numbers are co-prime or not Complexity Analysis

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

The function gcdRecursive(a, b) follows the Euclidean Algorithm for computing the GCD, which repeatedly reduces the problem size using:

gcd(a,b)=gcd(b,amod b) until b becomes 0.

Breakdown of Recursive Calls

  • The function makes one recursive call per step with the parameters (b, a % b).
  • The number of recursive calls is proportional to the logarithm of the smaller number (min(a, b)).
  • The worst case occurs when b is close to a, but the sequence of reductions follows:

O(log⁡(min⁡(a,b))) because the remainder decreases significantly with each step.

Final Time Complexity: O(log⁡(min⁡(a,b)))

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

Auxiliary Space Complexity

  • Each recursive call adds a new frame to the call stack.
  • The maximum depth of recursion is O(log(min(a, b))), since each recursive step reduces the problem size significantly.
  • There is no additional data structure used, so only stack frames contribute to auxiliary space.

Final Auxiliary Space Complexity: O(log⁡(min⁡(a,b)))

Total Space Complexity

Total space complexity consists of:

  1. Input storage (O(1)): Two integers num1 and num2 are stored in memory.
  2. Auxiliary space (O(log(min(a, b)))): Due to recursive function calls.
  3. Constant space overhead (O(1)): Used for local variables like num1, num2, and result.

Final Total Space Complexity: O(log⁡(min⁡(a,b)))

We achieved a better time complexity, but is there a way we can minimize the extra space required by the call stack. Let's explore !!

Most Optimal Solution (Iterative)

Finding GCD: Iterative Approach

A straightforward way to compute GCD is by using the iterative method based on the division approach. The steps are as follows:

Check if two numbers are co-prime or not Algorithm

Initialize Iteration: Continue looping while b is not zero.

Update Values in Each Iteration:

  • Store the value of b in a temporary variable temp.
  • Assign b as the remainder of a divided by b (b = a % b).
  • Assign a the previous value of b (a = temp).

Exit Condition: The loop terminates when b becomes zero.

Output Result:

  • The final value of a is the Greatest Common Divisor (GCD).
  • Print the computed GCD.

How the Algorithm works ? 

Let’s see this in action with an example: GCD(48, 18)

  • 48 ÷ 18 → remainder = 12 → (18, 12)
  • 18 ÷ 12 → remainder = 6 → (12, 6)
  • 12 ÷ 6 → remainder = 0 → (6, 0)
  • GCD = 6

Since the result is not 1, we know 48 and 18 are not co-prime.

check-if-two-numbers-are-co-prime-or-not-optimal-approach

Solution

Let's see the "check if two numbers are co-prime or not code" in C++, Java, Python and JavaScript.

"check if two numbers are co-prime or not" Code in all Languages.
1. check if two numbers are co-prime or not solution in C++ Try on Compiler 
#include <iostream>

using namespace std;

class Solution {
public:
    static int gcdIterative(int a, int b) {
        // Continue the loop until 'b' becomes zero.
        while (b != 0) {
            // Store the value of 'b' in a temporary variable.
            int temp = b;

            // Assign 'b' as the remainder of 'a' divided by 'b'.
            b = a % b;

            // Assign 'a' as the previous value of 'b'.
            a = temp;
        }

        // Return the computed GCD.
        return a;
    }
};

int main() {
    int num1, num2;

    // Read two integers from the user.
    cout << "Enter the first number: ";
    cin >> num1;

    cout << "Enter the second number: ";
    cin >> num2;

    // Compute the GCD using the iterative method.
    int result = Solution::gcdIterative(num1, num2);

    // Print the result.
    cout << "The GCD of " << num1 << " and " << num2 << " is: " << result << endl;

    return 0;
}

2. check if two numbers are co-prime or not Solution in Java Try on Compiler 
import java.util.Scanner;

class Solution {
    public static int gcdIterative(int a, int b) {
        // Continue the loop until 'b' becomes zero.
        while (b != 0) {
            // Store the value of 'b' in a temporary variable.
            int temp = b;

            // Assign 'b' as the remainder of 'a' divided by 'b'.
            b = a % b;

            // Assign 'a' as the previous value of 'b'.
            a = temp;
        }

        // Return the computed GCD.
        return a;
    }

    /**
     * Main method to read user input and compute GCD.
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Read two integers from the user.
        System.out.print("Enter the first number: ");
        int num1 = scanner.nextInt();

        System.out.print("Enter the second number: ");
        int num2 = scanner.nextInt();

        // Compute the GCD using the iterative method.
        int result = gcdIterative(num1, num2);

        // Print the result.
        System.out.println("The GCD of " + num1 + " and " + num2 + " is: " + result);

        scanner.close();
    }
}

3. check if two numbers are co-prime or not Solution in Python Try on Compiler 
class Solution:
    @staticmethod
    def gcdIterative(a, b):
        # Continue the loop until 'b' becomes zero.
        while b != 0:
            # Store the value of 'b' in a temporary variable.
            temp = b

            # Assign 'b' as the remainder of 'a' divided by 'b'.
            b = a % b

            # Assign 'a' as the previous value of 'b'.
            a = temp

        # Return the computed GCD.
        return a

# Main function to take input and execute
def main():
    # Read two integers from the user.
    num1 = int(input("Enter the first number: "))
    num2 = int(input("Enter the second number: "))

    # Compute the GCD using the iterative method.
    result = Solution.gcdIterative(num1, num2)

    # Print the result.
    print(f"The GCD of {num1} and {num2} is: {result}")

# Run the main function
if __name__ == "__main__":
    main()

4. check if two numbers are co-prime or not solution in JavaScript Try on Compiler 
class Solution {
    static gcdIterative(a, b) {
        // Continue the loop until 'b' becomes zero.
        while (b !== 0) {
            // Store the value of 'b' in a temporary variable.
            let temp = b;

            // Assign 'b' as the remainder of 'a' divided by 'b'.
            b = a % b;

            // Assign 'a' as the previous value of 'b'.
            a = temp;
        }

        // Return the computed GCD.
        return a;
    }
}

// Main function to take input and execute
function main() {
    const readline = require("readline").createInterface({
        input: process.stdin,
        output: process.stdout
    });

    readline.question("Enter the first number: ", (num1) => {
        readline.question("Enter the second number: ", (num2) => {
            // Convert input strings to numbers.
            num1 = parseInt(num1);
            num2 = parseInt(num2);

            // Compute the GCD using the iterative method.
            const result = Solution.gcdIterative(num1, num2);

            // Print the result.
            console.log(`The GCD of ${num1} and ${num2} is: ${result}`);

            readline.close();
        });
    });
}

// Run the main function
main();

Check if two numbers are co-prime or not Complexity Analysis

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

The GCD algorithm implemented here is the Euclidean algorithm, which efficiently computes the GCD of two numbers. It works by repeatedly replacing the larger number with the remainder of the division of the two numbers.

The number of iterations in the while loop is proportional to the number of digits in the smaller number, and its complexity is known to be: O(log⁡(min⁡(a,b)))

This follows from the fact that the Euclidean algorithm reduces the problem size significantly in each step.

  1. The while (b != 0) loop runs until b becomes 0.
  2. In each iteration:
    One modulus operation (a % b),
    One assignment (a = temp),
    Another assignment (b = a % b).
  3. The number of times this loop runs is approximately O(log(min(a, b))), since the size of b decreases rapidly.

Final Time Complexity: O(log⁡(min⁡(a,b)))

Space Complexity: O(1)

Auxiliary Space Complexity

  • The algorithm does not use any extra space apart from a few integer variables (a, b, temp).
  • These require only O(1) space.

Final Auxiliary Space Complexity: O(1)

Total Space Complexity

  • Input Storage: Two integers num1 and num2 (O(1) space).
  • Auxiliary Space: The function only uses O(1) extra space.

Since the function does not create additional data structures, the total space complexity is dominated by the input.

Final Total Space Complexity: O(1)

Final Thoughts

In this discussion, we started with the intuition behind co-prime numbers, then explored how to check their common factors efficiently using GCD. We examined both iterative and recursive ways to find the GCD and finally applied this knowledge to determine if two numbers are co-prime.

The takeaway? Instead of manually checking divisors, we can leverage the power of GCD to quickly determine co-primality. So, the next time we're faced with this problem, we’ll know exactly how to approach it!

Similar Problems

Find Greatest Common Divisor of Array

Given an integer array nums, return the greatest common divisor of the smallest number and largest number in nums.

The greatest common divisor of two numbers is the largest positive integer that evenly divides both numbers.