# Minimum LCM in python

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),end=" ")
print(min(c))
``````

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

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

``````

This works pretty fine.

Thank you, I hope it helps.

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

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.

Thanks! That helps a lot!