find a,b from a given gcd and lcm

Question

The problem was to find two numbers, and , such that their greatest common divisor and their least common multiple would add up to a given number, . Moreover, the difference between the two numbers should be as small as possible, and must be less than or equal to

problem description in codeforces

import math

def prime_factors(num):  
    ret = []
    prime = 1
    while num % 2 == 0:  
        prime *= 2 
        num = num / 2  
    prime  > 1 and ret.append(2)
    for i in range(3, int(math.sqrt(num)) + 1, 2):   
        prime = 1
        while num % i == 0: 
            prime = prime * i 
            num = num / i  
        prime > 1 and ret.append(i//1)
    if num > 2:  
        ret.append(num)
    return ret



def find_ab(gcd,lcm):
    """
        
    """
    return gcd,lcm
        
    

if __name__ == "__main__":
    t = int(input()) #number of test case
    while t:
        x = int(input())
        factors = prime_factors(x)
        print(x)
        print("===")
        for n in factors:
            gcd,lcm = n,x-n
            print("----")
            print(find_ab(gcd,lcm))
        t-=1

Answer 1

Since this was a private contest you cannot see what others have submitted. If it helps here is my submission:

def calc_gcd(a, b):
    if a == 0:
        return b
    return calc_gcd(b % a, a)

t = int(input())
for _ in range(t):
    x = int(input())
    if x % 2 == 0:
        aa, bb = x//2, x//2
    else:
        aa, bb = 1, x-1
        for y in (y for y in range(1, int(x ** 0.5) + 1, 2) if x % y == 0):
            for c in (c for c in (y, x // y) if c < x):
                lcm, gcd = x-c, c
                s = lcm // gcd
                for a in (a for a in range(int(s ** 0.5), 0, -1) if s % a == 0):
                    b = s // a
                    if calc_gcd(a, b) == 1:
                        if gcd*(b - a) < bb - aa:
                            aa, bb = gcd*a, gcd*b
                        break
    print(aa, bb)