Given two positive numbers X and Y. Find the maximum value integer A such that: a. A divides X i.e. X % A = 0 b. A and Y are co-prime i.e. gcd(A, Y) = 1

README.md

Problem Statement

Given two positive numbers X and Y. Find the maximum value integer A such that: a. A divides X i.e. X % A = 0 b. A and Y are co-prime i.e. gcd(A, Y) = 1 For example: X = 30
Y = 12 We return A = 5

Solution

Run python solution.py on your terminal

Tests

To run tests, run python test_solution.py on your terminal

Requirements

This solution will work for python3

max_value.py

def find_factors(X):
"""function to find factors of a number"""
    if X == 1: 
      factors = [1]
    else:
      factors = [i for i in range(1,X) if X%i == 0]
    return factors

def check_coprime(Y, num):  

"""function to find if two numbers are coprime"""
    while(num>0 and (Y!=1 and num!=1)):
        if  Y == num:
            return False
        if Y > num: 
            return check_coprime(Y - num, num)  
        return check_coprime(Y, num - Y)
    return True


def solution(X,Y):
    # Step 1, find all numbers that divide X
    factors = find_factors(X)
    factors.reverse() #Since we wish to find maximum number
    #Find the maximum number in factors that is coprime with Y
    for f in factors:
        if check_coprime(Y,f) == True:
            answer = f 
            break
        else:
            continue
        return('No such number exists')
    return answer

if __name__ == "__main__":
    X, Y = map(int, input('Enter space seperated values of X and Y: ').split())
    print(solution(X,Y))

test_max_value.py

import unittest
import solution

class TestSolution(unittest.TestCase):
    def test_findfactors(self):
        self.assertEqual(solution.find_factors(1),[1])
        self.assertEqual(solution.find_factors(2),[1])
        self.assertEqual(solution.find_factors(5),[1])
        self.assertEqual(solution.find_factors(12),[1,2,3,4,6])
    
    def test_checkcoprime(self):
        self.assertEqual(solution.check_coprime(1,1),True)
        self.assertEqual(solution.check_coprime(1,5),True)
        self.assertEqual(solution.check_coprime(7,3),True)
        self.assertEqual(solution.check_coprime(12,16),False)

    def test_solution(self):
        self.assertEqual(solution.solution(1,1),1)
        self.assertEqual(solution.solution(30,12),5)
        self.assertEqual(solution.solution(44,16),11)
        self.assertEqual(solution.solution(16,27),8)
        

if __name__ == '__main__':
    unittest.main()