摘要
Title: 869. 试除法求约数
Tag: 约数
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

869. 试除法求约数

• 题意

  给定 n 个正整数 ai，对于每个整数 ai，请你按照从小到大的顺序输出它的所有约数。

• 思路

  复杂度$O(sqrt(n))$

  求约数和求质因子有什么区别
  约数：

  • i从1开始
  • n不用每次整除i
    质因子
  • i从2开始
  • n每次需要一次或多次整除i （因为需要排除这个因子

• 代码

  for _ in range(int(input())):
      n = int(input())
      ans = []
      i = 1
      while i <= n // i:
          if n % i == 0:
              ans.append(i)
              if i != n // i:
                  ans.append(n // i)
          i += 1
      ans.sort()
      for i in ans: print(i, end = " ")
      print()