质因数分解
质因数分解的模板题
具体实现看代码注释
n, i, ans = int(input()), 2, 0 # n 枚举的质数 答案
while i ** 2 <= n: # 约数一定 <= √n
if n % i == 0: # 发现一个约数
ans += 1 # 更新答案
while n % i == 0: # 把该质因数分解出来
n //= i
i += 1
print(ans if n == 1 else ans + 1) # 循环结束后的值不为 1 的话,说明这个值也是 n 的质因数
复杂度分析
- 时间复杂度:$O(√n)$
- 空间复杂度:$O(1)$
强
太强了