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:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
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

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
if N == 1:
  print(0)
  exit()
ans = 0
for p,n in factorization(N):
  ans += int((math.sqrt(8*n+1)-1)/2)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def sieve(n):
    if n == 1:return []
    primes = [1 if i%2 == 1 else 0 for i in range(n + 1)]
    primes[1] = 0
    primes[2] = 1
    for i in range(3,n + 1,2):
        if i * i > n:
            break
        if primes[i]:
            for j in range(i * i,n + 1,i):
                primes[j] = 0
    return [p for p in range(2,n + 1) if primes[p] == 1]

def factorization(n,primes):
    factor = {}
    for p in primes:
        while n%p == 0:
            n //= p
            if p in factor:
                factor[p] += 1
            else:
                factor[p] = 1
    
    if n != 1:
        factor[n] = 1
    
    return factor

def main():
    N = int(input())
    primes = sieve(1000005)
    factor = factorization(N,primes)
    ans = 0
    for k,v in factor.items():
        i = 1
        while v - i >= 0:
            v -= i
            ans += 1
            i += 1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect


def factorization(n):
    arr = dict()
    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 not arr and n != 1:
        arr[n] = 1

    return arr


N = int(input())

tri = [i * (i + 1) // 2 for i in range(1, 50)]
ans = 0
for v in factorization(N).values():
    ans += bisect.bisect_right(tri, v)
print(ans)

Submission status: Accepted

Solution code:
def get_sieve_of_eratosthenes_new(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

prime=get_sieve_of_eratosthenes_new(10**6)

def ind(b,n):
    res=0
    while n%b==0:
        res+=1
        n//=b
    return res

N=int(input())
count={p:0 for p in prime}
for p in prime:
    a=ind(p,N)
    count[p]=a
    N//=p**a

if N!=1:
    count[N]=0
    count[N]=1

res=0
for p in count:
    if count[p]:
        t=(2*count[p])**0.5
        t=int(t)
        if 2*count[p]>=t*(t+1):
            res+=t
        else:
            res+=t-1

print(res)

Submission status: Accepted

Solution code:
import sys

import numpy as np
def sieve_of_eratosthenes(n=10**6):
  sieve = np.ones(n+1); sieve[:2] = 0
  for i in range(2, int(n**.5)+1):
    if sieve[i]: sieve[i*2::i] = 0
  return sieve, np.flatnonzero(sieve)

# def sieve_of_eratosthenes(n=10**6):
#   sieve = [1] * (n+1); sieve[0] = sieve[1] = 0
#   for i in range(2, int(n**.5)+1):
#     if not sieve[i]: continue
#     for j in range(i*2, n+1, i): sieve[j] = 0
#   prime_nums = [i for i in range(2, n+1) if sieve[i]]
#   return sieve, prime_nums

is_prime, prime_nums = sieve_of_eratosthenes()

def prime_factorize(n):
  res = dict()
  if n < 2: return res
  border = int(n**.5)
  for p in prime_nums:
    if p > border: break
    while n % p == 0: res[p] = res.get(p, 0)+1; n //= p
    if n == 1: return res
  res[n] = 1
  return res

def prime_factorize_fac(n):
  res = dict()
  for i in range(2, n+1):
    for p, c in prime_factorize(i).items(): res[p] = res.get(p, 0)+c
  return res

def main():
    n = int(sys.stdin.readline().rstrip())
    res = prime_factorize(n)
    ans = 0
    for m in res.values():
        i = 1
        while True:
            if (1 + i) * i // 2 > m:
                i -= 1
                break 
            i += 1
        ans += i
    print(ans)

    


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


def factor(n, m=None):
    # mを与えると、高々その素因数まで見て、残りは分解せずにそのまま出力する
    arr = {}
    temp = n
    M = min(m+1, int(-(-n**0.5//1))+1)
    for i in range(2, M):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i] = cnt

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

    if not arr:
        arr[n] = 1

    return arr

n = int(input())
f = factor(n, n)
ans = 0
if n==1:
    print(0)
else:
    for k,v in f.items():
        i = 1
        while v>=i:
            v -= i
            i += 1
            ans += 1
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
prime=[]
for i in range(2,int(n**0.5)+1):
	cnt=0
	while n%i==0:
		n//=i
		cnt+=1
	prime.append(cnt)
	if n==1:
		break
if n>1:
	prime.append(1)
ans=0
for x in prime:
	for i in range(1,x+1):
		if x>=i:
			ans+=1
			x-=i
		else:
			break
print(ans)

Submission status: Accepted

Solution code:
import bisect as bi
n=int(input())
ans=0
summ=[(i+2)*(i+1)//2 for i in range(100000)]
#summ[i]:=1~iの和
for divide in range(2,int(n**0.5)+1):
    if n==1:break
    cnt=0
    while n%divide==0:
        cnt+=1
        n//=divide
    if cnt==0:continue
    ans+=bi.bisect_right(summ,cnt)
print(ans+(n!=1))

Submission status: Accepted

Solution code:
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
n=N()
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
import collections
c=collections.Counter(prime_factorize(n))
ans=0
for i in c.values():
    t=1
    while i>=t:
        i-=t
        t+=1
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter


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())
pf = prime_factorize(n)
c = Counter(pf)

ans = 0
for v in c.values():
    i = 1
    while v > 0:
        v -= i
        i += 1
        if v >= 0:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
def factorization(n) -> list:
	ret = []
	i = 2
	while i * i <= n:
		while n % i == 0:
			n //= i
			ret.append(i)
		i += 1
	if n != 1:
		ret.append(n)
	return ret

n=int(input())
if n==1:
	print(0)
	exit()
c=Counter(factorization(n))
ans=0
for x in c.values():
	r=0
	while r*(r+1)//2<=x:
		r+=1
	ans+=r-1
print(ans)

Submission status: Accepted

Solution code:
def pfact(m):
	pf = {}
	for i in range(2,int(m**0.5)+1):
		while m%i == 0:
			pf[i] = pf.get(i,0) + 1
			m //= i
	if m>1 : pf[m]=1
	return pf

n = int(input())
pl = pfact(n).values()
ans = 0
for i in pl:
	k = i
	for j in range(1,41):
		k -= j
		if k < 0:
			break
		ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


def prime_factorize(n):
    ret = defaultdict(int)
    while n % 2 == 0:
        n //= 2
        ret[2] += 1
    d = 3
    while d * d <= n:
        while n % d == 0:
            n //= d
            ret[d] += 1
        d += 2
    if n > 1:
        ret[n] += 1
    return dict(ret)


n = int(input())
pf = prime_factorize(n)
ans = 0
for c in pf.values():
    i = 1
    while i <= c:
        c -= i
        i += 1
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

d = 2
ans = 0

while d * d <= n:
    if n % d != 0:
        d += 1
        continue

    z = d
    
    while n % z == 0:
        n //= z
        z *= d
        ans += 1

    while n % d == 0:
        n /= d

if n != 1:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
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)
ans = 0

for a,b in li:
    tmp = 0
    while tmp * (tmp+1) // 2 <= b:
        tmp += 1
    ans += tmp - 1

print(ans)

Submission status: Accepted

Solution code:
def make_prime_factors_compress(n: int) -> list:
    """自然数nの素因数を列挙した圧縮済みリストを出力する
    計算量：O(sqrt(N))
    入出力例：156 -> [(2, 2), (3, 1), (13, 1)]
    """
    prime_factors = []
    for k in range(2, int(n ** 0.5) + 1):
        cnt = 0
        while n % k == 0:
            cnt += 1
            n = n // k
        if cnt != 0:
            prime_factors.append((k, cnt))
    if n != 1:
        prime_factors.append((n, 1))
    return prime_factors


n = int(input())
primes = make_prime_factors_compress(n)
ans = 0
for _, cnt in primes:
     for i in range(10000):
         if i * (i + 1) // 2 > cnt:
            ans += i - 1
            break
print(ans)

Submission status: Accepted

Solution code:
def examA():
    A, B = LI()
    ans = A*B
    print(ans)
    return

def examB():
    N = I()
    A = LI()
    for a in A:
        if a==0:
            print(0)
            return
    ans = 1
    for a in A:
        ans *= a
        if ans>10**18:
            print(-1)
            return
    print(ans)
    return

def examC():
    A, B = list(map(float,input().split()))
    ans = int(A*B)
    print(ans)
    return

def examD():
    def factorization(n):
        arr = defaultdict(int)
        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 arr == []:
            arr[n] = 1
        return arr
    C = [0,1,3,6,10,15,21,28,36,45]
    N = I()
    F = factorization(N)
    ans = 0
    #print(F)
    for f in F.values():
        for i in range(10):
            if C[i]>f:
                ans += i-1
                break
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 1<<60
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
import bisect
from collections import defaultdict as dd
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct
N = int(input())
f = factorize(N)
dic=dd(int)
for val in f:
    if val!=1:
        dic[val] += 1
res = 0
ls = [1,3,6,10,15,21,28,36,45,55,66]
for val in dic.values():
    tmp = bisect.bisect_right(ls,val)
    res += tmp
print(res)

Submission status: Accepted

Solution code:
def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2, 7, 61] if n < 1<<32 else [2, 3, 5, 7, 11, 13, 17] if n < 1<<48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = y * y % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += i % 2 + (3 if i % 3 == 1 else 1)
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret
def sqrt(n):
    x = 1 << (n.bit_length() + 1) // 2
    y = (x + n // x) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x
def calc(k):
    return (sqrt(8*k+1) - 1) // 2

N  = int(input())
pf = primeFactor(N)
print(sum([calc(pf[p]) for p in pf]))

Submission status: Accepted

Solution code:
def factor(n):
    i = 2
    r = []
    while i * i <= n:
        if n % i == 0:
            c = 0
            while n % i == 0:
                c += 1
                n //= i
            r.append((i, c))
        i += 1
    if n > 1:
        r.append((n, 1))
    return r

def main():
    N = int(input())
    r = 0
    for p, e in factor(N):
        i = 1
        while e >= i:
            r += 1
            e -= i
            i += 1
    return r

print(main())

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    def PrimeDecomposition(N):
        ret = {}
        n = int(N ** 0.5)
        for d in range(2, n + 1):
            while N % d == 0:
                if d not in ret:
                    ret[d] = 1
                else:
                    ret[d] += 1
                N //= d
            if N == 1:
                break
        if N != 1:
            ret[N] = 1
        return ret

    N = int(input())
    P = PrimeDecomposition(N)
    ans = 0
    for d in P:
        a = P[d]
        for i in range(1, 100):
            if a >= i:
                a -= i
                ans += 1
            else:
                break
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
nmax = 10**6+10
eratos = [0 for i in range(nmax+1)]
prime = []
cnt = 2
while True:
  while cnt <= nmax and eratos[cnt]:
    cnt += 1
  if cnt > nmax:
    break
  eratos[cnt] = 1
  prime.append(cnt)
  for i in range(cnt**2,nmax+1,cnt):
    eratos[i] = 1
pr = []
for i in prime:
  while n%i == 0:
    n //= i
    pr.append(i)
if n > 1:
  pr.append(n)
c = Counter(pr)
ans = 0
for i in c.values():
  for j in range(10):
    if i < j*(j+1)//2:
      ans += j-1
      break
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
from collections import Counter

# O(sqrt(n))
def prime_factorize(n, unique=False):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    if unique:
        return set(fct)
    else:
        return fct

n = int(input())
fct = prime_factorize(n)
cnt = Counter(fct)
ans = 0
for key, val in cnt.items():
    cumsum = 0
    for i in range(1, 20):
        cumsum += i
        if cumsum <= val:
            ans += 1
        else:
            break
print(ans)

Submission status: Accepted

Solution code:
import math

def convert(nn):
    return math.floor(((nn*8+1)**0.5-1)/2)

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)
else:
    result=factorization(n)
    answer=0
    for i in range(len(result)):
        answer+=convert(result[i][1])
    print(answer)

Submission status: Accepted

Solution code:
N = int(input())

def prime_factor(x) :
  ret = dict()
  if x % 2 == 0 :
    ret[2] = 0
    while x % 2 == 0 :
      x //= 2
      ret[2] += 1
          
  i = 3
  while i * i <= x :
    if x % i == 0 :
      ret[i] = 0
      
      while x % i == 0 :
        x //= i
        ret[i] += 1
    i += 2
      
  if x != 1 :
    ret[x] = 1
  
  return ret

ret = 0
for k, v in prime_factor(N).items() :
  i = 1
  while v >= i :
    v -= i
    i += 1
    ret += 1
print(ret)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
#pyrival orz
import os
import sys
from io import BytesIO, IOBase

"""
    for _ in range(int(input())):
    n,m=map(int,input().split())
    n=int(input())
    a = [int(x) for x in input().split()]
"""

def main():
    ans=0
    n=int(input())
    i=2
    a=[]
    while i*i<=n:
        if not n%i:
            cnt=0
            while not n%i:
                cnt+=1
                n//=i
            a.append(cnt)
        i+=1
    if n>1:
        a.append(1)
    # print(a)
    for x in a:
        i=1
        while x>=i:
            ans+=1
            x-=i
            i+=1
    print(ans)

# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

def prime_factorization(n):
    assert n > 1
    factor=[]
    for d in range(2, int(n ** .5) + 1):
        while n % d == 0:
            n //= d
            factor.append(d)
    if n != 1: factor.append(n)
    return factor

from collections import Counter
def resolve():
    n = int(input())
    if n == 1:
        print(0)
        return
    C = Counter(prime_factorization(n))
    res = 0
    for v in C.values():
        n = 1
        while 2 * v >= n * (n + 1):
            n += 1
        res += n - 1

    print(res)
resolve()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul

mod = 10 ** 9 + 7
INF = 10 ** 13
sys.setrecursionlimit(2147483647)
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]



def prime_decomposition(n):
    D = defaultdict(int)
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            D[i] += 1
            n //= i
        if n == 1:
            break
    if n != 1:
        D[n] += 1
    return D

n = I()
ans = 0
DD = prime_decomposition(n)
for v in DD.values():
    now = 1
    while v >= now:
        v -= now
        ans += 1
        now += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

import math # version 3.5 >
from collections import defaultdict
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def lcm(*numbers):
    return reduce(lambda x,y: (x * y) // math.gcd(x, y), numbers, 1)

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=n_in()
f=factorize(n)



res = 0

for _,i in f:
    j=1
    while i-j >= 0:
        i=i-j
        j+=1
        res += 1

print(res)

Submission status: Accepted

Solution code:
import collections

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

n=int(input())
cnt=primes(n)
ans=0
for key in cnt.keys():
  val=cnt[key]
  for i in range(100):
    if (i*(i+1))//2>val:
      ans+=i-1
      break
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
def prime_factor(n):
  ass=[]
  for i in range(2,int(n**0.5)+1):
    while n%i==0:ass.append(i);n//=i
  if n!=1:ass.append(n)
  return ass
d=prime_factor(n)
from collections import Counter
ans=0
c=Counter(d)
for i in c:
  m=c[i]
  mm=1
  while mm<=m:
    m-=mm
    mm+=1
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
m = n
r = []
for i in range(2, n + 1):
    if i ** 2 > n:
        break
    if m % i == 0:
        c = 0
        while m % i == 0:
            m //= i
            c += 1
        r.append((i, c))
if m > 1:
    r.append((m, 1))
def calc(x):
    ans = 0
    for i in range(1, x + 1):
        if (1 + i) * i // 2 <= x:
            ans = i
        else:
            break
    return ans
ans = 0
for u, v in r:
    ans += calc(v)
print(ans)

Submission status: Accepted

Solution code:
import math


def prime_factors(n: int) -> list:
    tmp = n
    i = 2
    res = []
    while i*i <= n:
        cnt = 0
        while tmp%i==0:
            cnt += 1
            tmp //= i
        if cnt > 0:
            res.append((i, cnt))
        i += 1
    # add remaining factor
    if tmp > 1:
        res.append((tmp, 1))
    return res


def f(n):
    res = 1
    while res*(res+1)//2 <= n:
        res += 1
    return res-1


def main():
    N = int(input())
    ans = 0
    for _, ex in prime_factors(N):
        ans += f(ex)
    print(ans)
 
 
if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
n = int(input())


# nを素因数分解したリストを返す
def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(int(n))
    return table


from collections import defaultdict
dic = defaultdict(int)

for i in prime_decomposition(n):
    dic[i] += 1


ans = 0
for i in dic:
    k = dic[i]
    now = 1
    while k:
        k -= now
        if k == 0:
            ans += now
            break
        elif k < 0:
            ans += now - 1
            break
        now += 1

print(ans)

Submission status: Accepted

Solution code:
def prime_factorization(n):  # 素因数分解
    res = []
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                cnt += 1
                n //= i
            res.append((i, cnt))
    if n > 1:
        res.append((n, 1))
    return res


N = int(input())
pf = prime_factorization(N)

ans = 0
for p, f in pf:
    cnt = 1
    while True:
        if f >= cnt:
            ans += 1
            f -= cnt
            cnt += 1
        else:
            break
print(ans)