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:
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
n= int(input())
if n==1:
    print(0)
else:
    for a,b in factorization(n) :
        for i in range(1,10**12):
            if b < i:
                break
            else:
                b -= i
                ans += 1
    print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
from bisect import bisect

def soinsuu_bunkai(n):
    ret = {}
    p = 2
    while p * p <= n:
        while n % p == 0:
            ret[p]= ret[p]+1 if p in ret else 1
            n //= p
        p += 1
    if n != 1:
        ret[n] = 1
    return ret   
    
def make_triangle(n):
    cnt = 0
    sum_ = 0
    for i in range(1,n+1):
        sum_ += i
        if sum_ > n:
            break
        else:
            cnt += 1
    return cnt    

dic = soinsuu_bunkai(int(input()))
ans = 0
for k,v in dic.items():
    ans += make_triangle(v)  
print(ans)

Submission status: Accepted

Solution code:
def factor(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

def main():
    n = int(input())
    if n == 1:
        print(0); return
    fs = factor(n)
    ans = 0
    for f in fs:
        for e in range(1, f[1]+1):
            z = f[0] ** e
            if n % z == 0:
                n //= z
                ans += 1
    print(ans)

main()

Submission status: Accepted

Solution code:
from math import sqrt
pf={}
m=int(input())
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
#print(pf)

cnt = 0
calc = lambda n: (sqrt(8 * n + 1) - 1) // 2
for i in pf:
    v = pf[i]
    n = 1
    while v >= n:
        v -= n
        cnt += 1
        n += 1
#    cnt += calc(pf[i])
print(int(cnt))

Submission status: Accepted

Solution code:
from sys import stdin

def waru(a,b):
  if a%b != 0:
    return 0
  if a/b == 1:
    return b
  return waru(a/b,b)
  

def main():
  s = []
  read = stdin.readline
  N =int(read())
  if N == 1:
    print(0)
    exit()
  i = 2
  table = []
  ap = table.append
  while i * i <= N:
    while N%i == 0:
      ap(i)
      N //= i
    i += 1
  if N > 1:
    ap(N)
  set_table = sorted(list(set(table)))
  kaisu = [0] * len(set_table)
  num = 0
  for i in table:
    if i == set_table[num]:
      kaisu[num] += 1
    else:
      num += 1
      kaisu[num] += 1
  maxk = max(kaisu)
  j = 1
  k = 0
  count = 0
  while j <= maxk:
    count += len([i for i in kaisu if i >= j])
    k += 1
    j = j + k + 1
  print(count)
    
      
      

  
  
  
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()

def factor(x):
    i = 2
    l = []
    while i**2 <= x:
        y = 0
        while x%i == 0:
            x/=i
            y+=1
        if y != 0:
            l.append([i,y])
        i+=1
    
    if x != 1:
        l.append([x,1])
    return l

l = factor(n)
# print(l)

ans = 0
for i in l:
    p = i[0]
    c = i[1]
    b = 1
    while c >= b:
        ans += 1
        c -= b
        b += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby

def fact(n):
    table = []
    i = 2
    
    while(i*i <= n):
        while(n%i == 0):
            n //=i
            table.append(i)
        i += 1
    if(n > 1):
        table.append(n)
    return table

def main():
    N = int(input())
    P = fact(N)
    ans = 0
    for v, g in groupby(P):
        n = len(list(g))
        for i in range(1, 100000):
            n -= i
            if(n >= 0):
                ans += 1
            else:
                break
    print(ans)
    
main()

Submission status: Accepted

Solution code:
n = int(input())
if n == 1:
    print(0)
    exit()

from collections import Counter
def factorize(n):    
    d = Counter()
    if n < 2:
        return d
    
    while n%2 == 0:
        n //= 2
        d[2] += 1

    m = 3
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m += 2
    if n > 1:
        d[n] += 1
    return d
 
fac = factorize(n)
ans = 0
for v in fac.values():
    n = 1
    while v >= n:
        v -= n
        ans += 1
        n += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
if n == 1:
    print(0)
    exit()

from collections import Counter
def factorize(n):
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m += 1
    if n > 1:
        d[n] += 1
    return d
 
fac = factorize(n)
ans = 0
for v in fac.values():
    n = 1
    while v >= n:
        v -= n
        ans += 1
        n += 1
print(ans)

Submission status: Accepted

Solution code:
from math import sqrt
pf={}
m=int(input())
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
#print(pf)

cnt = 0
calc = lambda n: (sqrt(8 * n + 1) - 1) // 2
for i in pf:
    cnt += calc(pf[i])
print(int(cnt))

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


def run_prime_factorization(max_number: int) -> dict:
    '''Run prime factorization.
    Args:
        max_number: Int of number (greater than 1).
    Returns:
        A dictionary's items ((base, exponent) pairs).
    Landau notation: O(log n)
    '''

    from math import sqrt

    ans = dict()
    remain = max_number

    for base in range(2, int(sqrt(max_number)) + 1):
        if remain % base == 0:
            exponent_count = 0

            while remain % base == 0:
                exponent_count += 1
                remain //= base

            ans[base] = exponent_count

    if remain != 1:
        ans[remain] = 1

    return ans


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

    p = run_prime_factorization(n)
    ans = 0

    for _, value in p.items():
        count = 0

        for i in range(1, 40):
            if (i * (i + 1)) <= 2 * value:
                count += 1

        ans += count

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

def prime_factrization(n):
    factor = []
    tmp = int(math.sqrt(n)) + 1
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor.append(num)

    if not factor:
        return 0
    else:
        if n != 1:
            factor.append(n)
        return list(factor)

ans = 0
N = int(input())
factor = prime_factrization(N)
if N == 1:
    print(0)
elif factor == 0 and N != 1:
    print(1)
else:
    for i in list(set(factor)):
        num = factor.count(i)
        j = 1
        a = 1
        while j <= num:
            ans += 1
            a += 1
            j += a
    print(ans)

Submission status: Accepted

Solution code:
N=int(input())
NN = N
i = 2
ans = 0
while i*i <= NN:
  if N%i==0:
    j = 0
    while N%i==0:
      N /= i
      j+=1
    k = 1
    while j>0:
      if j - k < 0: break
      ans += 1
#      print(i,ans,j,k)
      j -= k
      k += 1
  i += 1
if N != 1:
  ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

#素因数分解
def factorize_dict(n):
    b = 2
    fct = dict()
    while b * b <= n:
        while n % b == 0:
            n //= b
            #fct.append(b)
            if b not in fct:
                fct[b] = 1
            else:
                fct[b] += 1
        b = b + 1
    if n > 1:
        #fct.append(n)
        if n not in fct:
            fct[n] = 1
        else:
            fct[n] += 1
            
    return fct

factorized_N = factorize_dict(N)
#print(factorized_N)

z_list = []

for f_dict in factorized_N.items():
    prime_number = f_dict[0]
    how_many = f_dict[1]
    z_list += [prime_number**i for i in range(1,how_many+1)]
    
z_list.sort(reverse=False)
#print(z_list)

ans = 0
for z in z_list:
    if N%z == 0:
        ans += 1
        N /= z
        if N == 1:
            break
        
print(ans)

Submission status: Accepted

Solution code:
def main():
    def factorization(n):
        arr = []
        tmp = n
        for i in range(2, int(-(-tmp**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 tmp == []:
            arr.append([n, 1])
        return arr
    n = int(input())
    fn = factorization(n)
    x = [fn[i][1] for i in range(len(fn))]
    b = 1
    res = 0
    for i in x:
        while b <= i:
            i -= b
            b += 1
            res += 1
        b = 1
    print(res)   

if __name__ == '__main__':
    main()

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())
div = factorization(N)

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

ans = 0
# print(div)
for d in div:
    c = d[1]
    i = 1

    while c >= 0:
        c -= i
        if c >= 0:
            ans += 1
        i += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter


def main():
    n = int(input())
    m = n
    factorization_p = []
    while m % 2 == 0:
        factorization_p.append(2)
        m //= 2
    prime_num = 3
    while prime_num * prime_num <= m:
        if m % prime_num == 0:
            factorization_p.append(prime_num)
            m //= prime_num
        else:
            prime_num += 2
    if m != 1:
        factorization_p.append(m)
    factorization_p = Counter(factorization_p)
    answer = 0
    for _, p in factorization_p.items():
        i = 1
        p *= 2
        while i * (i + 1) <= p:
            answer += 1
            i += 1
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

ans = 0
for i in range(2,int(n**0.5)+1):
    count = 1
    loop = 1
    while n % i == 0:
        n = int(n/i)
        count -= 1
        if count == 0:
            ans += 1
            loop += 1
            count = loop

if n > 1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

def factors(n: int):
    l = []
    for i in range(2, int(n**0.5) + 1):
        #prime factorization
        while n % i == 0:
            n //= i
            l.append(i)
    if n > 1:
        l.append(n)
    return l

c = Counter(factors(int(input())))
ans = 0
for items,values in c.items():
    cnt = 1
    while cnt <= values:
        values -= cnt
        ans += 1
        cnt += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
factors = []
i = 2
while N > 1:
  if N < i * i:
    factors.append(N)
    break
  while N % i == 0:
    factors.append(i)
    N //= i
  i += 1

ans = 0
for count in Counter(factors).values():
  i = 1
  while count >= i:
    count -= i
    i += 1
    ans += 1
print(ans)

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): #各素因数の指数について、k(k+1)//2<=(指数)を満たす最大のkを求める
        if (i*(i+1))//2>val:
            ans+=i-1
            break
print(ans)

Submission status: Accepted

Solution code:
import math
N=int(input())
L=[]
for i in range(2,int(math.sqrt(N))):
    if N%i==0:
        c=0
        while N%i==0:
            N/=i
            c+=1
        L.append(c)
if N!=1:
    L.append(1)
ans=0
for i in L:
    for n in range(10):
        if (n*(n+1))//2>i:
            ans+=n-1
            break
print(ans)

Submission status: Accepted

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


def get_knu(a):
    before = 1
    n = 2
    while True:
        knum = (n * (n + 1)) // 2
        if a == knum:
            return n
        elif knum > a > before:
            return n - 1
        else:
            n += 1
            before = knum


D = int(input())
p = get_prime_fact(D)

if len(p) != len(set(p)):
    res = 0
    for n in set(p):
        count = p.count(n)
        if count == 1:
            res += 1
        else:
            add = get_knu(count)
            res += add

    print(res)
else:
    print(len(p))

Submission status: Accepted

Solution code:
n = int(input())
if n == 1:
    print(0)
    exit()

def fact(n):
    arr = []
    res = []
    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])
            res.append(cnt)
    if temp!=1:
        arr.append([temp, 1])
        res.append(1)

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


    return res

alist = fact(n)
#print(alist)
ans = 0
for a in alist:
    for i in range(1,a+3):
        if a < i*(i+1)//2:
            #print(i-1)
            ans += i-1
            break

print(ans)

Submission status: Accepted

Solution code:
def prime_factorization(N):
    tmp = N
    ans = []
    for i in range(2, int(N ** 0.5) + 1):
        count = 0
        while tmp % i == 0:
            tmp //= i
            count += 1
        if count != 0:
            ans.append([i, count])
    if tmp != 1:
        ans.append([tmp, 1])
    if ans == []:
        ans.append([N, 1])
    return ans

def GetLimit(x):
    X = 2*x
    n = 1
    while True:
        if n*(n+1) <= 2 * x < (n+1)*(n+2):
            return n
        n += 1
N = int(input())
if N==1:
    print(0)
    exit()
PrimeList = prime_factorization(N)
ans = 0
for a, b in PrimeList:
    ans += GetLimit(b)
print(ans)

Submission status: Accepted

Solution code:
"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の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())
f = factorization(n)

#print(n)
#print(f)

ans = 0
for i in range(len(f)):
  if f[i][0] == 1:
    continue
  t = f[i][1]
  #print(t)
  
  for j in range(1, 40):
    if (t - j) < 0:
      break
    ans += 1
    t -= j

print(ans)

Submission status: Accepted

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

l=factorization(n)

ans=0
cnt=1
if n==1:
  print(0)
else:
  for i,e in l:
    cnt=1
    while(cnt<=e):
      e-=cnt
      ans+=1
      cnt+=1
  print(ans)

Submission status: Accepted

Solution code:
import math
n=int(input())
ans=0
for i in range(2,int(math.sqrt(n)+1)):
    if n%i==0:
        prime=i
        power=0
        while n%i==0:
            n=n//i
            power+=1
        st=1
        while st<=power:
            ans+=1
            power-=st
            st+=1
if n>1:
    ans+=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

def maxsum(e):
	n = 0
	while n*(n + 1)/2 <= int(e):
		n = n + 1 
	return n - 1

def solve(N):
	if N == 1:
		return 0
	fac = factorization(N)
	sum = 0
	for ret in fac:
		sum = sum + maxsum(ret[1])
	return sum

N = input()
print(solve(N))

Submission status: Accepted

Solution code:
N = int(input())


# try div
def prime_factorize(n: int): 
    ret = []

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


pf = prime_factorize(N)
# print(pf)
ans = 0
from collections import Counter

cpf = Counter(pf)
# print(cpf)
for k, v in cpf.items():
    e = v
    tmp = 0
    cur = 1

    while e >= cur:
        e -= cur
        cur += 1
        tmp += 1
    
    ans += tmp

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().strip())
c = collections.Counter(prime_factorize(n))
ans = 0
for elem in c.items():
    count = 1
    value = elem[1]
    while True:
        value -= count
        count += 1
        ans += 1
        if value < count:
            break
print(ans)

Submission status: Accepted

Solution code:
import math

def prime(x):
    if x==1:
        prime=False
    else:
        prime=True
        for i in range(2,int(math.sqrt(x)+1)):
            if x%i==0:
                prime=False
                break
    return prime

def count_prime(N):
    p=[0 for n in range(int(math.sqrt(N)+1))]
    
    if prime(N):#初期値が素数の場合
        big_prime=True
        
    else:#初期値が素数でない場合
        big_prime=False
        rtN_init=int(math.sqrt(N)+1)
        
        #素因数分解。ルートＮまでの範囲で素因数を探す。見つかったらpの素因数インデックスを++
        while N>1:
            #素数がルートNを超える場合
            if prime(N) and N>rtN_init:
                big_prime=True
                break
            else:
                for i in range(2,rtN_init):
                    if N%i==0 and prime(i):
                        p[i]+=1
                        N=N//i
                        break
    return p,big_prime

def main():
    N=int(input())
    p,q=count_prime(N)
    cnt=0
    
    for n in range(len(p)):
        num=1
        while p[n]>=1:
            p[n]-=num
            if p[n]>=0:
                cnt+=1
                num+=1
    if q==True:
        cnt+=1
    print(cnt)
        
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
# D - Div Game
from collections import defaultdict
from math import sqrt
from typing import ValuesView


def prime_factorize_indices(n: int) -> ValuesView[int]:
    """Prime factorization of n (trial division)."""
    if n < 1:
        raise ValueError

    prime_factors = defaultdict(int)
    while n % 2 == 0:
        n //= 2
        prime_factors[2] += 1

    for i in range(3, int(sqrt(n)) + 1, 2):
        while n % i == 0:
            n //= i
            prime_factors[i] += 1
        if n == 1:
            break

    if n > 2:  # n is prime
        prime_factors[n] += 1

    return prime_factors.values()


def main():
    N = int(input())
    calc = lambda n: (sqrt(8 * n + 1) - 1) // 2
    print(int(sum(calc(e) for e in prime_factorize_indices(N))))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
n = int(input())
a = []
b= []
while n % 2 == 0:
    b.append(2)
    n //= 2
if(len(b)!= 0):
    a.append(b)
    b= [] 
f = 3
while f * f <= n:

    if n % f == 0:
        b.append(f)
        n //= f
    else:
        f += 2
        if(len(b)!= 0):
            a.append(b)
            b= [] 

if(len(b)!= 0):
        a.append(b)
        b= [] 
if(len(a) != 0):
    if(n == a[len(a)-1][0]):
        a[len(a)-1].append(n)
        n  = 1
if (n != 1 ):
    b.append(n)
    a.append(b)

ans =0
for i in range(len(a)):
    ans += int((-1 + math.sqrt(1 + 8 * len(a[i])))/2)

print(ans)

Submission status: Accepted

Solution code:
# D - Div Game
from collections import defaultdict
from math import sqrt
from typing import ValuesView


def prime_factorize_indices(n: int) -> ValuesView[int]:
    """Prime factorization of n (trial division)."""
    if n < 1:
        raise ValueError

    prime_factors = defaultdict(int)
    while n % 2 == 0:
        n //= 2
        prime_factors[2] += 1

    for i in range(3, int(sqrt(n)) + 1, 2):
        while n % i == 0:
            n //= i
            prime_factors[i] += 1
        if n == 1:
            break

    if n > 2:  # n is prime
        prime_factors[n] += 1

    return prime_factors.values()


def main():
    N = int(input())
    calc = lambda n: int((sqrt(8 * n + 1) - 1) / 2)
    print(sum(calc(e) for e in prime_factorize_indices(N)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def factorize(n):
    res = []
    i = 2
    while i * i <= n:
        cnt = 0
        while n % i == 0:
            cnt += 1
            n //= i
        if cnt > 0:
            res.append([i, cnt])
        i += 1
    if n != 1:
        res.append([n, 1])
    return res

n = int(input())
nlist = factorize(n)
ans = 0
for k, v in nlist:
    i = 1
    while v >= i:
        v -= i
        i += 1
    ans += i-1
print(ans)

Submission status: Accepted

Solution code:
# D - Div Game
from collections import defaultdict
from math import sqrt
from typing import Dict


def prime_factorize_naive(n: int) -> Dict[int, int]:
    """Prime factorization of n (trial division)."""
    if n < 1:
        raise ValueError

    prime_factors = defaultdict(int)
    while n % 2 == 0:
        n //= 2
        prime_factors[2] += 1

    for i in range(3, int(sqrt(n)) + 1, 2):
        while n % i == 0:
            n //= i
            prime_factors[i] += 1
        if n == 1:
            break

    if n > 2:  # n is prime
        prime_factors[n] += 1

    return prime_factors


def main():
    N = int(input())
    calc = lambda n: int((sqrt(8 * n + 1) - 1) / 2)
    print(sum(calc(e) for e in prime_factorize_naive(N).values()))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math

N = int(input())

fact = set()
counter = 0

for i in range(2, int(math.sqrt(N))+1):
    if N % i != 0:
        continue
    powt = 0
    while N % i == 0:
        powt += 1
        N /= i
    fact.add((i, powt))

if N != 1:
    fact.add((N, 1))

for base, e in fact:
    for t in range(1, e+1):
        if t <= e:
            e -= t
            counter += 1
print(counter)

Submission status: Accepted

Solution code:
n=int(input())

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)
    divisors.sort()
    return divisors

def prime_fact(x):
    fact=[]
    for i in range(2, int(x**(0.5))+1):
        while x%i==0:
            fact.append(i)
            x//=i
    if x!=1:
        fact.append(x)
    if not fact:
        fact=[x]
    return fact

divisors=make_divisors(n)
divisors.pop(0)
cnt=0
for div in divisors:
    # print(n,div)
    # print(div, prime_fact(div), set(prime_fact(div)))
    if len(set(prime_fact(div)))==1 and n>1 and n%div==0:
        n//=div
        cnt+=1
    elif n<1:
        break
print(cnt)

Submission status: Accepted

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

a = factorization(n)
b = [1,3,6,10,15,21,28,36,43]
ans = 0
if len(a) == 1 and a[0][0] == 1:
    print(0)
    exit()
for i in a:
    for j in range(len(b)):
        if i[1] <b[j]:
            ans += j
            break
print(ans)

Submission status: Accepted

Solution code:
def is_prime(num:int):
    if num == 1:
        return False
    elif num == 2:
        return True
    elif num % 2 == 0:
        return False

    r_num = int(num ** 0.5)
    for i in range(3, r_num + 1, 2):
        if num % i == 0:
            return False
    return True


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

    if n == 1:
        print(0)
        return

    cnt = 0
    r_n = int(n ** 0.5)
    divided = []
    for i in range(2, n):
        if n < i:
            break
        elif cnt == 0 and r_n+1 < i:
            break
        if n % i == 0 and is_prime(i):
            n = int(n/i)
            divided.append(i)
            cnt += 1
            x = 2
            while True:
                q = i ** x
                if q > n:
                    break

                if n % q == 0:
                    n = int(n/q)
                    x += 1
                    cnt += 1
                else:
                    break
            if is_prime(n) and n not in divided:
                n = 1
                cnt += 1
                break

    if cnt == 0:
        cnt = 1
    print(cnt)


main()

Submission status: Accepted

Solution code:

import sys
import math
import itertools
import collections

# H1,M1,H2,M2,K = map(int,input().split())
# H2 -= K//60
# M2 -= K % 60

# print((H2 - H1) * 60 + (M2 - M1))

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[i]=cnt

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

    if arr==[]:
        arr[n] = 1

    return arr

factorization(24) 

## [[2, 3], [3, 1]] 
##  24 = 2^3 * 3^1

N = int(input())
dic = factorization(N)
cnt = 0

for key,value in sorted(dic.items()):
    if(N == 1):
        break
    for i in range(1,value+1):
        if(N % key ** i != 0):
            break
        N //= key ** i
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
def prime(p):
    memo = []
    for i in range(2,(int(p**0.5)+1)):
        while p%i==0:
            p //= i
            memo.append(i)
    if p != 1:
        memo.append(p)
    return memo

import collections

n=int(input())

memo = prime(n)

memo = collections.Counter(memo)

memo = sorted(memo.items(), key=lambda x:-x[1])

ans = 0

for sosu, count in memo:
  kosu = 1
  while 0 <= count-kosu:
    count -= kosu
    ans += 1
    kosu += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    ans = 0
    e = 1

    def facs():
        yield 2
        for x in range(10 ** 6):
            yield x * 2 + 3

    for fac in facs():
        while n % (div := pow(fac, e)) == 0:
            n //= div
            ans += 1
            e += 1
        while n % fac == 0:
            n //= fac
        if fac * fac > n:
            break
        e = 1

    if n != 1:
        ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    ans = 0
    e = 1
    facs = (2 if x == 0 else x * 2 + 1 for x in range(10 ** 6))
    for fac in facs:
        while n % (div := pow(fac, e)) == 0:
            n //= div
            ans += 1
            e += 1
        while n % fac == 0:
            n //= fac
        if fac * fac > n:
            break
        e = 1

    if n != 1:
        ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    ans = 0

    fac = 2
    e = 1
    while True:
        if n % (div := pow(fac, e)) == 0:
            n //= div
            ans += 1
            e += 1
            continue

        while n % fac == 0:
            n //= fac

        if fac == 2:
            fac += 1
        else:
            fac += 2

        if fac * fac > n:
            break
        e = 1

    if n != 1:
        ans += 1

    print(ans)


if __name__ == '__main__':
    main()