Question is to find two numbers within 1 to num that multiply to become num

Question

t=int(input())
while t > 0:
    num=int(input())
    lst=[]
    n=0
    for i in range(1,math.floor(math.sqrt(num))+1):
        if num%i==0:
            lst.append(i)
    n=len(lst)
    if n == 1:
        print(1,num)
    else:
        print(lst[1],int(num/lst[1]))
    t-=1

Question is to find two numbers within 1 to num that multiply to become num(for prime it is only 1, num and for rest any 2 factors). The time limit exceeded error is the thing that I am seeing now. Can anyone help me in optimizing it?

Answer 1

You can optimise the code by changing the limit inside the range to sqrt(num).I hope this solves your problem.

You can try like this:

 import math
 t= int(input())
 while(t>0):
     num = int(input())
     lst = []
     for i in range(1,(math.sqrt(num))+1):
          if(num%i == 0):
              lst.append((i,num/i))
              break
     print(lst[0])
     t= t-1

    

Answer 2

• If you just need to find any 2 factors, there is no need to use a list. Just break after the first one found.
• As suggested in the comments, there is no need to iterate until num, as the factors will start to repeat. It is enough to iterate until the square.
• Lastly, you can take advantage of the built-in divmod function to avoid calculating the modulus and then the division.

from math import sqrt

num = int(input())
for n in range(2, int(sqrt(num)) + 1):
    div, mod = divmod(num, n)
    if mod == 0:
        print(n, div)
        break
else:
    print(1, num)

• This uses the for/else construct so in case no factors were found, just 1, num will be printed which is always true.