2022年十三届----试题C：质因数个数（中）

• 题目
• 暴力
• 题解

题目

暴力

• 先暴力把到n的质数存在一个列表里面，如何遍历列表，如果n可以整除该质数就count++,最后返回count

m=[]
count=0
n=int(input())
for i in range(1,n):
    if i>1:
        for j in range(2,int(i**0.5)+1):
            if i%j==0:
                break
        else:
            m.append(i)
for i in  m:
    if n%i==0:
        count+=1

print(count)

• 只能通过30%的测试

题解

• 处理了n很大的情况，判断素数也做了一定优化

n = int(input()) #获取输入
a = [2, 3] #初始化列表用来保存质数
ans = 0 #初始化ans，用来存质因数个数

for i in a: #遍历列表 a，该列表包含 [2, 3]
    if n % i == 0:  #判断 n 是否能被 2 或 3 整除
        ans += 1
        while n % i == 0:#通过循环除以对应的素数，降低 n 的值
            n //= i
for i in range(5, int(n ** 0.5) + 1, 6):#使用从 5 开始，步长为 6 的循环
#除了 2 和 3，所有的质数都可以写成 6k ± 1 的形式。所以我们只需要检查它是否能被 i 和 i + 2 整除，就可以判断它是否为质数。
    b = [i, i + 2]#包含当前循环的素数 i 和 i+2
    for j in b:
        if n % j == 0:#如果能整除
            ans += 1 #将计数器 ans 增加
            while n % j == 0: #循环除以对应的素数
                n //= j #降低 n 的值。
if n > 1:#如果 n 的值大于 1，说明 n 本身就是一个素数
    ans += 1
print(ans)