Minimum LCM in python

1

Here given an integer n, find positive integers a and b such that a+b=n
and LCM(a,b) is the minimum value possible.

Input
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤10).
Each test case consists of a single integer n (2≤n≤10^9).

3
4
6
9

Output
For each test case, output two positive integers a and b, such that a+b=n and LCM(a,b) is the minimum possible.

2 2
3 3
3 6

Note

For the first test case, the numbers we can choose are 1,3 or 2,2. LCM(1,3)=3 and LCM(2,2)=2, so we output 2 2.
For the second test case, the numbers we can choose are 1,5, 2,4, or 3,3. LCM(1,5)=5, LCM(2,4)=4, and LCM(3,3)=3, so we output 3 3.
For the third test case, LCM(3,6)=6.
It can be shown that there are no other pairs of numbers which sum to 9 that have a lower LCM.

Here is my code:

import math
def lcm(a, b):
    return abs(a*b) // math.gcd(a, b)
for x in range(int(input())):
    c = []
    a = int(input())
    for i in range(a//2):
        c.append([lcm(i+1,a-(i+1)),i+1,a-(i+1)])
    print(min(c)[1],end=" ")
    print(min(c)[2])

But my code is time limit Time limit exceeded on pretest 4 .How can i make my code more efficient ?

I try to solve this problem from codeforces.You can take a look of original problem from here.

1 Like
2

Hello @Plabon_Kumer_Sarker,
[Updated]
Goal: We have to find two positive integers x and y which adds upto n i.e. x+y=n and LCM(x,y) has the least value.

Approach: For x and y to have the least LCM, we have to choose y such that it is a factor of x, i.e. y = Cx where C is some constant.

Also, x + y = n ----------------> equation 1
equation 1 can be re-written as:
x + Cx = n
=> x(1+C) = n
=> x = n/(1+C) -----------------------------> equation 2

Since x is an integer, we infer that x must be a multiple of n.
For: x+y =n and LCM(x,y) to be the least the best case would be when x=y. In that case C=1.
So, in equation 2 I want C to be as small as possible.
It means 1+C is the least value which completely divides the number n i.e. n%(1+C) == 0.

Therefore, 1+C can be found as the minimum no, which completely divides n.
This gives us x which is n/(1+C).
Now, we can calculate y as n-x.

Exception: In case no number can completely divide the number n, it is a prime number so, the best possible x+y for a prime number would be (1,n-1)

You can check the code below.

# B. Omkar and Last Class of Math

testCase = int(input())

while testCase>0:
    element = int(input())
    i = 2
    a = 0
    b = 0
    check=1
    #Finding the least element that divides our number n completely
    while (i*i<=element):
        if (element%i==0):
            a = element // i
            b = element - a
            check = 0
            break
        i+=1
    # If the element is a prime no then we do the following
    if check==1:
        a = 1
        b = element - 1
    print(a,end=" ")
    print(b)

    testCase-=1

OmkarProblem_CodeForces
OmkarProblem_CodeForces897×127 21.1 KB

This works pretty fine.

Thank you, I hope it helps.

3

That’s for contributing @thevirtualbuddy. Can you explain a bit about how your approach works instead of just giving the code?

4

Hey @JeremyLT
I have updated the previous reply with an explanation about the same. I would continue similar practice for adding explanation from next time.

5

Thanks! That helps a lot!