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:
#!/usr/bin/env python3


def main():
    from collections import deque

    def prime_factorization_list(n: int):
        """
        入力された整数nを素因数分解し，素因数が列挙されたリストで返却
        Parameters
        ----------
        n : int
            素因数分解したい整数
        Returns
        -------
        prime_factorization_lst : lst
            [素因数]の形で素因数が列挙された素因数分解結果
        """
        fct = []  # prime factor
        b = 2     # base factor
        while b * b <= n:
            while n % b == 0:
                n //= b
                fct.append(b)
            b += 1
        if n > 1:
            fct.append(n)
        return fct

    N = int(input())

    q = deque(prime_factorization_list(N))
    memo = []
    while q:
        p = q.popleft()
        res = p
        while res in memo and q:
            can = q.popleft()
            if can == p:
                res *= can
            else:
                res = can
                break
        if res not in memo:
            memo.append(res)
    print(len(memo))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())

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

count = dict(Counter(prime_factorize(N)))

ans = 0
for c in count.values():
    k = 1
    while c >= k:
        ans += 1
        c -= k
        k += 1

print(ans)

Submission status: Accepted

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

from collections import Counter

N = int(input())
c = Counter(prime_factorize(N))

ans = 0

v = list(c.values())
l = len(v)
for i in range(l):
    for j in range(40):
        if j*(j+1)//2 <= v[i] and v[i] < (j+1)*(j+2)//2:
            ans = ans + j

print(ans)

Submission status: Accepted

Solution code:
import math
def factorization(N):
  tmp=N
  F=[]
  for i in range(2,int(math.sqrt(N))+1):
    if tmp%i==0:
      F.append(i)
      tmp//=i
    while tmp%i==0:
      tmp//=i
    if i>tmp:
      break
  if tmp!=1:
    F.append(tmp)
  return F

N=int(input())
F=factorization(N)
ans=0
for f in F:
  ff=f
  while N%ff==0:
    ans+=1
    N//=ff
    ff*=f
print(ans)

Submission status: Accepted

Solution code:
import math
def factorization(N):
  tmp=N
  F=[]
  for i in range(2,int(math.sqrt(N))+1):
    if tmp%i==0:
      F.append(i)
      tmp//=i
    while tmp%i==0:
      tmp//=i
    if i>tmp:
      break
  if tmp!=1:
    F.append(tmp)
  return F

N=int(input())
F=factorization(N)
ans=0
for f in F:
  ff=f
  while N%ff==0:
    ans+=1
    N//=ff
    ff*=f
  while N%f==0:
    N//=f
print(ans)

Submission status: Accepted

Solution code:
N = int(input())


def sb(n):
    if n == 1:
        return {1: 0}
    else:
        dic = {}
        tmp = n
        for i in range(2, int(n ** 0.5) + 1):
            if tmp % i == 0:
                dic[i] = 0
                while tmp % i == 0:
                    dic[i] += 1
                    tmp //= i

        if tmp != 1:
            dic[tmp] = 1

        if dic == {}:
            dic[n] = 1

        return dic


ans = 0

for key in sb(N):
    v = sb(N)[key]
    dv = 1
    while v - dv >= 0:
        v -= dv
        dv += 1
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def fac(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())
  l = fac(N)
  counter = 0
  if N == 1:
    print(0)
    exit()
  if len(l) == 1 and l[0][1] == 1:
    print(1)
    exit()
  for x in l:
#    print(x)
    temp = 0
    for k in range(1, 141423):
      temp += 1
      z = x[0] ** temp
#      print("z:" + str(z))
      if N/z < 1:
        break
#      print("OK")
      N = N/z
      if float(N).is_integer() == False:
        N = N * z
        break
#      print("z:" + str(z) + ", N:" + str(N))
      counter += 1
    if N <= 1:
      break
  print(counter)
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from collections import Counter

N=int(input())

if N==1:
  print(0)
  exit()
  
def factorize(n):
    out=[]
    i = 2
    while 1:
        if n%i==0:
            out.append(i)
            n //= i
        else:
            i += 1
        if n == 1:break
        if i > int(n**.5+3):
            out.append(n)
            break
    
    return out
  
c = Counter(factorize(N))

def n_unique(n):
  out = 0
  while 1:
    if out*(out+1)//2 > n:
      return out-1
    out += 1

ans = 0
for k in c.keys():
  ans += n_unique(c[k])
  
print(ans)

Submission status: Accepted

Solution code:
def factorization(n):
    if n==1:
        return [[1,1]]
    temp=n
    ans=[]
    for i in range(2, int(n**0.5+1.01)):
        if temp % i ==0:
            ct=0
            while temp % i == 0:
                temp //= i
                ct += 1
            ans.append([i, ct])
    if temp != 1:
        ans.append([temp, 1])
    return ans

N=int(input())
L=factorization(N)
if N==1:
    print(0)
    exit()
ans=0
for l in L:
    ct=0
    fac=1
    while fac<=l[1]:
        ct+=1
        fac+=ct+1
    ans+=ct
print(ans)

Submission status: Accepted

Solution code:
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

n=k()
ans=0
for i in range(2,1000010):
	power=0
	j=1
	if(n%i==0):
		while(n%i==0):
			power+=1
			n=(n//i)
		while(power>=j):
			power-=j
			j+=1
			ans+=1
if(n>1):
	ans+=1
print(ans)

Submission status: Accepted

Solution code:
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())
cnt = 0
lis = list(set(prime_factorize(n)))
for i in range(len(lis)):
    for j in range(1, 10**9):
        if n % lis[i]**j == 0:
            n /= lis[i]**j
            cnt+=1
        else:
            break
print(cnt)

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
p = make_divisors(n)
x = 0
i = 1
ans = 0
def countf(x):
    for j in range(1,x+2):
        if (1+j)*j//2 > x:
            return j - 1
while n != 1:
    if n % p[i] == 0:
        x += 1
        n = n // p[i]
    else:
        if x != 0:
            ans += countf(x)
            x = 0
        i += 1
ans += countf(x)
print(ans)

Submission status: Accepted

Solution code:
from functools import lru_cache
N = int(input())

@lru_cache(maxsize=None)
def isprime(x):
    i = 2
    while i * i <= x:
        if x % i == 0:
            return False
        i += 1
    return True

@lru_cache(maxsize=None)
def ispow(a, b):
    while a % b == 0:
        a //= b
    return a == 1

prime_cache = [2, 3]

def primeiter():
    global prime_cache
    for p in prime_cache:
        yield p
    x = prime_cache[-1] + 1
    while True:
        if isprime(x):
            prime_cache.append(x)
            yield x
        x += 1

done = set()
while N > 1:
    ds = [N]
    d = 2
    while d * d <= N:
        if N % d == 0:
            if not d in done:
                ds.append(d)
            d2 = N // d
            if d2 != d and not d2 in done:
                ds.append(d2)
        d += 1
    ds.sort()
    z = -1
    for d in ds:
        if isprime(d):
            z = d
            break
        for p in primeiter():
            if d < p:
                break
            if ispow(d, p):
                z = d
                break
        if z > 0:
            break
    if z < 0:
        break
    N //= z
    done.add(z)
print(len(done))

Submission status: Accepted

Solution code:
N = int(input())

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""

def factorization(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

#print(factorization(N))

list_a = factorization(N)
count = 0
for i in range(len(list_a)):
    num = list_a[i][1]
    cal = 1
    while(num > 0):
        
        num -= cal
        cal += 1
        if(num < 0) :
            break
        
        count += 1

        #print(num,count)

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

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

    X = factorization(N)

    ans = 0
    for x,y in X:
        ans += int((-1+(1+8*y)**(1/2))/2)

    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
import sys
import math
N = int(input())
M = N
Nso = []
Nruto = math.sqrt(N)
Nruto = math.ceil(Nruto)
for i in range(2, Nruto+1):
    while N % i == 0:
        N = N//i
        Nso.append(i)
    if N == 1:
        break
    Nruto = math.sqrt(N)
    Nruto = math.floor(Nruto)

Nso.append(N)
if 1 in Nso:
    Nso.remove(1)

if len(Nso) == 0:
    if M == 1:
        print(0)
    else:
        print(1)
    sys.exit()

ans = 0
Nso = Counter(Nso)

for i in Nso.values():
    x = math.sqrt(2*i)
    x = math.floor(x)
    for j in range(x, 0, -1):
        if j*j+j <= 2*i:
            ans += j
            break
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

def prime_fact(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())
cnt = Counter(prime_fact(n))
#print(cnt)

ans = 0
for c in cnt.values():
    tmp = 1
    while c >= tmp:
        c -= tmp
        ans += 1
        tmp += 1
        
print(ans)

Submission status: Accepted

Solution code:
P = [1 for _ in range(10**6)]
P[0]=0
P[1]=0
for i in range(2,10**3):
    for j in range(i*i,10**6,i):
        P[j] = 0
Q = []
for i in range(10**6):
    if P[i]==1:
        Q.append(i)
N = int(input())
C = {}
for q in Q:
    if N%q==0:
        cnt = 0
        while N%q==0:
            N = N//q
            cnt += 1
        C[q] = cnt
if N>1:
    C[N] = 1
cnt = 0
for q in C:
    n = C[q]
    k = 1
    while n>=(k*(k+1))//2:
        k += 1
    cnt += k-1
print(cnt)

Submission status: Accepted

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


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

ans = 0
for _, f in pf:
    x = 1
    while f >= x:
        ans += 1
        f -= x
        x += 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==[]: #1の場合はここ
        arr.append([n, 1])
 
    return arr

def count(X):
  cnt = 0
  now = 1
  while cnt+now <=X:
    cnt += now
    now += 1
  return now-1
#print(count(3))    

N = int(input())
if N == 1:
  print(0)
  exit()
A = factorization(N)
#print(A)
ans = 0
for i in range(len(A)):
  ans += count(A[i][1])
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

#factorization(24) 

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


t=int(input())
if t==1:
  print(0)
  exit()
  
ans=0
x=factorization(t)


z=[i for i in range(51)]
z=list(itertools.accumulate(z))

for i in range(len(x)):
    cnt=x[i][1]
    for j in range(len(z)):
        if z[j]>cnt:
            ans+=j-1
            break

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
dp = [True] * 10**6
count = 0
if N % 2 == 0:
    times = 0
    while(N % 2 == 0):
        times += 1
        N //= 2
    i = 1
    while(times-i >= 0):
        times -= i
        i += 1
        count += 1
f = 3
while f**2 < N:
    if N % f == 0:
        times = 0
        while(N % f == 0):
            times += 1
            N //= f
        i = 1
        while(times-i >= 0):
            times -= i
            i += 1
            count += 1
    else:
        f += 2
if N != 1:
    count += 1
print(count)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import bisect

line=[i*(i+1)//2 for i in range(10**6+1)]

N=int(input())


do=[0 for i in range(10**6+1)]

for i in range(2,int(N**0.5)+1):
    while N%i==0:
        N/=i
        do[i]+=1

ans=0 if N==1 else 1

for _,item in enumerate(do):
    index=(bisect.bisect_right(line,item))-1
    ans+=index

print(ans)

Submission status: Accepted

Solution code:
from math import sqrt


N = int(input())
ans = 0
for d in range(2, int(sqrt(N)) + 1):
    if N % d == 0:
        i = 1
        while N % d**i == 0:
            ans += 1
            N //= d**i
            i += 1
        while N % d == 0:
            N //= d

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

Submission status: Accepted

Solution code:
from math import sqrt


def eratosthenes(x):
    prime = []
    for i in range(2, int(sqrt(x)) + 1):
        if x % i == 0:
            prime.append(i)
            while x % i == 0:
                x //= i
    
    return prime


N = int(input())
prime = eratosthenes(N)
ans = 0
for x in prime:
    i = 1
    while N % x**i == 0:
        ans += 1
        N //= x**i
        i += 1
    while N % x == 0:
        N //= x

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

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    ans = 0
    for k in range(2,int(n**0.5)+1):
        if n%k==0:
            cnt,mx = 0,0
            while n%k==0:
                n = n//k
                cnt += 1
                if cnt > mx:
                    ans += 1
                    mx += 1
                    cnt = 0
    if n!=1:
        ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())

def factorize(n):
    result = []
    tmp = n

    for i in range(2, int(n**0.5)+1):
        if tmp % i == 0:
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            result.append(cnt)
         
    if tmp != 1:
        result.append(1)
    
    if len(result) == 0:
        result.append(1)
    
    return result

def nearest_sum(n):
    num_list = [1]
    
    if n <= 2:
        return 1

    i = 2
    while True:
        num_list.append(num_list[-1]+i)
        i += 1
        if num_list[-1]+i > n:
            break
    
    return i-1

if N == 1:
    print(0)
else:
    ind_list = factorize(N)

    cnt = 0
    for ind in ind_list:
        cnt += nearest_sum(ind)

    print(cnt)

Submission status: Accepted

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

def main():
    n = int(input())
    primes = factorization(n)
    count = 0
    for prime in primes:
        e = prime[1]
        k = 1
        while e >= 0:
            e -= k
            k += 1
            if e >= 0:
                count += 1
    print(count)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def factorization(num):
    arr = []
    temp = num
    for i in range(2, int(num**0.5)+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([num, 1])

    return arr

x = factorization(n)
ans = 0
for i in range(len(x)):
  x[i][1] -= 1
  ans += 1
  y = 2
  while x[i][1] > 0:
    x[i][1] -= y
    if x[i][1] >= 0:
      ans += 1
    y += 1
 
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
D = {}

for k in range(2,10**6):
  while N%k<1:
    N//=k
    D[k]=D.get(k,0)+1

a = 0
for i in D.values():
  t = 0
  c = 0
  while t+c<i:
    c+=1
    t+=c
  a+=c

print(a+(N>1))

Submission status: Accepted

Solution code:
import math 
def prime(n):
    d = {}
    if n%2==0:
        d[2]=0
    while n % 2 == 0: 
        d[2]+=1
        n = n / 2
    for i in range(3,int(math.sqrt(n))+1,2):
        if n%i==0:
            d[i]=0
        while n % i== 0: 
            d[i]+=1
            n = n / i 
    if n > 2:
        d[n]=1
    return d
def maxsum(di):
    ans = 0
    for i in di.items():
        c = 1
        x = 0
        y = i[1]
        while y-c>=0:
            #print(y, c, x)
            y-=c
            c+=1
            x+=1
        ans+=x
    return ans
di = prime(int(input()))
#print(di)
print(maxsum(di))

Submission status: Accepted

Solution code:

def prime_factorization(n):
    """do prime factorization using trial division

    Returns:
        [[prime1,numbers1],[prime2,numbers2],...]
    """
    res = []
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            cnt=0
            while n%i==0:
                cnt+=1
                n//=i
            res.append([i,cnt])
    if n!=1:
        res.append([n,1])
    return res

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

    N = int(input())
    prime_factors = prime_factorization(N)
    ans = 0
    for p in prime_factors:
        i = 1
        while i <= p[1]:
            ans += 1
            N /= p[0]**i
            p[1] -= i
            i += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def factorization(n):
  arr = []
  tmp = n
  for i in range(2, int(-(-n**0.5//1))+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 arr == [] and n != 1:
    arr.append([n, 1])
  return arr

n = int(input())
c = factorization(n)
ans = 0

for k, v in c:
  cnt = 1
  while v >= cnt:
    v -= cnt
    cnt += 1
  ans += (cnt - 1)

print(ans)

Submission status: Accepted

Solution code:
import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
import itertools
from collections import Counter

def main():
    def factorization(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
    m = [0]
    for i in range(1,10**6):
        m.append(m[i-1]+i)
    ans = 0

    n = int(input())
    k = factorization(n)
    for i,l in k:
        for u in range(len(m)):
            if l < m[u]:
                ans += u-1
                break
    print(ans)



if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

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()
c = Counter(prime_factorize(n))
ans = 0
for x in c.values():
    ans += int(-1+sqrt(1+8*x))//2
print(ans)

Submission status: Accepted

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


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

    """
    ■ 解法
    N = p^{e1} * p^{e2} * p^{e3} ...
    と因数分解できるとき、
    z = p_i^{1}, p_i^{2}, ...
    としていくのが最適なので、それを数えていく

    (例) N = 2^2 * 3^2 * 5 * 7
    のとき、
    2,3,5,7の4回割れる。（6で割る必要はない）

    ■ 計算量
    素因数分解するのに、O(√N)
    割れる回数を計算するのはたかだか素因数分解するより少ないはずなので、
    全体としてはO(√N+α)くらいでしょ（適当）
    """
    def prime_factor(n):
        """素因数分解する"""
        i = 2
        ans = {}
        while i*i <= n:
            while n%i == 0:
                if not i in ans:
                    ans[i] = 0
                ans[i] += 1
                n //= i
            i += 1
        if n != 1:
            ans[n] = 1
        return ans

    pf = prime_factor(N)

    ans = 0
    for key, value in pf.items():
        i = 1
        while value-i >= 0:
            value -= i
            ans += 1
            i += 1
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def count_(n):
    cnt = 0
    k = 1
    while(n-k >= 0):
        n = n - k
        k = k + 1
        cnt = cnt + 1
    return cnt

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

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

    s_li = (factorization(n))
    
    if s_li[0][0] == 1:
        print(0)
    else:
        ans = 0
        for s_ in s_li:
            ans = ans + count_(s_[1])
        print(ans)

Submission status: Accepted

Solution code:
ini = lambda : int(input())
inm = lambda : map(int,input().split())
inl = lambda : list(map(int,input().split()))
gcd = lambda x,y : gcd(y,x%y) if x%y else y
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 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

n = ini()
d = factorization(n)
if d[0][0] == 1:
    d = []
ans = 0
for i in range(len(d)):
    j = 1
    while d[i][1] >= j:
        d[i][1] -= j
        j += 1
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

fact={}
i = 2
while n != 1:
    if n % i == 0:
        n = n/i
        if i in fact:
            fact[i] += 1
        else:
            fact[i] = 1
    else:
        i += 1
    if i > (n**(1/2)+1):
        if n in fact:
            fact[n] += 1
        else:
            fact[n] = 1
        break

if fact == {}:
    print(0)
else:
    ans = 0
    for v in fact.values():
        #print(v)
        for i in range(1,v+1):
            if v - i >= 0:
                ans +=1
                v = v-i
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

#bisect.bisect_left(list,key)はlistのなかでkey未満の数字がいくつあるかを返す
#つまりlist[i] < x となる i の個数
#bisect.bisect_right(list, key)はlistのなかでkey以下の数字がいくつあるかを返す
#つまりlist[i] <= x となる i の個数
#これを応用することで
#len(list) - bisect.bisect_left(list,key)はlistのなかでkey以上の数字がいくつあるかを返す
#len(list) - bisect.bisect_right(list,key)はlistのなかでkeyより大きい数字がいくつあるかを返す
#これらを使うときはあらかじめlistをソートしておくこと！
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 = I()
c = factorization(n)
ans = 0
if n == 1:
  print(0)
else:
  for i in range(len(c)):
    k = c[i][1]
    for j in range(100):
        if j*(j+1)//2 > k:
            ans += j-1
            break
  print(ans)

Submission status: Accepted

Solution code:
N = int(input())

def factorize(n):#factorize(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:#2*97みたいなとき
        arr.append([temp, 1])
    if arr==[]:#n自体が素数の時
        arr.append([n, 1])
    return arr

ans = 0
for f in factorize(N):
    if f[0]==1:
        continue
    num = f[1]
    i = 1
    while num-i>=0:
        num = num - i
        ans += 1
        i += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    # 「素数の乗数」かつ「Nを割り切れる」数Zをなるべく多く選ぶ

    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)
        sys.exit()
    pfactors = factorization(n)
    r = 0
    for pfe in pfactors:
        pfe1 = pfe[1]
        t1 = 1
        while pfe1:
            if pfe1 >= t1:
                r += 1
                pfe1 -= t1
                t1 += 1
            else:
                break
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(math.ceil(n**0.5))):
        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(0)

fact_1i = factorization(n)

res = 0
for _, num in fact_1i:
    temp_num = 1
    while temp_num <= num:
        res += 1
        num -= temp_num
        temp_num += 1

print(res)

Submission status: Accepted

Solution code:
def factorization(n):
    if n < 2:
      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

n=int(input())
factor=factorization(n) 
cnt=0
for f in factor:
  c=f[1]
  for i in range(1,100):
    c-=i
    if c < 0:
      break
    cnt+=1
  
print(cnt)