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

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

a = [0 for _ in range(40)]
start = 0
for i in range(8):
    a[start:start+(i+2)] = [i+1 for _ in range(i+2)]
    start = start + (i+2)

ans = 0
for i in list(c.values()):
    ans += a[i-1]

print(ans)

Submission status: Accepted

Solution code:
def factorization(n): #素因数分解のプログラム([素因数,指数]のリストのリストで出力→24→[[2, 3], [3, 1]])
    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 

import math
import sys
n = int(input())
ls = factorization(n)
q = 0
if n == 1:
    print(0)
    sys.exit()
for i in range(len(ls)):
    j = 1
    k = 2
    p = 0
    while True:
        if ls[i][1] >= j:
            j += k
            p += 1
            k += 1
        else:
            break
    q += p
print(q)

Submission status: Accepted

Solution code:
"""素因数分解"""
def prime_decomposition(n):
    i = 2
    tank = []
    while i * i <= n:
        while n%i == 0:
            n /= i
            tank.append(i)
        i += 1
    if n > 1:
        tank.append(int(n))
    return tank

from collections import Counter

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

lst = prime_decomposition(n)
c = Counter(lst)
ans = 0

for k,v in c.items():
    j = 1
    while True:
        if j*(j+1)//2 <=v:
            j += 1
        else:
            break
    ans += j-1
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

ans = factorization(n)
val = 0
for arr in ans:
    tmp = arr[1]
    for i in range(1,50):
        tmp = tmp -(i)
        if tmp < 0:
            val +=i - 1
            break
if n == 1:
    print(0)
else:
    print(val)

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

arr = factorization(n)
cnt = 0
for i in arr:
    if i[0] == 1:
        continue
    hiku = 1
    while i[1] > 0:
        i[1] = i[1] - hiku
        if i[1] < 0:
            break
        hiku +=1
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
# coding: utf-8
#import numpy as np
import re
import math
from collections import defaultdict
from collections import deque
import collections
from fractions import Fraction
import bisect
from queue import PriorityQueue
import itertools
from copy import deepcopy
import random
import time
import os
import sys
import datetime
from functools import lru_cache
from functools import reduce
readline=sys.stdin.readline
sys.setrecursionlimit(2000000)
alphabet="abcdefghijklmnopqrstuvwxyz"
numbers="0123456789"
mod=int(10**9+7)
inf=int(10**19)
class Edge():
    def __init__(self,x,y,val=1):
        self.x=x
        self.y=y
        self.val=val
class unionfind():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(n)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):
            self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def yn(b):
    if b:print("yes")
    else:print("no")
def Yn(b):
    if b:print("Yes")
    else:print("No")
def YN(b):
    if b:print("YES")
    else:print("NO")
def ispow(a,b):
    now=b
    while now<a:
        now*=b
    return now==a
def getbin(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def getfacs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod_>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def nextcomb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:return num
def getprimes(n):
    if n==0:return []
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    ret=[]
    for a in range(n+1):
        if(A[a]):ret.append(a)
    return ret
def isprime(num):
    if(num<=1):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(bbool,ret1,ret2):
    if bbool:return ret1
    else:return  ret2
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n):
    b = 2
    ret=defaultdict(int)
    while b * b <= n:
        while n % b == 0:
            n //= b
            ret[b]+=1
        b+=1
    if n > 1:ret[n]+=1
    return ret
def pm(x):
    return x//abs(x)
def inputintlist(): 
    return list(map(int,input().split()))
def istanchouzouka(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>=a:
            f=False
        prev=a
    return f
def istanchouhigensyou(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>a:
            f=False
        prev=a
    return f
def getallsum(A):
    s=sum(A)
    dp=defaultdict(int)
    dp[0]=1
    for a in range(0,len(A)):
        for b in range(s,-1,-1):
            if b-A[a]>=0:
                dp[b]+=dp[b-A[a]]
    return dp
def yuukoutomukou(edges):
    ret=deepcopy(edges)
    for edge in edges:
        if not edge.x==edge.y:
            ret.append(Edge(edge.y,edge.x,edge.val))
    return ret
def dijkstra(edges,V,start):
    mincost=[inf]*V
    G=[[] for a in range(V)]
    for edge in edges:
        G[edge.x].append([edge.val,edge.y])
    Q=PriorityQueue()
    Q.put([0,start])#[cost,x]
    while not Q.empty():
        nowcost,nowx=Q.get()
        if mincost[nowx]==inf:
            mincost[nowx]=nowcost
            for cost,y in G[nowx]:
                newcost=nowcost+cost
                Q.put([newcost,y])
    return mincost
def warshallfloyd(edges,V):
    mincost=[[inf for b in range(V)] for a in range(V)]
    for a in range(V):mincost[a][a]=0
    for edge in edges:
        mincost[edge.x][edge.y]=min(mincost[edge.x][edge.y],edge.val)#x→yが複数ある場合のためにmin()する
    for k in range(V):
        for s in range(V):
            for t in range(V):
                if mincost[s][k]==inf or mincost[k][t]==inf:continue
                mincost[s][t]=min(mincost[s][t],mincost[s][k]+mincost[k][t])
    return mincost
def bellemanford(edges,V,start):
    mincost=[inf]*V
    mincost[start]=0
    for _ in range(V):
        for edge in edges:
            if mincost[edge.x]==inf:continue
            mincost[edge.y]=min(mincost[edge.y],mincost[edge.x]+edge.val)
    return mincost
def ruisekiwa(A):
    ret=[0]*(len(A)+1)
    for a in range(len(A)):
        ret[a+1]=ret[a]+A[a]
    return ret
def getmd(x1,y1,x2,y2):
    return abs(x1-x2)+abs(y1-y2)
def geted(x1,y1,x2,y2):
    return math.sqrt((x1-x2)**2+(y1-y2)**2)
class fordfulkerson():
    def __init__(self,edges,V,s,t):
        self.V=V
        self.used=[False]*V
        self.G=[[] for a in range(V)]
        self.s=s
        self.t=t
        for edge in edges:
            self.G[edge.x].append({"x":edge.x,"y":edge.y,"cap":edge.val,"rev":len(self.G[edge.y])})
            self.G[edge.y].append({"x":edge.y,"y":edge.x,"cap":0,"rev":len(self.G[edge.x])-1})
    def dfs(self,v,t,f=inf):
        if v==t:return f
        self.used[v]=True
        for a in range(len(self.G[v])):
            x=self.G[v][a]["x"]
            y=self.G[v][a]["y"]
            cap=self.G[v][a]["cap"]
            rev=self.G[y][self.G[x][a]["rev"]]
            if self.used[y] or cap==0:continue
            f2=self.dfs(y,t,min(f,cap))
            if f2>0:
                self.G[v][a]["cap"]-=f2
                rev["cap"]+=f2
                return f2
        return 0
    def maxflow(self):
        flow=0
        while True:
            self.used=[False]*V
            zouka=self.dfs(self.s,self.t)
            if zouka==0:break
            flow+=zouka
        return flow



######################################################################################################
n=int(input())
ans=0
A=[0]
for a in range(1,10000):
    A.append(a+A[-1])
fac=factorize(n)
for a,cnt in fac.items():
    i=bisect.bisect_right(A,cnt,lo = 0,hi = len(A))-1
    ans+=i

print(ans)

Submission status: Accepted

Solution code:
def main():
    def factorization(num):
        result = []
        count = 0
        temp = num
        for i in range(2, int(num ** 0.5) + 1):
            if temp % i == 0:
                count = 0
                while temp % i == 0:
                    count += 1
                    temp /= i
                result.append(count)
        if temp != 1:
            result.append(1)
        return result
    C = []
    c = 0
    for i in range(1, 40):
        c += i
        C.append(c)
    def combi(num, C):
        for i, c in enumerate(C):
            if num < c:
                return i
        return -1
    n = int(input())
    exps = factorization(n)
    count = 0
    for e in exps:
        count += combi(e, C)
    print(count)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def prime(n):
    factor = {}
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            if not num in factor.keys():
                factor[num] = 1
            else:
                factor[num] += 1
        if num > n:
            break
    if n != 1:
        if not n in factor.keys():
            factor[n] = 1
        else:
            factor[n] += 1
    return factor

#print(prime(n))

ans = 0

#dic = {}
pr = prime(n)
for num, count in pr.items():
    tmp = count
    ini = 1
    while tmp > 0:
        tmp -= ini
        if tmp < 0:
            break
        ini += 1
        ans += 1
    #print(ans,num,tmp)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())


from collections import Counter
def prime_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

soinsu = prime_factorize(n)

sankaku = [1]*20

from bisect import bisect_right

for i in range(1,20):
    sankaku[i] = sankaku[i-1]+(i+1)

ans=0
for k,v in soinsu.items():
    index = bisect_right(sankaku,v)
    ans += index

print(ans)

Submission status: Accepted

Solution code:
from collections import deque, Counter
def prime_factorize(n):
    a = deque([])
    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())
A = Counter(prime_factorize(N))
B = [1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66]
ans = 0
for i in A:
    for j in range(len(B)):
        if B[j] <= A[i] < B[j + 1]:
            ans += (j + 1)
            break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
ans = 0
for i in range(2,int(N**(1/2)//1)+1):
  if N%i == 0:
    cnt = 0
    while N%i == 0:
      N //= i
      cnt += 1
    for j in range(1,cnt+1):
      if cnt - j >=0:
        cnt -= j
        ans += 1
      else:
        break
  else:
    continue   
if N != 1:
  ans += 1     
print(ans)

Submission status: Accepted

Solution code:
from math import sqrt

def fact(n):
    F_dict,F_set = {},set()
    for i in range(2,int(sqrt(n))+1):
        if n % i == 0:
            F_dict[i] = 1
            F_set.add(i)
            n //= i
            while n % i == 0:
                F_dict[i] += 1
                n //= i
        if n == 1:
            break

    if n != 1:
        F_dict[n] = 1
        F_set.add(n)

    return (F_dict,F_set)

def main_cal(F_dict,F_set):
    output = 0
    for f in F_set:
        num = 1
        while F_dict[f] > 0:
            if F_dict[f] >= num:
                F_dict[f] -= num
                num += 1
            else:
                break
        output += (num-1)
    return output

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

    fa = fact(N)
    print(main_cal(fa[0],fa[1]))

if __name__ == "__main__":
    main()

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
List = factorization(N)
ans = 0
for i in range(len(List)):
  X = List[i][1]
  j = 1
  num = 0
  if List[i][0] != 1:
    while True:
      X -= j
      j += 1
      if X >= 0:
        num += 1
      else:
        break
    ans += num
  
print(ans)

Submission status: Accepted

Solution code:
from math import floor
from math import sqrt
N = int(input())
def f(x):
  return (floor((-1+sqrt(1+8*x))/2.0))
ans = 0
i = 2
while N > 1:
  x = 0
  while N % i == 0:
    N = N // i
    x = x + 1
  if x != 0:
    ans = ans + f(x)
  i = i + 1
  if i > 10 ** 6:
    ans = ans + 1
    break
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import OrderedDict
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect,math,heapq
alphabet = "abcdefghijklmnopqrstuvwxyz"


def primeFactors(n):
	count = defaultdict(int)
	while n % 2 == 0: 
		count[2]+=1 
		n = n / 2 
	for i in range(3,int(math.sqrt(n))+1,2): 
		while n % i== 0: 
			count[i]+=1
			n = n / i 
	if n > 2: 
		count[n]+=1
	return count


n = int(input())
c = primeFactors(n)
ans = 0
for k,v in c.items():
	ans += (-1 + (1+8*v)**0.5)//2
print(int(ans))

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

def judge(N):
  n = 0
  cnt = 0
  while n < N:
    n += cnt+1
    if n<=N:
      cnt += 1
  return cnt


c = collections.Counter(prime_factorize(N))

ans = 0


keys = c.keys()

for i in range(len(keys)):
  ans += judge(c[list(keys)[i]])

print(ans)

Submission status: Accepted

Solution code:

#!/usr/bin/python
# -*- coding: utf-8 -*-

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

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


c = collections.Counter(prime_factorize(N))

ans = 0

a = list(c.values())

for i in range(len(a)):
    cnt = 1
    while True:
        a[i] -= cnt
        cnt += 1
        if a[i] <0:
            break
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import accumulate
from bisect import bisect_right


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


stairs = list(accumulate(i for i in range(1, 64)))
N = int(input())
factors = factor(N)
ans = 0
for cnt in Counter(factors).values():
    ans += bisect_right(stairs, cnt)
print(ans)

Submission status: Accepted

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

def available_n(v):
    value = ((1+8*v)**(1/2) - 1)/2
    return math.floor(value)

n=int(input())
ls = prime_factorize(n)
d={}
for i in ls:
    d.setdefault(i,0)
    d[i]=d[i]+1

count=0
for k,v in d.items():
    count+=available_n(v)

print(count)

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

count = 0
a = factorization(n)
if n == 1:
  print(0)
  exit()
  
for i in range(len(a)):
  a[i][1] -= 1
  count += 1
  count_n = 2
  while a[i][1] > 0:
    a[i][1] -= count_n
    if a[i][1] >= 0:
      count += 1
    count_n += 1

print(count)

Submission status: Accepted

Solution code:
n=int(input())

def f(n):
  if n==1:
    return []
  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

arr=[]
for p,e in f(n):
  for i in range(1,e+1):
    arr.append(p**i)
arr.sort()

cnt=0
for i in arr:
  if n%i==0:
    cnt+=1
    n//=i

print(cnt)

Submission status: Accepted

Solution code:
from collections import Counter
def p_factorization(n):
  p=[]
  for i in range(2,int(n**0.5)+1):
    while n%i==0:
      p.append(i)
      n//=i
  if n>1:
    p.append(n)
  return p
n=int(input())
ans=0
for pi in Counter(p_factorization(n)).items():
  x=pi[1]
  for i in range(50):
    if i*(i+1)//2<=x<(i+1)*(i+2)//2:
      ans+=i
      break
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())
c = collections.Counter(prime_factorize(N))
o = 0
for i in c:
    m = 1
    s = 1
    while(c[i] >= s):
        m += 1
        s += m
    o += m - 1
print(o)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
from collections import defaultdict
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


def prime_decomposition(n):
    i = 2
    ans = 0
    while i * i <= n:
        cnt = 1
        tmp = 0
        while n % i == 0:
            n = n // i
            tmp += 1
            if cnt == tmp:
                ans += 1
                cnt += 1
                tmp = 0
        i += 1
    if n > 1:
        ans += 1
    return ans


# 処理内容
def main():
    N = int(input())
    print(prime_decomposition(N))


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())
s=factorization(n)
ans=0
for i in s:
  k=i[0]
  l=i[1]
  p=1
  while l>=0:
    ans+=1
    l-=p
    p+=1
  ans-=1
if n==1:
  print(0)
else:
  print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    cur=0
    isum=[]
    for i in range(1,41):
        cur+=i
        isum.append(cur)
    def prime_factorize(n):
        a = dict()
        while n % 2 == 0:
            a[2]=a.get(2,0)+1
            n //= 2
        f = 3
        while f * f <= n:
            if n % f == 0:
                a[f]=a.get(f,0)+1
                n //= f
            else:
                f += 2
        if n != 1:
            a[n]=a.get(n,0)+1
        return a
    a=prime_factorize(N)
    primes=a.keys()

    
    #primes=list(primes)

    #primes=divs&primes
    #divisors = []
    ans=0

    for p in primes:
        imax=1
        imax=a[p]
        for j,ind in enumerate(isum):
            if imax<ind:
                #print(p,ind)
                ans+=j
                break

    print(ans)
    # divisors.sort()
    return 0



if __name__ == "__main__":
    main()

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


ans = 0
n = int(input())
c = collections.Counter(prime_factorize(n))
cnt = list(c.values())
# print(cnt)
for i in range(len(cnt)):
    mainasu = 1
    while True:
        if cnt[i] == 0 or cnt[i] < mainasu:
            break
        # print(cnt[i], mainasu)
        cnt[i] -= mainasu
        mainasu += 1
        ans += 1


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

arr = factorization(N)

res = 0
for a,b in arr:
    tmp = 1
    while b >= tmp:
        b = b - tmp
        tmp += 1
        res = res + 1

if N == 1:
    print(0)
else:
    print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math

###
# main
if(__name__ == '__main__'):
    # input
    n = int(input())

    # 素因数分解
    div_dict = {}
    nom = n
    while True:
        for denom in range(2,int(math.sqrt(nom)+1)):
            if nom % denom == 0:
                if denom in div_dict:
                    div_dict[denom] += 1
                else:
                    div_dict[denom] = 1
                nom /= denom
                break
        else:
            if nom in div_dict:
                div_dict[nom] += 1
            else:
                div_dict[nom] = 1
            break

    if 1 in div_dict:
        del div_dict[1]

    ans = 0
    for elem in div_dict.values():
        tgt = elem
        sub = 0
        while sub < tgt:
            ans += 1
            sub += 1
            tgt -= sub

    print(ans)

# else:
    # do nothing

Submission status: Accepted

Solution code:
def fact(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
n = int(input())
if n == 1:
    print(0)
    exit()
D = fact(n)
ans = 0
for _, d in D:
    k = int(d**.5)
    while (k+1)*(k+2)//2 <= d:
        k += 1
    ans += k
print(ans)

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_factor(n):
    factors = []
    for i in range(2, int(n**0.5)+1):
        count = 0
        while n % i == 0:
            count += 1
            n //= i
        if count != 0:
            factors.append((i, count))
    if n != 1:
        factors.append((n, 1))
    return factors

seen = set()
flag = True
ans = 0
while flag:
    flag = False
    div = make_divisors(n)
    for i in div:
        if len(prime_factor(i)) == 1 and i not in seen:
            seen.add(i)
            n /= i
            ans += 1
            flag = True
            break
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())
c = collections.Counter(prime_factorize(N))

result = 0
for i in c.values():
    temp = 0
    temp_sum = 0
    while True:
        temp += 1
        temp_sum += temp
        if temp_sum > i:
            break
    result += (temp-1)
        
print(result)

Submission status: Accepted

Solution code:
import numpy as np


def count(a):
    i = 0
    while a > 0:
        i += 1
        a -= i
        if a == 0:
            break
        if a < 0:
            i -= 1
            break
    return i


def main(N):
    num = N
    ans = 0
    A = np.zeros((1000000), np.int32)
    i = 2
    last = 0
    if N == 1:
        return 0
    while True:
        if num % i == 0:
            num = num//i
            A[i] += 1
        else:
            i += 1
            if num == 1:
                break
            if i*i > num:
                last = 1
                break
    for j in range(i):
        ans += count(A[j])
    ans += last
    return ans


N = int(input())
print(main(N))

Submission status: Accepted

Solution code:
import sys
import numpy as np
import bisect
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
# 1~1000の累計和
a = [i for i in range(1,1000)]
s = np.cumsum(a)
s_list=list(s)
N = int(read())
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

arr = factorization(N)
ans = 0
for p in arr:
  index = bisect.bisect_right(s_list, p[1])
  ans += index
print(ans)

Submission status: Accepted

Solution code:
import math
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:
    a = factorization(n)
    cnt = 0
    for i in a:
        #print(i,math.floor((math.sqrt(1+8*i[1])-1)/2))
        cnt += math.floor((math.sqrt(1+8*i[1])-1)/2)
    print(cnt)