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:
from itertools import count
# 素因数分解
def prime_factors(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            yield i
    if n > 1:
        yield n


from collections import Counter

c = Counter(prime_factors(int(input())))
res = 0
for cnt in c.values():
    for i in count(1):
        if cnt < 0:
            break
        cnt -= i
        res += 1
    res -= 1

print(res)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
from heapq import *
import sys
# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 1000000007

from fractions import *
def inverse(f):
    # return Fraction(f.denominator,f.numerator)
    return 1/f


def combmod(n, k, mod=MOD):
    ret = 1
    for i in range(n - k + 1, n + 1):
        ret *= i
        ret %= mod

    for i in range(1, k + 1):
        ret *= pow(i, mod - 2, mod)
        ret %= mod

    return ret
def bunsu(n):
    ret = []
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            tmp = 0
            while(True):
                if n % i == 0:
                    tmp += 1
                    n //= i
                else:
                    break
            ret.append((i, tmp))

    ret.append((n, 1))
    return ret

def solve():
    n = getN()
    bun = bunsu(n)
    # print(bun)
    acc = []
    tmp = 0
    for i in range(10000):
        tmp += i
        acc.append(tmp)
    ans = 0
    for b, cnt in bun:
        if b == 1:
            continue
        ans += bisect_right(acc, cnt) - 1
    print(ans)
def main():
    # n = getN()
    # for _ in range(n):
    solve()
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n=int(input())
def factorize(n):
    fct=[]
    b,e=2,0
    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
l=factorize(n)
ans=0
for i,j in l:
    ans+=int((-1+pow(1+8*j,0.5))/2)
print(ans)

Submission status: Accepted

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

n = int(input())

A = [0] * (10**6 + 5)
for i in range(2, int(n**0.5) + 1):
    while n % i == 0:
        n //= i
        A[i] += 1

if n != 1:
    A.append(1)
# print(A[:5])

ans = 0

def a(x):
    l = 0
    r = 10**6 + 5
    m = (l+r)//2
    while r-l > 1:
        if m*(m+1)//2 > x:
            r = m
        else:
            l = m
        m = (l+r)//2
    return l
A.sort(reverse=True)
for i in range(len(A)):
    if A[i] == 0:
        break
    ans += a(A[i])
print(ans)

Submission status: Accepted

Solution code:
#素因数分解して列挙する関数、約数列挙ではない！
from collections import Counter
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)
    fct = Counter(fct)
    return fct

N = int(input())
fct = factorize(N)
ans = 0
for v in fct.values():
    n = 1
    i = 0
    while n<=v:
        i += 1
        n += i+1
    ans += i
print(ans)

Submission status: Accepted

Solution code:
def main():
    from collections import Counter as ct
    n = int(input())

    def soinsuu(a):
        yy, j = [], 2
        y = yy.append
        while(a > 1):
            for i in range(j, int(a**0.5)+1):
                if a % i == 0:
                    y(i)
                    a, j = a//i, i
                    break
            else:
                y(a)
                break
        yy.sort()
        return yy
    s = ct(soinsuu(n))
    cnt = 0
    for i, j in s.items():
        for k in range(1, 10**5):
            if j >= k:
                j -= k
                cnt += 1
            else:
                break
    print(cnt)


main()

Submission status: Accepted

Solution code:
def prime_factor(n):
    factors = {}
    if n % 2 == 0:
        cnt = 0
        while n % 2 == 0:
            cnt += 1
            n //= 2
        factors[2] = cnt
    i = 3
    while i * i <= n:
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                cnt += 1
                n //= i
            factors[i] = cnt
        i += 2
    if n != 1:
        factors[n] = 1
    return factors

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

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def f(N):
    D = {}

    for i in range(2, int(N ** 0.5) + 1):
        c = 0
        while N % i == 0:
            c += 1
            N //= i
        if c > 0:
            D[i] = c
        if N == 1:
            break
            
    if N != 1:
        D[N] = 1
    return D


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

    res = 0
    for k, v in D.items():
        t = 1
        while t <= v:
            v -= t
            t += 1
        res += t - 1
    print(res)       


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import os
from collections import Counter

import math
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353
def get_factors(n):
    """
    素因数分解
    :param int n:
    :rtype: list of int
    """
    if n <= 1:
        return []

    ret = []
    while n > 2 and n % 2 == 0:
        ret.append(2)
        n //= 2
    i = 3
    while i <= math.sqrt(n):
        if n % i == 0:
            ret.append(i)
            n //= i
        else:
            i += 2
    ret.append(n)
    return ret
def get_primes(max=None, count=None):
    """
    素数列挙
    昇順にソートされています
    https://qiita.com/Ishotihadus/items/73e107271275611f05f2
    :param int max:
    :param int count:
    """
    assert max is not None or count is not None
    if count:
        raise NotImplementedError()
    if max <= 1:
        return []

    primes = [2]
    sieve = [False for _ in range(max + 1)]
    p = 3
    while p <= max:
        primes.append(p)
        sieve[p] = True
        if p <= math.sqrt(max):
            for i in range(p * (p | 1), max + 1, p * 2):
                sieve[i] = True
        while p <= max and sieve[p]:
            p += 2

    return primes

N = int(sys.stdin.buffer.readline())

# primes = get_primes(max=1000001)
# a = math.sqrt(10**12)


fs = Counter(get_factors(N))
ans = 0
for k, c in fs.items():
    m = 1
    while c >= m:
        c -= m
        m += 1
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def fctr1(n):
    f = list()
    r = int((n+1)**0.5)
    for i in range(2, r+1):
        if n % i == 0:
            c = 0
            while n % i == 0:
                c += 1
                n //= i
            f.append((i, c))
    if n > 1:
        f.append((n, 1))
    return f

n = ni()
l = fctr1(n)
res = 0
for x, c in l:
    t = 1
    while (t + 1) * (t + 2) // 2 <= c:
        t += 1
    res += t
print(res)

Submission status: Accepted

Solution code:
def bsearch(mn, mx, func):
    #func(i)=False を満たす最大のi (mn<=i<mx)
    idx = (mx + mn)//2
    while mx-mn>1:
        if func(idx):
            idx, mx = (idx + mn)//2, idx
            continue
        idx, mn = (idx + mx)//2, idx
    return idx
def prime_decomposition(n):                                                                                            
    i = 2
    table = []                
    while i * i <= n:                                       
        c = 0                          
        while n % i == 0:              
            n /= i                          
            c+=1                                 
        if c!=0:                                                     
            table.append((i,c))                  
        i += 1                                
    if n > 1:                                  
        table.append((int(n), 1))                                                                                     
    return table

N = int(input())
X = prime_decomposition(N)
R = 0
for a, b in X:
    R += bsearch(-1, 10**18, lambda x : x*(x+1)//2>b)
print(R)

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
 
YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
input=lambda: sys.stdin.readline().rstrip()


class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=0):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.size=len(ls)+1
                self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def __str__(self):
        return  str(self.edges)
 
    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        #self.st=SegTree(self.size*2-1,self.ETdepth,function=min,ide=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]

## Tested by EduFor 88 D
## https://codeforces.com/contest/1359/problem/D

class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))]):
            b=a
        return b
    
    # return boundary index of r such that func({table[i]} =< x , i in [pos,r]
    def right_bound(self,pos,x):
        k=(self.size-pos).bit_length()
        for j in range(k)[::-1]:
            nx=pos+(1<<j)
            if nx<n and self.query(pos,nx+1)<=x:
                pos+=(1<<j)
        return pos
    
    # return boundary index of l such that func({table[i]} =< x , i in [l,pos]
    def left_bound(self,pos,x):
        k=pos.bit_length()
        for j in range(k)[::-1]:
            nx=pos-(1<<j)
            if 0<=nx and self.query(nx,pos+1)<=x:
                pos-=(1<<j)
        return pos

    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)
 

## return prime factors of N as dictionary {prime p:power of p}
## within 2 sec for N = 2*10**20+7
def primeFactor(N):
    i,n=2,N
    ret={}
    d,sq=2,99
    while i<=sq:
        k=0
        while n%i==0:
            n,k,ret[i]=n//i,k+1,k+1
        if k>0 or i==97:
            sq=int(n**(1/2)+0.5)
        if i<4:
            i=i*2-1
        else:
            i,d=i+d,d^6
    if n>1:
        ret[n]=1
    return ret


## return the list of prime numbers in [2,N], using eratosthenes sieve
## within 2sec for N = 1.2*10**7
def PrimeNumSet(N):
    Max = int(N**0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList:
        if seachList[0] <= Max:
            break
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

## retrun LCM of numbers in list b
## within 2sec for no of B = 10*5  and  Bi < 10**6
def LCM(b,mo=10**9+7):
    prs=PrimeNumSet(max(b))
    M=dict(zip(prs,[0]*len(prs)))
    for i in b:
        dc=primeFactor(i)
        for j,k in dc.items():
            M[j]=max(M[j],k)
    
    r=1
    for j,k in M.items():
        if k!=0:
            r*=pow(j,k,mo)
            r%=mo
    return r

 
show_flg=False
show_flg=True
ans=0


n=I()

d=primeFactor(n)

#for i in range(n*0):
for p,j in d.items():
    #show(p,j)
    c=1
    for x in range(1,11):
        j-=x
        if j<x+1:
            break
        c+=1
    ans+=c

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter


def factorize(n):
    a = 2
    fct = []
    while a * a <= n:
        while n % a == 0:
            n //= a
            fct.append(a)
        a += 1
    if n > 1:
        fct.append(n)
    return fct


n = int(input())
c = Counter(factorize(n))
ans = 0
for v in c.values():
    t = 1
    while v >= t:
        v -= t
        t += 1
        ans += 1
print(ans)

Submission status: Accepted

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

x=int(input())

import math 
L=int(math.sqrt(x))

FACT=dict()

for i in range(2,L+2):
    while x%i==0:
        FACT[i]=FACT.get(i,0)+1
        x=x//i

if x!=1:
    FACT[x]=FACT.get(x,0)+1

ANS=0
for f in FACT.values():
    i=1
    while f:
        if f>=i:
            ANS+=1
            f-=i
            i+=1
        else:
            break
print(ANS)

Submission status: Accepted

Solution code:
n = int(input())


def p(x):
    a = []
    i = 2
    while True:
        if x % i == 0:
            j = 0
            while x % i == 0:
                x //= i
                j += 1
            a.append((i, j))
        if i * i > x:
            break
        i += 1
    if x != 1:
        a.append((x, 1))
    return a


ans = 0
for _, j in p(n):
    i = 1
    while j >= i:
        j -= i
        i += 1
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()

ans = 0
for v in range(2, n):
    if v*v > n:
        break
    e = 0
    while n % v == 0:
        n //= v
        e += 1
    if e > 0:
        for k in range(1, 10):
            if e >= k:
                e -= k
                ans += 1
            else:
                break
if n > 1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import Counter
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

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
l=prime_factorize(N)
c=Counter(l)
ans=0
for k,v in c.items():
    tmp=1
    while True:
        if tmp<=v:
            ans+=1
            v-=tmp
            tmp+=1
        else:
            break
print(ans)

Submission status: Accepted

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

x=int(input())

import math 
L=int(math.sqrt(x))

FACT=dict()

for i in range(2,L+2):
    while x%i==0:
        FACT[i]=FACT.get(i,0)+1
        x=x//i

if x!=1:
    FACT[x]=FACT.get(x,0)+1

ANS=0
for f in FACT.values():
    i=1
    while f:
        if f>=i:
            ANS+=1
            f-=i
            i+=1
        else:
            break
print(ANS)

Submission status: Runtime Error

Solution code:
import sys

N = int(input())
# a,b = map(int,sys.stdin.readline().split())
# arr= list(map(int,sys.stdin.readline().split()))

n= int(1000000000000 ** 0.5)
a = [False,False] + [True]*(n-1)
primes=[]

for i in range(2,n+1):
  if a[i]:
    primes.append(i)
    for j in range(2*i, n+1, i):
        a[j] = False
        
ans_dict = {}

# 1일 경우
if N == 1:
    print(0)
    exit()
else:
    i=0
    while N>1:
        if N%primes[i] == 0:
            N = N//primes[i]
            if primes[i] in ans_dict:
                ans_dict[primes[i]] +=1
            else:
                ans_dict[primes[i]] = 1
        else:
            i+=1
    ans = 0
    for i in ans_dict:
        m = ans_dict[i]
        j = 1
        while m-j >= 0:
            m -= j
            j+=1
            ans+=1
    print(ans)

Submission status: Runtime Error

Solution code:
	from collections import Counter
import math

NN = int(input())
c = Counter()
# create sieve
#MAXLEN = math.ceil(math.sqrt(N+1))+1
#sv = [False] * (MAXLEN+1)
#pr = list()
#for i in range(2, MAXLEN+1):
#    if sv[i]: continue
#    pr.append(i)
#    for j in range(i, MAXLEN+1, i):
#        sv[j] = True
#if N!=1: pr.append(N)
N = NN
for i in range(2, math.ceil(math.sqrt(N)+1)+1):
    while N%i == 0:
        c.update([i])
        N = N // i
if N!=1: c.update([N])
            
def R(n):
    ret = 0
    for i in range(1, n+1):
        if n>=i:
            ret += 1
            n -= i
        else:
            break
    return ret
 
ans = 0
for n in c:
    ans += R(c[n])
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter
N = int(input())
c = Counter()
# create sieve
MAXLEN = math.ceil(math.sqrt(N+1))+1
sv = [False] * (MAXLEN+1)
pr = list()
for i in range(2, MAXLEN+1):
    if sv[i]: continue
    pr.append(i)
    for j in range(i, MAXLEN+1, i):
        sv[j] = True
if N!=1: pr.append(N)

i = 2
for i in range(len(pr)):
    p = pr[i]
    while N%p == 0:
        c.update([p])
        N = N // p
            
def R(n):
    ret = 0
    for i in range(1, n+1):
        if n>=i:
            ret += 1
            n -= i
        else:
            break
    return ret
 
ans = 0
for n in c:
    ans += R(c[n])
print(ans)

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(ll i=0;i<(n);i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORC(i,a,b,c) for(ll i=(a);i<(b);i+=(c))
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define ff first
#define ss second
#define dd long double
#define mod 1000000007
const ll N=2e6+10;
ll dp[N];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    dp[0]=0;
    for(ll i=1;i<N;i++){
        dp[i]=dp[i-1]+i;
    }
    ll n;
    cin>>n;
    ll ans=0;
    for(ll i=2;i*i<=n;i++){
        ll temp=0;
        if(n%i==0){
            while(n%i==0){
                temp++;
                n/=i;
            }
            ll x=upper_bound(dp,dp+N,temp)-dp;
            x--;
            ans+=x;
        }

    }
    if(n>1){
        ans++;
    }
    cout<<ans<<endl;
}

Submission status: Runtime Error

Solution code:
import math
import numpy as np
n = int(input())
# 素因数分解
s = math.sqrt(n)
i = 2
f = np.zeros(n)
while i <= s:
    while n % i == 0:
        f[i-1] += 1
        n = n // i
    i += 1

ans = 0
for x in f:
    e = 0
    while x > 0:
        e += 1
        x -= e
    ans += e
print(ans)

Submission status: Runtime Error

Solution code:
import math

def get_prime(number):
    prime_list = []
    search_list = list(range(2,number + 1))
    while search_list[0] <= math.sqrt(number):
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        search_list = [num for num in search_list if num % head_num != 0]
    prime_list.extend(search_list)
    return prime_list

l = get_prime(10**6)
N = int(input())
ans = 0
k = 1
i = 0
while(l[i]**2 <= N):
    if N % (l[i]**k) == 0:
        N //= (l[i]**k)
        k += 1
        ans += 1
    else:
        i += 1
        k = 1
if N != 1 and l[i]!=N:
    ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
#import numpy as np
from math import sqrt, floor
def main():
    def factorization(n):
        l = []
        t = n
        for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
            if t % i == 0:
                cnt = 0
                while t % i == 0:
                    cnt += 1
                    t = t // i
                l.append([i, cnt])
        if t != 1:
            l.append([t, 1])
        if not l:
            l.append([n, 1])
        return l
    n = int(input())
    if n == 1:
        print(0)
        sys.exit()
    p = factorization(n)
    r = 0
    for pe in p[:][1]:
        r += floor(sqrt(pe*2))
    print(r)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n # 親(uf.find()で経路圧縮して根)の番号。根の場合は-(そのグループの要素数)
    def find(self,x):
        #グループの根を返す
        if self.parents[x]<0:return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        #要素x,yのグループを併合
        x,y=self.find(x),self.find(y)
        if x==y:return
        if self.parents[x]>self.parents[y]:#要素数の大きい方をxに
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x #要素数が大きい方に併合
def main():
    n, m = map(int,input().split())
    uf = UnionFind(n)
    for i in range(m):
        a, b = map(int,input().split())
        a -= 1
        b -= 1
        uf.unite(a, b)
    uf_lis = uf.parents
    ans = 0
    for p in uf_lis:
        if p < 0:
            ans = max(ans, -p)
    print(ans)


if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
d = dict()
while n%2 == 0:
  n = n//2
  if 2 in d.keys():
    d[2]+=1
  else:
    d[2] = 1
for i in range(3,int(math.sqrt(n)) + 1,2):
  while n%i == 0:
    n = n//i
    if i in d.keys():
      d[i] +=1
    else:
      d[i] = 1
def func(k):
  u = int(math.sqrt(1 + 8*k))
  return int(-1/2 + u/2)
count = 0
for j in d.keys():
  count += func(d[j])
print(count)

Submission status: Runtime Error

Solution code:
N = int(input())
pri_cnt = {}
n = N
i = 2

while i ** 2 <= N
  while n % i == 0:
    if i not in div_cnt:
      pri_cnt[i] = 1
    else:
      pri_cnt[i] += 1
    
    n = n / i

if n > 1:
  pri_cnt[N] = 1

ans = 0
for pri, cnt in pri_knt:
  count = 1
  remain = cnt
  while remain > count:
    ans += 1
    remain -= count
    count += 1
print(ans)

Submission status: Runtime Error

Solution code:
a,n=0,int(input())
for i in range(2,int(n**0.5+1)):x=0
  while(n%i==0):n//=i;x+=1
  j=1
  while(x>=j):a+=1;x-=j;j+=1
print(1 if n-1 else a)

Submission status: Runtime Error

Solution code:
import math

N = int(input())

ans = 0
check = [True for _ in range(10 ** 6)]

for p in range(2, 10 ** 6):
    if check[p] == True:
        for j in range(2, (10 ** 6) // p + 1):
            check[p * j] = False

        e = 1
        while N % (p ** e) == 0:
            N = N // (p ** e)
            e += 1
            ans += 1

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

Submission status: Runtime Error

Solution code:
import math
N = int(input())
max_D = int(1 + math.sqrt(N))
count = []
for i in range(max_D):
   if N % i == 0:
      count.append([0])
      while N%i == 0:
         N = N / i
         count[-1] += 1
   if N < i:
      break
l = len(count)
ans = 0
for i in range(l):
   E = count[i]
   j = 0
   while j * (j + 1) <= 2 * E:
      j += 1
   ans += j - 1
print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())

is_prime = [True] * (N+1)
is_prime[0] = False
is_prime[1] = False
for i in range(2, int(N**0.5) + 1):
    if not is_prime[i]:
        continue
    for j in range(i * 2, N+1, i):
        is_prime[j] = False
A=[i for i in range(N + 1) if is_prime[i]]

a=[]
for i in A:
    if N%i==0:
        a.append(i)
print(a)
ans=0
for i in a:
    e=0
    while N%i==0:
            N = N//i
            e+= 1
    x=0
    for j in range(1,100):
        x+=j
        if e>=x:
            ans+=1
        else:
            break

print(ans)

Submission status: Runtime Error

Solution code:
import math

N=int(input())

is_prime = [True] * (N+1)
is_prime[0] = False
is_prime[1] = False
for i in range(2, int(N**0.5) + 1):
    if not is_prime[i]:
        continue
    for j in range(i * 2, N+1, i):
        is_prime[j] = False
A=[i for i in range(N + 1) if is_prime[i]]


a=[]
for i in A:
    if N%i==0:
        a.append(i)

ans=0
for i in a:
    e=int(math.log(N,i))
    x=0
    for j in range(1,100):
        x+=j
        if e>=x:
            ans+=1
        else:
            break

print(ans)