摘要
Title: 867. 分解质因数
Tag: 质数
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

867. 分解质因数

• 题意

  给定 n 个正整数 ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。

• 思路

  复杂度$O(sqrt(n))$
  n中最多只包含一个大于$sqrt(n)$的质因子 （要不然两个乘起来就比n大了）

  所以：

  • 先枚举小于等于$sqrt(n)$的因子
  • 在最后看有没有大于$sqrt(n)$的质因子

• 代码

  for i in range(int(input())):
      n = int(input())
      i = 2
      while i <= n // i:
          if n % i == 0:
              s = 0
              while n % i == 0:
                  s += 1
                  n //= i
              print(i, s)
          i += 1
      if n > 1:
          print(n, 1)
      print()