python - 问题是找到 1 到 num 内的两个数字相乘成为 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

问题是在乘法中找到两个数字1 to num成为num（素数只有 1，num 和其余任何 2 个因数）。我现在看到的是超出时间限制的错误。谁能帮我优化它？

Answer 1

您可以通过将范围内的限制更改为 sqrt(num) 来优化代码。我希望这可以解决您的问题。

你可以这样尝试：

 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

• 如果您只需要找到任何 2 个因素，则无需使用列表。刚break找到第一个。
• 正如评论中所建议的，没有必要迭代 until num，因为这些因素将开始重复。迭代到正方形就足够了。
• 最后，您可以利用内置divmod函数来避免计算模数和除法。

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)

• 这使用了for/else构造，所以如果没有找到任何因素，只会1, num打印出来，这总是正确的。