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 numpy as np


def solve(n):
    # primes
    primes = np.ones(10 ** 6 + 1, dtype=int)
    primes[:2] = 0
    for p in range(2, 10 ** 6 + 1):
        if primes[p]:
            primes[p * p::p] = 0

    res = 0
    for p in range(10 ** 6 + 1):
        if primes[p] and n % p == 0:
            c = 0
            while n % p == 0:
                n = n // p
                c += 1
            d = 1
            while c >= d:
                c -= d
                res += 1
                d += 1
    if n > 1:
        res += 1

    return res


def main():
    n = int(input())
    res = solve(n)
    print(res)


def test():
    assert solve(24) == 3
    assert solve(1) == 0
    assert solve(64) == 3
    # assert solve(1000000007) == 1
    # assert solve(997764507000) == 7


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

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

N = int(input())
ans = 0
done = set()
# print(prime_factors(N))
for k,v in prime_factors(N).items():
    p = 0
    while v > 0:
        p += 1
        v -= 1
        if not pow(k, p) in done:
            ans += 1
            done.add(pow(k, p))
            p = 0
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
if N==1:
    print(0)
else:
    def factorization(n):
        arr = []
        temp = n
        for i in range(2, int(-(-n**0.5//1))+1):
            if temp%i==0:
                cnt=0
                while temp%i==0:
                    cnt+=1
                    temp //= i
                arr.append([i, cnt])

        if temp!=1:
            arr.append([temp, 1])

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

        return arr

    A=factorization(N)
    total=0
    for i in range(len(A)):
        for j in range(1,10**6):
            if j*(j+1)//2<=A[i][1]<(j+1)*(j+2)//2:
                total+=j
                break
    print(total)

Submission status: Accepted

Solution code:
N = int(input())
if N == 1:
    print(0)
    quit()
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 sousa(n):
    x = [1,3,6,10,15,21,28,36,45,55]
    for i in range(10):
        a = x[i]
        if n < a:
            return i
            break
bunkai = factorization(N)
ans = 0
for i in range(len(bunkai)):
    c = bunkai[i][1]
    ans += sousa(c)
print(ans)

Submission status: Accepted

Solution code:
#! /usr/bin/env python3
# -*- coding:utf-8 -*-

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 f(N):
    if N == 1: return 0
    fact = factorization(N)
    ans = 0
    count_list = [0]
    for i in range(100):
        for j in range(i+2):
            count_list.append(i+1)
    for k, count in fact:
        ans += count_list[count]
    return ans

def main():
    N = int(input())
    print(f(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())

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

s = factorization(n)
ans = 0

for i in s:
    cnt = 1
    tmp = i[1]
    while tmp > 0:
        tmp -= cnt
        if tmp >= 0:
            ans += 1
        cnt += 1

print(ans)

Submission status: Accepted

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

n = int(input())
nn = factorization(n)
#print(nn)
ans = 0

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

for i in range(len(nn)):
    ans += 1
    cnt = 1
    dif = 2
    cnt += dif
    while cnt <= nn[i][1]:
        ans += 1
        dif += 1
        cnt += dif
print(ans)

Submission status: Accepted

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))

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 = ii()
A = factorization(n)
#print(A)
ans = 0
if n == 1:
    print(0)
else:
    for i in A:
        num = i[1]
        cnt = 0
        while  num-cnt > 0:
            cnt += 1
            num -= cnt
        ans += cnt
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


def factorize(n):
    facts = defaultdict(int)
    while n % 2 == 0:
        n //= 2
        facts[2] += 1
    m = 3
    while m * m <= n:
        while n % m == 0:
            facts[m] += 1
            n //= m
        m += 2
    if 1 < n:
        facts[n] += 1
    return facts


N = int(input())

ans = 0
facts = factorize(N)
for num in facts.values():
    for i in range(1, num + 1):
        if i <= num:
            num -= i
            ans += 1
        else:
            break
print(ans)

Submission status: Accepted

Solution code:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

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

    return arr

N = int(input())
if N==1:
    print(0)
elif N==2:
    print(1)
else:
    f = factorization(N)
    #print(f)
    
    ans=0
    for elem in f:
        t = elem[1]
        for i in range(1,N):
            if (i*(i+1)//2)>t:
                break
        #print(t,i)
        ans += (i-1)
        
    print(ans)

Submission status: Accepted

Solution code:
import collections
import math

N = int(input())

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


def aaa(num):
    tmp = (math.sqrt(8*num+1)-1)/2
    t = math.floor(tmp)
    return t


c = collections.Counter(prime_decomposition(N))


ans = 0
d = list(c.values())

for i in range(len(d)):
    if d[i] == 1:
        ans += 1
    else:
        ans += aaa(d[i])
        
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

ps = prime_fact(n)
current = 0
num = 0
tmp_c = 0
cnt = 0
if ps:
  for i in range(len(ps)):
    if ps[i] != current:
      num = 2
      tmp_c = 0
      cnt += 1
      current = ps[i]
    else:
      tmp_c += 1
      if tmp_c == num:
        cnt += 1
        tmp_c = 0
        num += 1
  print(cnt)
else:
  print(0)

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)
ans = 0
if arr==[[1,1]]:
    print(0)
else:
    suretsu = [1,3,6,10,15,21,28,36,45]
    import bisect
    for i in arr:
        ans += bisect.bisect_right(suretsu,i[1])
    print(ans)

Submission status: Accepted

Solution code:
import bisect

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

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

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

    return arr


l = factorization(N)

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


for p in l:
    n = bisect.bisect_right(a, p[1]) - 1
    ans += n

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

D = defaultdict(int)

N = int(input())

x = N
y = 2
while y*y <= x:
    while x % y == 0:
        D[y] += 1
        x //= y
    y += 1
if x > 1:
    D[x] += 1

res = 0
for k, v in D.items():
    i = 1
    c = 0
    v -= 1
    while v >= 0:
        c += 1
        i += 1
        v -= i
    res += c

print(res)

Submission status: Accepted

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
def prime_factor(n):
    """Return a list of prime factorization numbers of n"""
    res = []
    for i in range(2,int(n**0.5)+1):
        while n%i==0: res.append(i); n //= i
    if n != 1: res.append(n)
    return res
from collections import Counter
#======================================================#
def main():
    n = II()
    p = prime_factor(n)
    c = Counter(p)
    cnt = 0
    for ci in c.values():
        t = ci
        i = 1
        while t >= i:
            t -= i
            i += 1
            cnt += 1
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    d = {}
    for i in range(2,int(math.sqrt(N))+1):
        while N % i == 0:
            if i in d:
                d[i] += 1
            else:
                d[i] = 1
            N //= i
    if N > 1:
        d[N] = 1

    ans = 0
    for i in d.values():
        n = int((-1+math.sqrt(1+4*2*i))/2)
        ans += n
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

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

Counter=[1]
for i in range(2,10):
  Counter.append(Counter[-1]+i)


ans = 0
tmp = 0
for i in range(len(Fact)):
  tmp = Fact[i][1]
  ans += bisect_right(Counter, tmp)

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import count


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 index_counter(e):
    c = 0
    for i in count(start=1):
        e -= i
        if e >= 0:
            c += 1
        else:
            break
    return c


N = int(input())
prime_factors = Counter(prime_factorize(N))
ans = 0
for key, value in prime_factors.items():
    ans += index_counter(value)
print(ans)

Submission status: Accepted

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

P = prime_factorize(n)

import collections
C = collections.Counter(P)


L = [0]
for i in range(1, 1000):
    L.append(L[-1] + i)

import bisect


ans = 0

for k, v in C.items():
    i = bisect.bisect(L, v) - 1
    ans += i
print(ans)

Submission status: Accepted

Solution code:
from math import ceil, sqrt

n = int(input())

p_map= {}
for i in range(2, ceil(sqrt(n))+1):
    while n % i == 0:
        n /= i
        if i not in p_map:
            p_map[i] = 1
        else:
            p_map[i] += 1
if n > 2:
    p_map[n] = 1

res = 0
for i, v in p_map.items():
    prev = 0
    for i in range(1, 41):
        current = prev+1
        if v < current:
            break
        v -= current
        res += 1
        prev = current
print(res)

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

if(N == 1):
  print(0)
else:
  result = factorization(N)
  ans = 0
  for i in range(len(result)):
    count = 1
    temp = 0
    while(result[i][1] - count >= 0):
      result[i][1] -= count
      count += 1
      temp += 1
    ans += temp
  print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

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=I()
u=prime_factorize(n)
c=Counter(u)
ans=0
lis=[0 for i in range(15)]
for i in range(14):
    lis[i+1]=lis[i]+i+1
#print(lis)
mans=[]
for x in c.keys():
    y=c[x]
    man=-1
    for i in range(15):
        if y>=lis[i]:
            man+=1
    mans.append(man)
print(sum(mans))

Submission status: Accepted

Solution code:
import sys
from collections import Counter

input = sys.stdin.readline


def calc_prime_factors(n, count=False):
    """Trial division"""
    factors = []
    # factor: 2
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    # factor: 3, 5, 7, 11, ...
    f = 3
    while f ** 2 <= n:
        if n % f == 0:
            factors.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        factors.append(n)
    if count:
        factors = Counter(factors).items()
    return factors


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

    factors = calc_prime_factors(N, count=True)
    ans = 0
    for _, count in factors:
        n = 1
        while True:
            if n * (n + 1) // 2 <= count:
                n += 1
            else:
                break
        ans += (n - 1)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import math

n = int(input())

primes = defaultdict(int)
t = n
for i in range(2, int(math.sqrt(n)) + 1):
    while t % i == 0:
        primes[i] += 1
        t //= i
if t != 1:
    primes[t] += 1

count = 0
for cn in primes.values():
    count += int((-1 + math.sqrt(1 + 8 * cn)) / 2)

print(count)

Submission status: Accepted

Solution code:
N = int(input())

def prime_factorization(n):
    dct = {}
    tmp = n
    for i in range(2, int(n**0.5)+1):
        if tmp == 1:
            break
        if tmp % i == 0:
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            dct[i] = cnt
    if tmp != 1:
        dct[tmp] = 1
    if len(dct) == 0:
        dct[n] = 1

    return dct

if N == 1:
    print(0)
else:
    pf = prime_factorization(N)
    ans = 0
    for p in pf:
        num = pf[p]
        k = 1
        while num >= k:
            ans += 1
            num -= k
            k += 1
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
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
c = collections.Counter(prime_factorize(N))
ans = 0
for i in c.values():
    k = i
    j = 1
    while(k>=j):
        k = k-j
        j += 1
        ans += 1
print(ans)

Submission status: Accepted

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

n = int(input())
ass = prime_factor(n)
cnt = {}
for x in ass:
    if x not in cnt:
        cnt[x] = 1
    else:
        cnt[x] += 1
#print(cnt)
ass = set(ass)
ans = 0
for x in ass:
    i = 1
    c = cnt[x]
    while c >= i:
        c -= i
        ans += 1
        i += 1

print(ans)
#print(ass)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
if n==1:
    print(0)
    quit()
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
tmp=factorization(n)
# print(tmp)
lst=list(accumulate(range(1,1000)))
# print(lst)
ans=0
for i in range(len(tmp)):
    so,num=tmp[i]
    ans+=bisect.bisect_right(lst,num)
    # print(so,num)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())

def prime_pair(n):
    pairs = {}
    tmp = n
    for i in range(2, n):
        if i * i > n:
            break
        if tmp % i != 0:
            continue
        ex = 0
        while tmp % i == 0:
            ex += 1
            tmp /= i
        pairs[i] = ex
    if tmp != 1:
        pairs[int(tmp)] = 1
    return pairs

pp_n = prime_pair(N)
res = 0
for k in pp_n.keys():
    val = pp_n[k]
    power = 1
    while val >= power:
        val -= power
        power += 1
        res += 1

print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict

D = defaultdict(int)
N = int(input())

a = 2
while a * a <= N:
    if N % a:
        a += 1
    else:
        N //= a
        D[a] += 1

if N != 1:
    D[N] += 1

ans = 0
for k,v in D.items():
    i = 0
    while i*(i+1) <= v * 2:
        i += 1
    ans += i-1

print(ans)

Submission status: Accepted

Solution code:
import math

def isprime(n):
    for k in range(2,math.floor(math.sqrt(n))+1):
        if n%k == 0:
            return False
    return True

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

P = [N]
for k in range(2,math.floor(math.sqrt(N))+1):
    if N % k == 0:
        P.append(k)
        P.append(N//k)
P = sorted(P)
Q = []
for k in range(len(P)):
    if isprime(P[k]) == True:
        temp = 0
        while N%P[k] == 0:
            N //= P[k]
            temp += 1
        Q.append(temp)

ans = 0
for e in Q:
    if e > 0:
        t = 0
        for k in range(1,100):
            t += k
            if t <= e:
                ans += 1
            else:
                break
print(ans)

Submission status: Accepted

Solution code:
#import math

n=int(input())

ans=0
p=2
for p in range(2, int((n+0.5)**0.5)+1):
    if n%p==0:
        cnt=0
        while n%p==0:
            cnt+=1
            n//=p
        k=1
        while cnt>=k:
            cnt-=k
            k+=1
            ans+=1

if n>1:
    ans+=1

print(ans)

Submission status: Accepted

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


N = int(input())
primes = factorization(N)
ans = 0
for p in primes:
    num = p[1]
    for i in range(1, N):
        if num >= i:
            num -= i
            ans += 1
        else:
            break
print(ans)

Submission status: Accepted

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

def prime_factorization(n):
    '''
    Trial division.
    Input: 
        n : a positive integer
    Output:
        a dictionary of #(each prime factors) of n,
    '''
    result = []
    app = result.append
    if n < 2: return Counter()
    while n % 2 == 0:
        app(2)
        n //= 2
    p = 3
    while p*p <= n:
        while n % p == 0:
            app(p)
            n //= p
        p += 2
    if n > 1: app(n)
    return Counter(result)

cumsum = list(accumulate(range(1, 50)))

N = int(input())
factors = prime_factorization(N)
ans = 0
for _, n in factors.items():
    ans += bisect_right(cumsum, n)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(200000)
from collections import defaultdict


def read():
    N = int(input().strip())
    return N,


def sieve(n):
    """
    n以下の素数を昇順に列挙する
    """
    is_prime = [True for i in range(n+1)]
    primes = []
    for i in range(2, n+1):
        if is_prime[i]:
            primes.append(i)
            for j in range(i+i, n+1, i):
                is_prime[j] = False
    return primes


def prime_factorization(n, primes):
    """
    nの素因数分解を求める
    """
    prime_factors = defaultdict(int)
    if n < 2:
        return prime_factors
    for p in primes:
        if p * p > n:
            break
        while n % p == 0:
            prime_factors[p] += 1
            n //= p
    if n > 1:
        prime_factors[n] = 1
    return prime_factors


def solve(N, INF = 10**8):
    primes = sieve(10**6+1)
    factors = prime_factorization(N, primes)
    ans = 0
    for c in factors.values():
        m = 0
        for i in range(1, 63):
            if m + i <= c:
                m += i
                ans += 1
            else:
                break
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache
 
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())
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=read()
ls=factorization(n)
res=0
#print(ls)
for num in ls:
    k=num[1]
    if num[0]==1:
      break
    i=1
    while True:
        k-=i
        if k>=0:
            res+=1
        else:break
        i+=1
print(res)

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())
a = factorization(n)
ans = 0
for i in a:
    t = i[1]
    b = 1
    while (b*(b+1))//2  <= t:
        b += 1
    ans += b-1
if n==1:
    print(0)
    exit()
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())

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

def unique_count(n):
    res = 0
    while n>=0:
        res += 1
        n -= res
    # print(res)
    return res-1

Cnt = Counter(prime_decomposition(N))
# print(Cnt)
ans = 0
for c in Cnt.values():
    ans += unique_count(c)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

import math
def div(m):
    d = {}
    temp = int(math.sqrt(m))+1
    for i in range(2, temp):
        while m%i== 0:
            m //= i
            if i in d:
                d[i] += 1
            else:
                d[i] = 1
    if d == {}:
        d[m] = 1
    else:
        if m in d:
            d[m] += 1
        elif m != 1:
            d[m] =1
    return d

d = div(n)
#print(d)
ans = 0
for k, v in d.items():
    temp = 0
    i = 1
    while True:
        temp += i
        if temp > v:
            break
        i += 1
    #print(k, v, temp, i)
    ans += (i-1)
print(ans)

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

ans = 0
for v in c.values():
    n = 1
    while n <= v:
        v -= n
        ans += 1
        n+=1
print(ans)

Submission status: Accepted

Solution code:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

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

    return arr

  
def count(n):
  ans = ((1 + 8 * n) ** (1 / 2) - 1) // 2
  return int(ans)
  
N = int(input())
ans = 0
X = factorization(N)
if N == 1:
  print("0")
  quit()
for i in range(len(X)):
  ans += count(X[i][1])
  
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from queue import deque
readline = sys.stdin.buffer.readline
#sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def prime_factors(n):
    ret = dict()

    i = 2
    tmp = n
    while i * i <= n:
        e = 0
        while tmp % i == 0:
            tmp //= i
            e += 1
        if e > 0:
            ret[i] = e

        i += 1

    if tmp > 1:
        ret[tmp] = 1

    return ret


def main():
    n = gete(int)
    d = prime_factors(n)

    ans = 0
    for p in d:
        e = d[p]
        tmp = e
        for i in range(1, e + 1):
            tmp -= i
            if tmp < 0: break
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

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
primes = prime_factorize(int(input()))
prime_set = set(primes)
count = 0
for p in prime_set:
    cnt = primes.count(p)
    count += 1
    i = 2
    while cnt>i:
        cnt -= i
        count += 1
        i = i + 1
print(count)