"Divide by $ p ^ 1, p ^ 2, p ^ 3, \ ldots $ and record the number of cracks, Stop recording the number of times and divide as much as you can divide by $ p $ " Is repeated with $ p = 2, 3, 5, 7, 9, \ ldots, \ sqrt {N} $. Add 1 if there are still prime numbers left. Like.
N = int(input())
n, p, score = N, 2, 0
while p ** 2 <= N:
e = 1
while n % (p ** e) == 0:
n //= (p ** e)
score += 1
e += 1
else:
while n % p == 0:
n //= p
p = p + 1 if p == 2 else p + 2
else:
if n != 1:
score += 1
print(score)
A little shorter
N = int(input())
n, p, score = N, 2, 0
while p ** 2 <= N:
e = 1
while n % (p ** e) == 0:
n //= (p ** e)
score += 1
e += 1
else:
while n % p == 0:
n //= p
p += 2 - (p == 2)
else:
score += n > 1
print(score)
Recommended Posts