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 collections

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())
c = collections.Counter(prime_factorize(n))
l = c.values()
ans=0
for i in list(l):
    temp = i
    j=1
    while temp > 0:
        if temp < j:
            break
        temp -= j
        j += 1
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def prime_factorise(n):
    a=[]
    while n%2==0:
        n//=2
        a.append(2)
    f=3
    while f*f<=n:
        if n%f==0:
            n//=f
            a.append(f)
        else:
            f+=2
    if n!=1:
        a.append(n)
    return a

n=int(input())
factors = Counter(prime_factorise(n))
ans=0
for i in factors.values():
    temp=1
    while i-temp>=0:
        i-=temp
        temp+=1
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from math import sqrt
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())
fac = factorization(n)
s = 0
for i in fac:
    if i[0] != 1:
        s += (-1+sqrt(1+4*i[1]*2))//2
print(int(s))

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(j) for j in input().split()]
#template
N = int(input())
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

li = factorization(N)
n = len(li)
ans = 0
counts = [1]*40
for i in range(2,41):
    counts[i-1] = counts[i-2]+i
from bisect import bisect_right
for i in range(n):
    count = li[i][1]
    ans += bisect_right(counts,count)
print(ans)

Submission status: Accepted

Solution code:
# 素因数分解
# O(N**0.5)
def p_bunkai(N):
    ret = []
    for i in range(2, int(N ** 0.5) + 1):
        if N % i == 0:
            count = 0
            while N % i == 0:
                N //= i
                count += 1
            ret.append((i, count))
    if N != 1:
        ret.append((N, 1))
    return ret

N = int(input())

ans = 0
for _, i in p_bunkai(N):
    j = 1
    while True:
        if i >= j:
            ans += 1
            i -= j
            j += 1
        else:
            break
print(ans)

Submission status: Accepted

Solution code:
# import sys
# import math #sqrt,gcd,pi
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# from itertools import product,permutations,\
#     combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
# mod = 998244353
INF = 1<<29
lINF = 1<<35

def readInt():
    return list(map(int,input().split()))

def prime_fact(a): # 素因数分解
    fact = {}
    prime = set()
    for i in range(2,int(a**(1/2)+1)):
        if a%i==0:
            fact[i] = 0
            while a%i==0:
                a //= i
                fact[i] += 1
    if a!=1:
        fact[a] = 1
    return fact

def main():
    n = int(input())
    if n==1:
        print(0)
        return
    fact = prime_fact(n)
    ans = 0
    for x in fact.keys():
        i = 1
        while i<=fact[x]:
            fact[x] -= i
            i += 1
            ans += 1
    print(ans)
    return

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
import math
from collections import deque 
from functools import reduce
import collections

# input = sys.stdin.readline

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
prime_list = prime_factorize(n) 
c = collections.Counter(prime_list)
total = 0
for prime, cnt in c.items():
    i = 1
    while True:
        if cnt - i >= 0:
            total += 1
            cnt -= i
            i += 1
        else :
            break
print(total)

Submission status: Accepted

Solution code:
import collections
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

c = collections.Counter(prime_factorize(n))
ans = 0
for v in c.values():
    prev = 1
    while v >= prev:
        v -= prev
        prev += 1
        ans += 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)
c = Counter(a)
ans = 0
for i in c.values():
    j = 1
    while i >= j:
        i -= j
        j += 1
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import os
import sys
from atexit import register
from io import BytesIO
sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))
input = lambda: sys.stdin.readline().rstrip('\r\n')
raw_input = lambda: sys.stdin.readline().rstrip('\r\n')


n = int(input())
ans = 0
p = 2
while n > 1:
    cnt = 0
    cntcnt = 1
    while n % p == 0 and n > 0:
        n  = n // p
        cnt += 1
        if cnt == cntcnt:
            ans += 1
            cnt = 0
            cntcnt += 1
    if n <= 1:
        break
    # next prime
    if p == 2:
        p = 3
    else:
        p += 2
        
        is_prime = False
        while not is_prime:
            if n % p != 0:
                p += 2
                if p*p > n:
                    p = n
                    break
                continue
            i = 5
            is_prime = True
            while (i * i <= p):
                if (p % i == 0) or (p % (i+2) == 0):
                    is_prime = False
                    break
                i += 6
            if not is_prime:
                p += 2
                

    
print(ans)

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

def factorize(num: int) -> dict:
    """ 素因数分解 """
    from math import sqrt
    from collections import Counter

    d = Counter()
    for i in range(2, int(sqrt(num))+1):
        while num % i == 0:
            num //= i
            d[i] += 1
        if num == 1:
            break
    if num != 1:
        d[num] += 1
    return d

N = INT()

fact = factorize(N)
used = set()
for k in fact.keys():
    cnt = 1
    while fact[k] >= cnt:
        if (k, cnt) not in used:
            used.add((k, cnt))
            fact[k] -= cnt
        cnt += 1
ans = len(used)
print(ans)

Submission status: Accepted

Solution code:
import math
n = int(raw_input())
ans = 0

for i in range(2, int(math.sqrt(n) + 1)):
	if n % i == 0:
		p = i
		cnt = 0
		while n % i == 0:
			n /= i
			cnt += 1
		start = 1
		while start <= cnt:
			ans += 1
			cnt -= start
			start += 1
if n > 1:
	ans += 1
print ans

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())

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

factor = prime_factor(n)
c = Counter(factor)

cnt = 0
for k, v in c.items():
    num, idx = 1, 1
    while num <= v:
        cnt += 1
        idx += 1
        num += idx

print(cnt)

Submission status: Accepted

Solution code:
def p_facto(n):
    ret = []
    nc = n
    for i in range(2, nc):
        if i*i > nc:
            break
        if n % i == 0:
            ex = 0
            while n % i == 0:
                ex += 1
                n //= i
            ret.append([i, ex])
    if n != 1:
        ret.append([n, 1])
    return ret


def main(N):
    ans = 0
    for p, e in pf:
        ex = 1
        while True:
            z = p**ex
            if N % z == 0:
                ans += 1
                N //= z
            else:
                break
            ex += 1
    print(ans)


if __name__ == "__main__":
    N = int(input())
    pf = p_facto(N)
    main(N)

Submission status: Accepted

Solution code:
from itertools import accumulate


def main():
    n = int(input())
    acc = tuple(accumulate(range(1, 42)))  # 10^12 < 2^39

    def count_add(c):
        for accum_index, x in enumerate(acc):
            if c < x:
                return accum_index

    f = 2
    count = 0
    ans = 0
    while n % f == 0:
        n //= f
        count += 1
    ans += count_add(count)

    f = 3
    count = 0
    while 1:
        if n % f == 0:
            n //= f
            count += 1
            continue

        ans += count_add(count)
        f += 2
        count = 0
        if f * f > n:
            break
    if n != 1:
        ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
from collections import Counter
def solve():
    N = int(input())
    primeFac = prime_factorize(N)
    counter = Counter(primeFac)
    divisors = []
    for key, val in counter.items():
        for i in range(1,val+1):
            divisors.append(pow(key,i))

    divisors.sort()
    now = N
    ans = 0
    for d in divisors:
        if now % d == 0:
            ans += 1
            now //= d
    
    print(ans)

def prime_factorize(n):
    prime_numbers = []
    for p in range(2, int(math.sqrt(n)+1)):
        if n % p != 0:
            continue
        while n % p == 0:
            n /= p
            prime_numbers.append(p)

    if n != 1:
        prime_numbers.append(n)
    return prime_numbers
    
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n = int(input())
li = []
flg = 0
for i in range(1000000):
  if n==1:
    break
  if i==0 or i==1 or n%i!=0:
    continue
  j = i
  cnt = 0
  while(n%j==0):
    if flg==0:
      flg = 1
    n /= j
    cnt += 1
  li.append(cnt)
if flg==0 and n!=1:
  print(1)
elif flg==0 and n==1:
  print(0)
elif n==1:
  ans = 0
  for e in li:
    i = 1
    while(e-i>=0):
      e -= i
      i += 1
      ans += 1
  print(ans)
else:
  ans = 1
  for e in li:
    i = 1
    while(e-i>=0):
      e -= i
      i += 1
      ans += 1
  print(ans)

Submission status: Accepted

Solution code:
import sys
n=int(input())
if n ==1:
    print("0")
    sys.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

l = factorization(n)
count =0
for i in l:
    cou = 0
    a = i[1]
    hiku = 1
    while a - hiku >=0:
        cou += 1
        a -= hiku
        hiku += 1
    count += cou
print(count)

Submission status: Accepted

Solution code:
import math
def get_prime(n):
    if n <= 1:
        return []
    prime = [2]
    if n > 2:
        limit = int(math.sqrt(n))
        odd = [i for i in range(3, n + 1, 2)]
        while limit >= odd[0]:
            prime.append(odd[0])
            odd = [j for j in odd if j % odd[0] != 0]
        prime += odd
    return prime

from collections import defaultdict
def prime_factorization(n):
    if n <= 1:
        return {}
    else:
        # print(int(math.sqrt(n)))
        prime = get_prime(int(math.sqrt(n)))
        dct = defaultdict(int)
        for p in prime:
            while n % p == 0:
                dct[p] += 1
                n //= p
        if n != 1:
            dct[n] += 1
        dct = dict(dct)
        return dct

n = int(input())
pf = prime_factorization(n)

Z = []
for k, v in pf.items():
    for i in range(1, v + 1):
        Z.append(k ** i)
Z.sort()
count = 0
for z in Z:
    if n % z == 0:
        count += 1
        n //= z


print(count)

Submission status: Accepted

Solution code:
n = int(input())
cnt = 0

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

a = factorization(n)
c = 0
for i in a:
	k = 1
	x = i[1]
	while x-k >= 0:
		x -= k
		c += 1
		k += 1
if n == 1:
	print (0)
else:
	print (c)

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()

ans = 0

fact = factorization(n)

for p, e in fact:
    f = e
    j = 1
    while f >= 0:
        f -= j
        j += 1
    ans += j - 2
    
print(ans)

Submission status: Accepted

Solution code:
import collections

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())

ans = 0

c = collections.Counter(prime_factorize(n))

for key in c.keys():
    for i in range(1, c[key] + 1):
        if n % (key ** i) == 0:
            n //= (key ** i)
            ans += 1


print(ans)

Submission status: Accepted

Solution code:
import math
def get_prime(n):
    if n <= 1:
        return []
    prime = [2]
    if n > 2:
        limit = int(math.sqrt(n))
        odd = [i for i in range(3, n + 1, 2)]
        while limit >= odd[0]:
            prime.append(odd[0])
            odd = [j for j in odd if j % odd[0] != 0]
        prime += odd
    return prime

from collections import defaultdict
def prime_factorization(n):
    if n <= 1:
        return {}
    else:
        # print(int(math.sqrt(n)))
        prime = get_prime(int(math.sqrt(n)))
        dct = defaultdict(int)
        for p in prime:
            while n % p == 0:
                dct[p] += 1
                n //= p
        if n != 1:
            dct[n] += 1
        dct = dict(dct)
        return dct

n = int(input())
pf = prime_factorization(n)

Z = []
for k, v in pf.items():
    for i in range(1, v + 1):
        Z.append(k ** i)
Z.sort()
count = 0
for z in Z:
    if n % z == 0:
        count += 1
        n //= z
    if n == 1:
        break

print(count)

Submission status: Accepted

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

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

def main():
    N = int(readline())
    fct = factorize(N)
    res = 0
    for a, b in fct:
        p = 1
        while b - p >= 0:
            b -= p
            res += 1
            p += 1

    print(res)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

N = int(input())

p = 2
counter = 0
while N != 1:
 if p > math.sqrt(N):
  counter += 1
  break
 ind = 0
 n = -1
 while N % p == 0:
  N //= p
  ind += 1
 if ind == 0:
  p += 1
  continue
 while (n+1)*(n+2)//2 <= ind:
  n += 1
 counter += n
 p += 1

print(counter)

Submission status: Accepted

Solution code:
def CountTimesforT(N, T):
    t = T
    count = 0
    while N % t == 0:
        count += 1
        N //= t
        t *= T
    while N % T == 0:
        N //= T
    return [count, N]

N = int(input())
M = int(pow(N, 0.5)) + 2
ans = 0
if N != 1:
    for i in range(2, M):
        if N % i == 0:
            l = CountTimesforT(N, i)
            N = l[1]
            ans += l[0]
    if N != 1:
        ans += 1
print(ans)

Submission status: Accepted

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

#import collections
#from bisect import *
from heapq import *

def linput(_t=int):
	return list(map(_t, input().split()))

def gcd(n,m):
    while m: n,m = m, n%m
    return n

def lcm(n,m): return n*m//gcd(n,m)

def prime_factorize(n):
	r = []
	rapp = r.append
	while n%2<1: rapp(2); n//=2
	f = 3
	while f*f<=n:
		if n%f<1: rapp(f); n//=f
		else: f+=2
	if n != 1: rapp(n)
	return r

def main():
	N = int(input())
	#N,P,C,M = linput()

	res = 0
	vQ = prime_factorize(N)
	vQ.sort(reverse=True)
	
	sV = set([])
	t = 1
	pp = 1
	for p in vQ:
		if t != 1 and p != pp:
			t = 1
		t *= p
		if t not in sV:
			N //= t
			sV |= {t}
			res += 1
			t = 1
		pp = p
		if N==1: break
	
	print(res)
	#print("{:.5f}".format(res/R))


main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline


def prime_factorization(n):
    prime_arr = []
    while n % 2 == 0:
        prime_arr.append(2)
        n //= 2

    f = 3
    while f * f <= n:
        if n % f == 0:
            prime_arr.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        prime_arr.append(n)
    return prime_arr


N = int(input())
c = Counter(prime_factorization(N))
counter = 0

for v in c.values():
    t = 1
    while v - t >= 0:
        counter += 1
        v -= t
        t += 1

print(counter)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline


def prime_factorization(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())
c = Counter(prime_factorization(N))
counter = 0

for v in c.values():
    t = 1
    while v - t >= 0:
        counter += 1
        v -= t
        t += 1

print(counter)

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()
ans=0
t=factorization(n)

fg=[]
for i in range(1,16):
    fg.append(i*(i+1)//2)

tmp=[]
for i in range(len(t)):
    cnt=0
    for j in range(len(fg)):
        if t[i][1]>=fg[j]:
            cnt=(j+1)
    ans+=cnt

print(ans)

Submission status: Accepted

Solution code:
import math

#素因数分解
def prime_factorization(N):

    n = N
    sqrt = int(math.sqrt(n)) + 1
    m = {}
    for i in range(2, sqrt):
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                cnt += 1
                n /= i
            m[i] = cnt

    # nが1になっていなければn自体が素数
    if n != 1:
        m[n] = 1

    return m

n = int(input())
m = prime_factorization(n)
ans = 0

for v in m.values():
    b = 1
    while v - b >= 0:
        ans += 1
        v -= b
        b += 1

print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


class Prime():
    def __init__(self, n):
        self.M = m = int(math.sqrt(n)) + 10
        self.A = a = [True] * m
        a[0] = a[1] = False
        self.T = t = [2]
        for j in range(4, m, 2):
            a[j] = False
        for i in range(3, m, 2):
            if not a[i]:
                continue
            t.append(i)
            for j in range(i*i,m,i):
                a[j] = False
        self.ds_memo = {}
        self.ds_memo[1] = set([1])

    def is_prime(self, n):
        return self.A[n]

    def division(self, n):
        d = collections.defaultdict(int)
        for c in self.T:
            while n % c == 0:
                d[c] += 1
                n //= c
            if n < 2:
                break
        if n > 1:
            d[n] += 1
        return d

    # memo
    def divisions(self, n):
        if n in self.ds_memo:
            return self.ds_memo[n]

        for c in self.T:
            if n % c == 0:
                rs = set([c])
                for cc in self.divisions(n // c):
                    rs.add(cc)
                    rs.add(cc * c)
                self.ds_memo[n] = rs
                return rs

        rs = set([1, n])
        self.ds_memo[n] = rs
        return rs

    def sowa(self, n):
        r = 1
        for k,v in self.division(n):
            t = 1
            for i in range(1,v+1):
                t += math.pow(k, i)
            r *= t
        return r


def main():
    n = I()
    pr = Prime(n)
    d = pr.division(n)
    r = 0
    for c in d.values():
        for i in range(1,1000):
            if c < i:
                break
            r += 1
            c -= i

    return r

print(main())

Submission status: Accepted

Solution code:
# sqrt(n) <= 10**6 ループに耐えうる
# // -> (python 3) 除算の結果をintに
import math
N = int(input())
PrimeFactList = []
tmpNum = N

# 素因数分解
# 2 から順に数字を+1しながら√N + 1まで素因数分解すれば素数以外では素因数分解されない
for i in range(2, int(math.sqrt(N))+1):
    if N % i == 0:
        expcnt = 0
        while tmpNum % i == 0:
            tmpNum //= i
            expcnt += 1
        PrimeFactList.append(i)
        PrimeFactList.append(expcnt)

# 1以外の数が残っていたら足す
if tmpNum != 1:
    PrimeFactList.append(tmpNum)
    PrimeFactList.append(1)

# 素因数が1つもなければN自体を因数に加える
if len(PrimeFactList) == 0:
    PrimeFactList.append(N)
    PrimeFactList.append(1)
ans = 0

if PrimeFactList[0] == 1:
    print(0)
    exit()

opeList = [1, 3, 6, 10, 15, 21, 28, 36, 45]  # 同じ因数の連続操作に必要な累乗数
for i in range(1, len(PrimeFactList), 2):
    for j in range(len(opeList)):
        if PrimeFactList[i] < opeList[j]:
            ans += j
            break
print(ans)

Submission status: Accepted

Solution code:
from math import sqrt
from bisect import bisect


def main():
    N = int(input())
    factor = {}
    max_count = 1
    while N > 1:
        for i in range(2, int(sqrt(N)) + 1):
            if N % i == 0:
                N = N // i
                if i in factor:
                    factor[i] += 1
                    if max_count < factor[i]:
                        max_count = factor[i]
                else:
                    factor[i] = 1
                break
        else:
            if N in factor:
                factor[N] += 1
                if max_count < factor[N]:
                    max_count = factor[N]
            else:
                factor[N] = 1
            N = 1
    sum_up = [n * (n + 1) // 2 for n in range(max_count + 1)]
    ans = 0
    for prime, count in factor.items():
        ans += bisect(sum_up, count)-1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
N = int(input())
ans = 0
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

for i, j in factorization(N):
    if i == 1:
        print("0")
        sys.exit()
    n= 1
    while 2*j >= n*(n+1):
        n += 1
        ans += 1
    
print(ans)

Submission status: Accepted

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

def factorization(n):
    arr = []
    tmp = n
    i = 2
    while i ** 2 <= n:
        if tmp % i == 0:
            cnt = 0
            while tmp % i == 0:
                tmp //= i
                cnt += 1
            arr.append([i, cnt])
        i += 1
    if tmp != 1:
        arr.append([i, 1])
    if arr == []:
        arr.append([n, 1])
    return arr

def main():
    n = int(input())
    if n == 1:
        print(0)
        exit()

    f = factorization(n)
    ans = 0
    c = len(f)
    for i in range(c):
        s = 0
        g = f[i][1]
        if g <= 2:
            ans += 1
        else:
            for j in range(g):
                f[i][1] -= j+1
                s += j+1
                if s > g:
                    break
                ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def prime_factorize(n):
    result = []
    if n % 2 == 0:
        t = 0
        while n % 2 == 0:
            n //= 2
            t += 1
        result.append((2, t))
    for i in range(3, int(n ** 0.5) + 1, 2):
        if n % i != 0:
            continue
        t = 0
        while n % i == 0:
            n //= i
            t += 1
        result.append((i, t))
        if n == 1:
            break
    if n != 1:
        result.append((n, 1))
    return result


N = int(input())

result = 0
for p, e in prime_factorize(N):
    i = 1
    while e >= i:
        result += 1
        e -= i
        i += 1
print(result)

Submission status: Accepted

Solution code:
from math import sqrt


def prime_factorize(n):
    result = []
    if n % 2 == 0:
        t = 0
        while n % 2 == 0:
            n //= 2
            t += 1
        result.append((2, t))
    for i in range(3, int(sqrt(n)) + 1, 2):
        if n % i != 0:
            continue
        t = 0
        while n % i == 0:
            n //= i
            t += 1
        result.append((i, t))
        if n == 1:
            break
    if n != 1:
        result.append((n, 1))
    return result


N = int(input())

result = 0
for p, e in prime_factorize(N):
    i = 1
    while e >= i:
        result += 1
        e -= i
        i += 1
print(result)

Submission status: Accepted

Solution code:
from math import sqrt


def prime_factorize(n):
    result = []
    for i in range(2, int(sqrt(n)) + 1):
        if n % i != 0:
            continue
        t = 0
        while n % i == 0:
            n //= i
            t += 1
        result.append((i, t))
        if n == 1:
            break
    if n != 1:
        result.append((n, 1))
    return result


N = int(input())

result = 0
for p, e in prime_factorize(N):
    i = 1
    while e >= i:
        result += 1
        e -= i
        i += 1
print(result)

Submission status: Accepted

Solution code:
def pf(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())
from collections import Counter 
b = Counter(pf(n))

ans = 0
for i in b:
    a = b[i]
    for i in range(1,30):
        a -= i
        if a < 0:
            break
        ans += 1
        
print(ans)