Largest Coprime Divisor InterviewBit Solution

Problem: Largest Coprime Divisor

Problem Description:

You are given two positive numbers A and B. You need to find the maximum valued integer X such that:

• X divides A i.e. A % X = 0

• X and B are co-prime i.e. gcd(X, B) = 1

For example,

A = 30 
B = 12 
We return X = 5

Approach

We have two numbers A and B, where, we have to find a number X that should be a factor of A and gcd of (X, B) should be equal to 1.

The method is pretty simple, let's take X = A and keep on dividing X with gcd(X,B) until gcd(X,B) becomes 1. As you can see that, since we are diving X with its factor(gcd(X, B)) so the number will always be a factor of A too, because in the start we have taken X = A. And since B is not changing and X is kept on decreasing, so a time will come when gcd(X, B) = 1, because no matter what, X=1 is always the answer if there is no such number greater than 1.

So we know that gcd(X, B) will eventually become 1. But we still don't prove that the answer we will get would be the maximum answer possible.

As you know that gcd of any two numbers is the multiplication product of all the common prime factors present in both the numbers. So in each step, we are discarding it by dividing X by gcd. So that's why a time will come for sure when there will be no common prime factors present in these numbers.

Time & Space Complexity:

Time Complexity: O(klogN)

- logN is the time complexity for gcd function, and k is the count of times the loop will run, and it depends on the prime factorization of both the numbers A and B.

Space Complexity: O(1)

Solution:

Code in C++