Problem:


Score : 400 points

Problem Statement

Given is a positive integer N. Consider repeatedly applying the operation below on N:

First, choose a positive integer z satisfying all of the conditions below:

z can be represented as z=p^e, where p is a prime number and e is a positive integer;

z divides N;

z is different from all integers chosen in previous operations.

Then, replace N with N/z.

Find the maximum number of times the operation can be applied.

Constraints

All values in input are integers.

1 \leq N \leq 10^{12}

Input

Input is given from Standard Input in the following format:

N

Output

Print the maximum number of times the operation can be applied.

Sample Input 1

24

Sample Output 1

3

We can apply the operation three times by, for example, making the following choices:

Choose z=2 (=2^1). (Now we have N=12.)

Choose z=3 (=3^1). (Now we have N=4.)

Choose z=4 (=2^2). (Now we have N=1.)

Sample Input 2

1

Sample Output 2

0

We cannot apply the operation at all.

Sample Input 3

64

Sample Output 3

3

We can apply the operation three times by, for example, making the following choices:

Choose z=2 (=2^1). (Now we have N=32.)

Choose z=4 (=2^2). (Now we have N=8.)

Choose z=8 (=2^3). (Now we have N=1.)

Sample Input 4

1000000007

Sample Output 4

1

We can apply the operation once by, for example, making the following choice:

z=1000000007 (=1000000007^1). (Now we have N=1.)

Sample Input 5

997764507000

Sample Output 5

7



Sample input:
24


Sample output:
3

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

def trial_division(n):  # n > 1
    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

def count_primes(n):
    a = trial_division(n)
    b = [[a[0],1]]
    for i in range(1,len(a)):
        if b[-1][0]==a[i]:
            b[-1][1]+=1
        else:
            b.append([a[i],1])
    return b


n = readint()
if n==1:
    print(0)
    exit()

a = count_primes(n)
ans = 0
for i in range(len(a)):
    x,y = a[i]
    b = 1
    while y>0:
        y-=b
        if y>=0:
            ans += 1
            b+=1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())

def primeFactorization(n):
    res = defaultdict(int)
    m = int(n**0.5)
    for i in range(2,m+1):
        while n % i == 0:
            n = n//i
            res[i] += 1
    if n > 1:
        res[n] = 1
    return res

dic = primeFactorization(N)

ans = 0
for k,v in dic.items():
    n = 1
    while v >= n*(n+1)//2:
        ans += 1
        n += 1

print(ans)

Submission status: Accepted

Solution code:
import bisect as bi
def fact(n):
  arr=[]
  temp=n
  for i in range(2,int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0:
        cnt+=1
        temp//=i
      arr.append([i,cnt])
  if temp!=1:
    arr.append([temp,1])
  if arr==[]:
    arr.append([n,1])
  return arr
n=int(input())
if n==1:
  print(0)
  exit()
l=[i*(i+1)//2 for i in range(1,100)]
c=0
for t in fact(n):
  c+=bi.bisect_right(l,t[1])
print(c)

Submission status: Accepted

Solution code:
from collections import *


def factors(n):
    div = 2
    l = []
    while div * div <= n:
        if n % div == 0:
            l.append(div)
            n //= div
        else:
            div += 1
    if n != 1:
        l.append(n)
    return Counter(l)


l = factors(int(input()))
z = 0
for k, v in l.items():
    i = 1
    while v >= i:
        z += 1
        v -= i
        i += 1
print(z)

Submission status: Accepted

Solution code:
# 素因数分解 - 試し割り法
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

n = int(input())

ans = 0

for num, cnt in factorization(n):
    if num != 1:
        tmp = 1
        while True:
            cnt -= tmp
            if cnt >= 0:
                ans += 1
                tmp += 1
            else:
                break

print(ans)

Submission status: Accepted

Solution code:
import bisect
n = int(input())

def Prime(m):
    res = {}
    x = m
    i = 2
    while i*i <= m:
        if x%i == 0:
            res[i] = 0
            while x%i == 0:
                x //= i
                res[i] += 1
        i += 1
    if x > 1:
        if x not in res:res[x] = 0
        res[x] += 1
    return res
array = [0]*1000
for i in range(1000):
    array[i] = i*(i+1)//2
ans = 0
for v in Prime(n).values():
    ans += bisect.bisect_right(array,v) - 1
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

if N == 1:
	print(0)
	exit()

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

ans = 0
for x, n in factorization(N):
	tmp = int((2*n)**0.5)
	if tmp*(tmp+1) > 2*n:
		tmp -= 1
	ans += tmp
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


def main():
    n=int(input())
    i = 2
    m = {}
    while i*i <= n:
        while n % i == 0:
            m[i] = m.get(i, 0) + 1
            n //= i
        i += 1
    if n != 1:
        m[n] = m.get(i, 0) + 1
    s = 0
    for v in m.values():
        i = 1
        while i <= v:
            s += 1
            v -= i
            i += 1
    print(s)

main()

Submission status: Accepted

Solution code:
def fac(n):
    dic = {}
    cur = n
    for i in range(2,(int(n**0.5)+2)):
        if cur % i == 0:
            count = 0
            while cur % i == 0:
                count += 1
                cur //= i
            dic[i] = count
            if cur == 1:
                break
    if cur != 1:
        dic[cur] = 1
    return dic

n = int(input())
ans = 0
for i in fac(n).values():
    count = 1
    while i >= count:
        i -= count
        count += 1
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np


def factorize(N):
    up = int(np.sqrt(N))+2
    out = {}

    for i in range(2,up):
        if N%i == 0:
            temp = N
            count = 0
            while(True):
                N = N//i
                count += 1
                if N%i != 0:
                    break
            out[i] = count
        else:
            continue
    if N != 1:
        out[N] = 1
    return out

n = int(input())
f = factorize(n)
# print(f)

ans = 0
base = 1
for key in f.keys():
    while f[key] >= base:
        ans += 1
        f[key]-= base
        base += 1
    base = 1
print(ans)

Submission status: Accepted

Solution code:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr



n=int(input())
if n==1:
    print(0)
    exit()
f = factorization(n)
ans=0
for g,m in f:
    for i in range(10000):
        if i*(i+1)//2>m:
            ans+=i-1
            break
print(ans)

Submission status: Accepted

Solution code:
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

N = int(input())
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i ==0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr

if N == 1:
    print(0)
else:
    ans = 0
    l = factorization(N)
    for i in range(len(l)):
        now = l[i][1]
        c = 1
        while now-c >= 0:
            now -= c
            ans += 1
            c += 1
    print(ans)

Submission status: Accepted

Solution code:

N = int(input())

dic = {}

for i in range(2,10**6+10):

    if N == 1:
        break
    while N % i == 0:

        if i not in dic:
            dic[i] = 1
        else:
            dic[i] += 1
        N //= i

if N != 1:
    if N not in dic:
        dic[N] = 1
    else:
        dic[N] += 1

ans = 0

for i in dic:

    l = 1
    r = 10**12

    while r-l != 1:

        m = (l+r)//2

        now = (1+m)*m//2

        if now <= dic[i]:
            l = m
        else:
            r = m

    ans += l

print (ans)

Submission status: Accepted

Solution code:
n = int(input())

def factorization(n):
    arr = []
    tmp = n
    for i in range(2, int(n**0.5)+1):
        if tmp % i == 0:
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            arr.append([i, cnt])

    if tmp != 1:
        arr.append([tmp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr

if n == 1:
    print(0)
    exit()

arr = factorization(n)
#print(arr)

ans = 0
for x, cnt in arr:
    for i in range(100):
        if i * (i - 1) // 2 <= cnt < i * (i + 1) // 2:
            ans += i - 1
            break

print(ans)

Submission status: Accepted

Solution code:
import sys

import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline

def prime_factorization(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors


def main():
    N = int(input())

    x = prime_factorization(N)

    c = collections.Counter(x)

    ans = 0
    for k in c.keys() :
        for i in range(1, 10 ** 5):
            if c[k] >= i:
                c[k] -= i
                ans += 1


    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

def factoring(M,n=2):
    if M==1: return {}
    for i in range(n,int(M**0.5)+1):
        if M%i==0:
            ret = factoring(M//i,i)
            ret[i] = ret.get(i,0)+1
            return ret
    return {M:1}

F = factoring(N)

ans = 0
for n in F.values():
    tmp = 1
    while n >= tmp:
        n -= tmp
        ans += 1
        tmp += 1

print(ans)

Submission status: Accepted

Solution code:
def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return None
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
if __name__ == "__main__":
    N = int(input())
    A = factorization(N)
    cnt = 0
    if A:
        for a in A:
            b = a[1]
            c = 1
            d = 0
            while(c <= b):
                d += 1
                c += d+1
            cnt += d
    print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict


def factorize(n: int) -> dict:
    f = defaultdict(int)
    while n % 2 == 0:
        f[2] += 1
        n //= 2
    p = 3
    while p * p <= n:
        while n % p == 0:
            f[p] += 1
            n //= p
        p += 2
    if n != 1:
        f[n] += 1
    return f


n = int(input())
if n > 1:
    f = factorize(n)

    MAX = max(f.values())
    b = [0]
    while len(b) < MAX + 10:
        b.extend([b[-1] + 1] * (b[-1] + 2))

    # print(b)
    # print(f)
    ans = 0
    for v in f.values():
        ans += b[v]
else:
    ans = 0

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
D=dict()
p=2
M=N
while(p*p<=N):
    if M%p==0:
        if p in D:
            D[p]+=1
        else:
            D[p]=1
        M=M//p
    else:
        p+=1
if M>1:
    D[M]=1
#print(D)
def block(K):
    t=1
    tmp=K
    res=0
    while(1):
        if tmp>=t:
            tmp-=t
            t+=1
            res+=1
        else:
            tmp=0
            break
    return res
ans=0
for p in D:
    ans+=block(D[p])
print(ans)

Submission status: Accepted

Solution code:
def prime_factorize(num): # 整数に対し素因数分解
    prime_factor = {}
    i = 2
    while i ** 2 <= num:
        while num % i == 0:
            num //= i
            if i in prime_factor.keys():
                prime_factor[i] += 1
            else:
                prime_factor[i] = 1
        i += 1
    if num > 1:
        prime_factor[num] = 1
    return prime_factor

n = int(input())
data = prime_factorize(n)
ans = 0
for i in data:
    x = data[i]
    j = 1
    while j <= x:
        x -= j
        j += 1
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def is_p(n):
        if n < 4:
            return 1
        i = 2
        while i*i <= n:
            if n%i == 0:
                return 0
            i += 1
        return 1

    def f(n):
        res = set([n])
        i = 2
        while i*i <= n:
            if n%i == 0:
                m = n//i
                res.add(i)
                res.add(m)
            i += 1
        res = list(res)
        res.sort()
        return res

    n = I()
    if n == 1:
        print(0)
        return
    if is_p(n):
        print(1)
        return
    f = f(n)
    m = len(f)
    k = [0]*m
    for i in range(m):
        fi = f[i]
        if is_p(fi):
            for j in range(i+1,m):
                if f[j]%fi == 0:
                    k[j] += 1
    lis = deque([f[i] for i in range(m) if k[i] <= 1])
    ans = 0
    while lis:
        x = lis.popleft()
        if n%x == 0:
            n //= x
            ans += 1
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import defaultdict
import math
N = int(input())
ps = defaultdict(int)
for i in range(2, int(math.sqrt(N))+1):
    while N % i == 0:  
        ps[i] += 1
        N //= i
    i += 1
if N > 1:
    ps[N] += 1
ans = 0
for p in ps:
    k = 1
    while ps[p] >= k:
        ans += 1
        ps[p] -= k
        k += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())

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

a = prime_factorize(N)
num = list(Counter(a).values())

ans = 0
for i in num:
    j = 1
    while i - j >= 0:
        ans += 1
        i -= j
        j += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
input = sys.stdin.readline
N = int(input())
x = 2
ps = Counter()
while x * x <= N:
  while N % x == 0:
    ps[x] += 1
    N //= x
  x += 1
if N > 1: ps[N] += 1
#print(ps)
res = 0
for k in ps.keys():
  ok = 0
  ng = pow(10, 12)
  while ng - ok > 1:
    m = (ok + ng) // 2
    if m * (m + 1) // 2 <= ps[k]: ok = m
    else: ng = m
  res += ok
print(res)

Submission status: Accepted

Solution code:
N=int(input())
def prime_factorization(n):
    p={}
    for i in range(2,int(n**.5)+1):
        x=0
        while n%i==0:
            n//=i
            x+=1
        if x:
            p[i]=x
    if n>1:
        p[n]=1
    return p
p=prime_factorization(N)
x=0
for v in p.values():
    y=0
    while y<v:
        x+=1
        y+=1
        v-=y
print(x)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import math

# 素因数分解、辞書で返すやつ
# mathをimportする
def prime(n):
    factor = {}
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            if not num in factor.keys():
                factor[num] = 1
            else:
                factor[num] += 1
        if num > n:
            break
    if n != 1:
        if not n in factor.keys():
            factor[n] = 1
        else:
            factor[n] += 1
    return factor

N = int(input())
fac = prime(N)
ans = 0
for v in fac.values():
    tmp = 0
    for i in range(1, 10**9):
        if tmp + i <= v:
            tmp += i
            ans += 1
        else:
            break
print(ans)

Submission status: Accepted

Solution code:
def factorization(n):
    from collections import Counter
    arr = Counter()
    temp = n
    for i in range(2, int(-(-n**0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr[i] = cnt

    if temp != 1:
        arr[temp] = 1

    if len(arr.keys()) == 0 and n != 1:
        arr[n] = 1

    return arr


N = int(input())

primes = factorization(N)

cnt = 0
for p, n in primes.items():
    k = 1
    while n >= k:
        cnt += 1
        n -= k
        k += 1
print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import time
import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    

    class Eratos:
        def __init__(self, num):
            '''
            O(nlglgn) で num までの素数判定テーブルを作る
            >>> e = Eratos(10)
            >>> e.table
            [False, False, True, True, False, True, False, True, False, False, False]
            '''
            assert(num >= 1)
            self.table_max = num
            # self.table[i] は i が素数かどうかを示す (bool)
            self.table = [False if i == 0 or i == 1 else True for i in range(num+1)]
            for i in range(2, int(math.sqrt(num)) + 1):
                if self.table[i]:
                    for j in range(i ** 2, num + 1, i):    # i**2 からスタートすることで定数倍高速化できる
                        self.table[j] = False
        
        def is_prime(self, num):
            '''
            O(1) で素数判定を行う
            >>> e = Eratos(100)
            >>> [i for i in range(1, 101) if e.is_prime(i)]
            [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
            '''
            assert(num >= 1)
            if num > self.table_max:
                raise ValueError('Eratos.is_prime(): exceed table_max({}). got {}'.format(self.table_max, num))
            return self.table[num]
        
        def prime_factorize(self, num):
            '''
            O(√n) で素因数分解を行う
            >>> e = Eratos(10000)
            >>> e.prime_factorize(6552)
            {2: 3, 3: 2, 7: 1, 13: 1}
            '''
            assert(num >= 1)
            if int(math.sqrt(num)) > self.table_max:
                raise ValueError('Eratos.prime_factorize(): exceed prime table size. got {}'.format(num))
            # 素因数分解の結果を記録する辞書        
            factorized_dict = dict()
            candidate_prime_numbers = [i for i in range(2, int(math.sqrt(num)) + 1) if self.is_prime(i)]
            # n について、√n 以下の素数で割り続けると最後には 1 or 素数となる
            # 背理法を考えれば自明 (残された数が √n より上の素数の積であると仮定。これは自明に n を超えるため矛盾)
            for p in candidate_prime_numbers:
                if num == 1:    # これ以上調査は無意味
                    break
                if num % p == 0:
                    cnt = 0
                    while num % p == 0:
                        num //= p
                        cnt += 1
                    factorized_dict[p] = cnt
            if num != 1:
                factorized_dict[num] = 1
            return factorized_dict
        
        def enum_divisor(self, num):
            '''
            O(√n) で約数列挙を行う
            >>> e = Eratos(10000)
            >>> e.enum_divisor(4)
            [1, 2, 4]
            >>> e.enum_divisor(19)
            [1, 19]
            >>> e.enum_divisor(100)
            [1, 2, 4, 5, 10, 20, 25, 50, 100]
            '''
            divisor_small = []
            divisor_large = []
            for i in range(1, int(math.sqrt(num)) + 1):
                if num % i == 0:
                    divisor_small.append(i)
                    if i != num // i:
                        divisor_large.append(num // i)
            divisor_large.reverse()
            return divisor_small + divisor_large
    

    def calc(num):
        # x * (x+1) <= 2 * num なる最大の x を返す
        left = 0
        right = 50
        while right - left > 1:
            # print(f"{right} {left}")
            mid = (right + left) // 2
            if mid * (mid + 1) > 2 * num:
                right = mid
            else:
                left = mid
        return left

    n = ii()
    e = Eratos(10**6+2)
    # print(e)
    d = e.prime_factorize(n)
    ans = 0
    for v in d.values():
        ans += calc(v)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def f(n):
  res = 0
  s = 0
  for i in range(1, n + 1):
    s += i
    if s <= n:
      res = i
    else:
      break
  return res
n = int(input())
p = 2
ans = 0
while p * p <= n:
  e = 0
  while n % p == 0:
    e += 1
    n //= p
  ans += f(e)
  p += 1
if n > 1:
  ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

"""nを素因数分解"""
"""2以上の整数n => [(素因数, 指数), ...]の2次元リスト"""

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(n**0.5)+1):
        if temp%i == 0:
            cnt = 0
            while temp%i == 0:
                cnt += 1
                temp //= i
            arr.append((i, cnt))
    if temp != 1:
        arr.append((temp, 1))
    if arr == []:
        arr.append((n, 1))
    return arr

li = factorization(N)
ans = 0
for i in li:
    k = i[1]
    loop = 1
    while True:
        k -= loop
        if k>=0:
            ans += 1
        else:
            break
        loop += 1
if N==1:
    print(0)
else:
    print(ans)

Submission status: Accepted

Solution code:
def factorize(n):#素因数分解
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append([b, e])
        b, e = b + 1, 0
    if n > 1:
        fct.append([n, 1])
    return fct

n = int(input())

l = factorize(n)

m = len(l)

ans = 0

for i in range(m):
    x = l[i][1]
    for j in range(1, 50):
        if x >= j:
            ans += 1
            x -= j
        else:
            break

print(ans)

Submission status: Accepted

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

N = int(input())

def prime_decomposition(n):
    i = 2
    table = defaultdict(int)
    while i*i <= n:
        while n%i == 0:
            n //= i
            table[i] += 1
        i += 1
    if n > 1:
        table[n] += 1
    return table

table = prime_decomposition(N)

cnt = 0
for key, val in table.items():
    mnum = 1
    while val-mnum >= 0:
        val -= mnum
        mnum += 1
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
from collections import Counter


def primeFactors(n):
    # Returns a counter of prime factors of n
    # e.g., 12 returns {2: 2, 3: 1}
    assert n >= 1
    factors = Counter()
    while n % 2 == 0:
        factors[2] += 1
        n //= 2
    x = 3
    while x * x <= n:
        while n % x == 0:
            factors[x] += 1
            n //= x
        x += 2
    if n != 1:
        factors[n] += 1
    return factors


(N,) = [int(x) for x in input().split()]
ans = 0
for p, count in primeFactors(N).items():
    for i in range(1, count + 1):
        if count - i >= 0:
            ans += 1
            count -= i
        else:
            break
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
def main():
    N = int( input())
    d = defaultdict( int)
    for i in range(2, int(N**(1/2))+1):
        while N%i == 0:
            d[i] += 1
            N //= i
    if N > 1:
        d[N] += 1
    ans = 0
    for key in d:
        for i in range(1, 100):
            if i*(i+1)//2 > d[key]:
                ans += i-1
                break
    print(ans)
if __name__ == '__main__':
    main()