AtCoder Beginner Contest 169 [ D - Div Game ] https://atcoder.jp/contests/abc169/tasks/abc169_d

abc169_d.py

'''
[問題]
https://atcoder.jp/contests/abc169/tasks/abc169_d

[解説]
https://blog.hamayanhamayan.com/entry/2020/06/01/210704
　素因数分解は計算量 O(sqrt(N))　
　制約条件N=10^12なので計算量は10^6
　計算量から素因数分解をメタ読みできる。
　
https://img.atcoder.jp/abc169/editorial.pdf

https://youtu.be/-fTsuyin-a8?t=5166


[参考]
Pythonで素因数分解（試し割り法）
https://note.nkmk.me/python-prime-factorization/

https://atcoder.jp/contests/abc169/submissions/24180077
　ansの回し方が参考になる

[結果]
PyPy3(7.3.0) AC 71ms
Python(3.8.2) AC 95ms
'''

import sys
import collections

sys.setrecursionlimit(10 ** 6)  # 再帰上限の引き上げ
input = sys.stdin.readline

INF = 2 ** 63 - 1

# 素因数分解
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


N = int(input())
p = prime_factorize(N)

if len(p) == 0:
    print(0)
    exit()

# 素因数分解の結果、素数がどれが何回でてきたかという形式に変換する
c = collections.Counter(p)

# 素因数分解の結果が割り算の結果そのものなので、ここから答えをカウントしていく
ans = 0
# f:素因数, i:指数
for f, i in c.items():
    # 確実に1回は割れる
    j = 1
    # 存在するfが割る数jより多い間はループを回す
    while i >= j:
        ans += 1
        # i個あるfがj個なくなる
        i -= j
        j += 1

print(ans)