Problem:


Score : 400 points

Problem Statement

Given is a positive integer N. Consider repeatedly applying the operation below on N:

First, choose a positive integer z satisfying all of the conditions below:

z can be represented as z=p^e, where p is a prime number and e is a positive integer;

z divides N;

z is different from all integers chosen in previous operations.

Then, replace N with N/z.

Find the maximum number of times the operation can be applied.

Constraints

All values in input are integers.

1 \leq N \leq 10^{12}

Input

Input is given from Standard Input in the following format:

N

Output

Print the maximum number of times the operation can be applied.

Sample Input 1

24

Sample Output 1

3

We can apply the operation three times by, for example, making the following choices:

Choose z=2 (=2^1). (Now we have N=12.)

Choose z=3 (=3^1). (Now we have N=4.)

Choose z=4 (=2^2). (Now we have N=1.)

Sample Input 2

1

Sample Output 2

0

We cannot apply the operation at all.

Sample Input 3

64

Sample Output 3

3

We can apply the operation three times by, for example, making the following choices:

Choose z=2 (=2^1). (Now we have N=32.)

Choose z=4 (=2^2). (Now we have N=8.)

Choose z=8 (=2^3). (Now we have N=1.)

Sample Input 4

1000000007

Sample Output 4

1

We can apply the operation once by, for example, making the following choice:

z=1000000007 (=1000000007^1). (Now we have N=1.)

Sample Input 5

997764507000

Sample Output 5

7



Sample input:
24


Sample output:
3

Submission status: Accepted

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

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

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

    return arr

p = [1,1,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,5,5,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,9,10,10,10,10,10,10,10,10,10,10,10,11,11,11,11,11,11,11,11,11,11,11,11,12,12,12,12,12,12,12,12,12,12,12,12,12,13,13,13,13,13,13,13,13,13,13,13,13,13,13,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15]

n = int(input())
if n == 1:
    print(0)
else:
    ans = 0
    for j in factorization(n):
        ans += p[j[1]-1]

    print(ans)

Submission status: Accepted

Solution code:
n = int(input())


def prime_factorize(n):
    map = {}
    while n % 2 == 0:
        if 2 in map:
            map[2]+=1
        else:
            map[2]=1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            if f in map:
                map[f]+=1
            else:
                map[f]=1
            n //= f
        else:
            f += 2
    if n != 1:
        if n in map:
            map[n]+=1
        else:
            map[n]=1
    return map

map = prime_factorize(n)

count = 0
for key in map:
    k = 1
    while map[key] >= k:
        map[key]-=k
        count+=1
        k+=1
print(count)

Submission status: Accepted

Solution code:
n = int(input())

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

if n == 1:
	arr = []

nums = []
for i in arr:
	nums.append(i[0])

for f in arr:
	i = 2
	while f[1]>i:
		nums.append(f[0]**i)
		f[1] -= i
		i += 1

nums.sort()

ln = len(nums)

cnt = 0
ans = 0

while n >= 1 and cnt<ln:
	if n%nums[cnt] == 0:
		n /= nums[cnt]
		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())
L = factorization(N) 
#print(L)
counter = 0
for i in L:
    if i[0] != 1:
        counter += (-1+(1+8*i[1])**0.5)//2
print(int(counter))

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 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()
    divisors.remove(1)
    return divisors
N=int(input())
l=make_divisors(N)
count=0

for i in l:
  if 1==len(factorization(i)) and N%i==0:
    count+=1
    N/=i

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

P = factorization(N)

flag = 0

for i in range(len(P)):
  for j in range(40):
    P[i][1] = P[i][1] - (j + 1)
    if P[i][1] >= 0:
      flag += 1
    else:
      break
if N == 1:
  print(0)
else:
  print(flag)

Submission status: Accepted

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

cnt = 0
for c in l.values():
    cnt += int((-1 +((1-4*(-2*c))**0.5))/2)
print(cnt)

Submission status: Accepted

Solution code:
import collections

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

if __name__ == "__main__":
    n = int(input())
    lst = collections.Counter(prime_factorize(n))

    #primes = lst.keys()
    counts = lst.values()

    ans = 0
    for c in counts:
        num = c
        cnt = 1
        while True:
            num -= cnt
            if num < 0:
                break
            ans += 1
            cnt += 1
    
    print(ans)

Submission status: Accepted

Solution code:
def SieveOfEratosthenes(n):
    sn = int(n ** 0.5)
    res = []
    check = [False] * (sn + 1)
    for i in range(2, sn+1):
        if check[i]:
            continue
        res.append(i)
        for j in range(2 * i, sn+1, i):
            check[j] = True
    return res

def trialDivision(n):
    res = dict()
    pn = SieveOfEratosthenes(n)
    for p in pn:
        while n % p == 0:
            res[p] = res.get(p, 0) + 1
            n //= p
    if n > 1:
        res[n] = 1
    return res

N = int(input())
fn = trialDivision(N)
ans = 0
for n in fn.values():
    res = 0
    s = 0
    for i in range(1, n+1):
        if s + i > n:
            break
        s += i
        res += 1
    ans += res

print(ans)

Submission status: Accepted

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

arr = factorization(N)

min_nums = [1]
num_lists = [1]
num_dic = {1: 1}

ans = 0

for Z in arr:
    o = Z[1]
    for i, num in enumerate(num_lists):
        if num > o:
            ans += num_dic[num_lists[i-1]]
            break
    if num <= o:
        o = o - num
        _ans = len(min_nums)
        n = min_nums[-1]+1
        while o >= n:
            o -= n
            min_nums.append(n)
            _ans += 1
            num_lists.append(n+num_lists[-1])
            num_dic[num_lists[-1]] =  _ans
            n += 1
        ans += _ans

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
a = []
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

prime_factorize(N, a)
ans = 0
if len(a) > 1:
    before = a[0]
    kosuu = 1
    for i in range(1, len(a)):
        tmp = a[i]
        if tmp == before:
            kosuu += 1
        else:
            ini = 1
            while kosuu - ini >= 0:
                kosuu = kosuu - ini
                ini += 1
                ans += 1
            before = tmp
            kosuu = 1
        ini = 1
    while kosuu - ini >= 0:
        kosuu = kosuu - ini
        ini += 1
        ans += 1
if len(a) == 1:
    ans = 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())


# 素因数分解する関数
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

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

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

    return arr


fct=factorization(n)


cnt = 0
tmp = 0
ma = 0
for t in fct:
    if t[0] == 1:
        break
    
    tmp = t[1]
    ma = 1
    while tmp >= ma:
        tmp -= ma
        ma += 1
        cnt += 1


print(cnt)

Submission status: Accepted

Solution code:
n = int(input())

pf={}
m=n
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1

ans = 0

for i in pf.items():
    m = i[1]

    a = 1
    cnt = 1

    while a <= m:
        cnt += 1
        a += cnt
    
    cnt -= 1

    ans += cnt

print(ans)

Submission status: Accepted

Solution code:
import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
   
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n=int(input())

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

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

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

    return arr
    
a=factorization(n)
le=len(a)
cnt=0
b=0
for i in range(le):
	b=1
	while a[i][1]>=b: 
		a[i][1]-=b
		b+=1
		cnt+=1

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

Submission status: Accepted

Solution code:
import collections

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

def tmp(m):
  c = 0
  s = 0
  for i in range(1,m+1):
    if s + i > m:
      return c
    c = c + 1
    s = s + i
  
  return c

def main():
  N = int(input())
  c = collections.Counter(prime_factorize(N))
  multupliyer_list = c.values()
  count = 0
  for m in multupliyer_list:
    t = tmp(m)
    count = count + t

  print(count)


if __name__ == "__main__":
  main()

Submission status: Accepted

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



c = collections.Counter(prime_factorize(n))
ans = 0
for i in c:
    nn = c[i]
    st = 1
    while nn>=st:
        nn=nn-st
        ans += 1
        st=st+1

print(ans)

Submission status: Accepted

Solution code:
import math

def factrize(x):
    f = {}
    if x == 1:
        return f
    tmp = x
    i = 2
    while i**2 <= tmp:
        cnt = 0
        while tmp % i == 0:
            cnt += 1
            tmp = tmp//i
        if cnt > 0:
            f[i] = cnt
        i += 1
    if tmp != 1 or f == {}:
        f[tmp] = 1
    return f
n = int(input())
m = factrize(n)
l = []
for i in m.values():
  l.append(i)
ans=[]
for i in l:
  for j in range(1, 40):
    if i - j >= 0:
      i -= j
      continue
    else:
      ans.append(j-1)
      break
print(sum(ans))

Submission status: Accepted

Solution code:
import sys

n = int(input())
ans = 0
if n == 1:
    print(0)
    sys.exit()
ma = int(n**(0.5))+1
for i in range(2,ma):
    j = 1
    k = 0
    while n%i == 0:
        k += 1
        n //= i
    else:
        while j <=k:
            ans += 1
            k -= j
            j += 1
if n != 1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import *
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

a = Counter(prime_factorize(int(input())))
count=0
for s in a.values():
    for m in range(40):
        if (m+1)*(m+2)/2>s:
            count+=m
            break
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

#main
n = int(input())
B=[0]
for i in range(1,11):
    for j in range(i+1):
        B.append(i)

A=factorization(n)

ans=0
for i in A:
    ans+=B[i[1]]

if n==1:
    ans=0

print(ans)

Submission status: Accepted

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


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

d = collections.Counter(prime_factorize(n))

r = 0
for v in d.values():
    _v = v
    e = 1
    while _v > 0:
        _v -= e
        if _v >= 0:
            r += 1
        e += 1

print(r)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi
from copy import deepcopy

# If you use recursive call, uncomment this code
#sys.setrecursionlimit(10**6)

def divider(N):
    threshold = int(sqrt(N))
    res = defaultdict(int)
    for n in range(2,threshold+1):
        while N % n == 0:
            res[n] += 1
            N //= n
    if N > 1:
        res[N] += 1
    return res

def main():
    N = int(input())
    res = divider(N)
    #print(res)
    ans = 0
    for k,v in res.items():
        i = 1
        while True:
            if v < i:
                break
            v -= i
            i += 1
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections

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

def resolve():
    N = int(input())
    factor_list = prime_factorize(N)
    if len(factor_list) == 0:
        print(0)
        return
    factor_count = collections.Counter(factor_list)
    div_count = 0
    for factor, count in factor_count.items():
        e = 1
        while True:
            if count >= e:
                N = N // (factor**e)
                div_count += 1
                count -= e
                e += 1
            else:
                break
    print(div_count)

resolve()

Submission status: Accepted

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

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

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

    return arr

A = factorization(N)
c = 0
for i in range(len(A)):
    j = 2
    while True:
        f = j * (j - 1) / 2
        if A[i][1] < f:
            c += j - 2
            break
        j += 1
print(c)

Submission status: Accepted

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


def readstr():
    return input().strip()


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)

    divisors.sort()
    return divisors


def is_prime(q, k=50):
    q = abs(q)
    # 計算するまでもなく判定できるものははじく
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False

    # n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    # 判定をk回繰り返す
    for i in range(k):
        a = random.randint(1, q - 1)
        t = d
        y = pow(a, t, q)
        # [0,s-1]の範囲すべてをチェック
        while t != q - 1 and y != 1 and y != q - 1:
            y = pow(y, 2, q)
            t <<= 1
        if y != q - 1 and t & 1 == 0:
            return False
    return True


def main():
    N = readint()
    if N == 1:
        print(0)
        exit()
    d = make_divisors(N)
    ans = 0
    # print(d)
    p = [i for i in d if is_prime(i)]
    # print(p)
    for i in range(1, 10):
        for z in [j ** i for j in p]:
            if z == 1:
                continue
            if not N % z:
                N //= z
                ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def check_prime(k):
    '''
    素数の時1、合成数の時0を返す
    '''
    if k == 1:return 0
    num = int(k ** 0.5 // 1)
    for i in range(2, num + 1):
        if k % i == 0:return 0
    return 1
n = int(input())
if n == 1:
    print(0)
    exit()

num = int(n ** 0.5 // 1)
check = []
for i in range(2, num + 2):
    if n % i == 0:
        cnt = 0
        while True:
            if n % i != 0:break
            n = n // i
            if n > num and check_prime(n):
                check.append([n, 1])
            cnt += 1
        check.append([i, cnt])
ans = 0

for num, cnt in check:

    temp = 1
    while True:
        #print(ans, temp, cnt)
        if cnt >= temp:
            ans += 1
            cnt -= temp
            temp += 1
        else:break

print(ans if len(check) != 0 else 1)

Submission status: Accepted

Solution code:
from collections import Counter 
from collections import defaultdict
from collections import deque
from functools import reduce
import math
import itertools
import heapq
import numpy as np
import bisect
import sys
#import sympy
sys.setrecursionlimit(10**6)


def bfs(s,n,node):
    #頂点が探索済みかどうかのチェック配列
    check=[False for _ in range(n)]
    check[s]=True
    #次見る頂点を格納するキュー
    queue=deque([s])
    visited_num=1

    #問題固有の配列
    #color_check=[[True for _ in range(l)] for _ in range(n)]
    color=[-1 for _ in range(n)]
    color[s]=0
    
    while visited_num<n:
        #グラフが全連結ではない場合
        if len(queue)==0:
            #空配列を返す
            #現状までの計算済み配列を返してもいいと思う
            return color

        now_vertex=queue.popleft()
        #インデックスがない場合は
        for next_vertex in node[now_vertex]:


            if check[next_vertex]==True:
                continue

            queue.append(next_vertex)
            check[next_vertex]=True

            #問題固有の計算
            color[next_vertex]=color[now_vertex]+1
            visited_num+=1

    return color

#n=int(input())z
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
ceil=lambda x,y: (x+y-1)//y
input_list = lambda : list(map(int,input().split()))



n=int(input())
#n,m=input_list()
#a=input_list()
#a=input().split()
#n=int(a[0])
#m=float(a[1])
#print(math.floor(n*m))
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

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
div=make_divisors(n)
#print(div)
ind=0
ans=0
while(n!=1 and n>=div[ind]):
    ind+=1
    check=Counter(prime_factorize(div[ind]))
    if (len(check.keys()))>1:
        continue
    #print("pass")    
    if n%div[ind]==0:
        ans+=1
        n=n//div[ind]

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

def isit(N):

    A = make_divisors(N)
    A.pop(0)

    #print(A)

    num = len(A)
    i=num-1

    for n in reversed(A):
        mul = False
        for m in A:
            if n%m == 0 and n!=m:
                mul = True
                break
        if mul == True:
            A.pop(i)
    #        print(A.pop(i))
    #        print(A)
        i -= 1
    #print(A)

    if len(A) == 1:
        return True
    else:
        return False

A =  make_divisors(N)
A.pop(0)

num = 0

for m in A:
    if isit(m) == True:
        if N%m == 0:
            N = N//m
            #print(m)
            num += 1
        if N<m:
            break

print(num)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
import math
import bisect


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 not arr:
        arr.append([n, 1])

    return arr


def solve(n):
    if n == 1:
        return 0
    ans = 0
    acc = list(accumulate(list(range(int(math.log2(n) + 2)))))
    arr = factorization(n)
    for e in arr:
        ans += bisect.bisect_right(acc, e[1]) - 1
    return ans


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

    print(solve(n))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def trial_division(n):
    if n < 2:
        return []

    prime_factors = []

    for i in range(2, int(n**0.5)+1):
        # nがi（の累乗）で割り切れるかを調べる
        while n % i == 0:
            # nがiで割り切れる場合、iを素因数としてリストに追加する
            prime_factors.append(i)
            # nをiで割った商で更新しておく
            n //= i
    # nの平方根より大きい素因数が存在する場合
    if n > 1:
        prime_factors.append(n)

    return prime_factors

n = int(input())
import collections
l = trial_division(n)
c = collections.Counter(l)

count = 0
for v in c.values():
  n = 1
  while v >= n*(n+1)/2:
    count += 1
    n +=1
    
print(count)

Submission status: Accepted

Solution code:
def era(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = num**0.5

    for serial in range(3, num, 2):

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial): 
            input_list[s] = False

N=int(input())
if N<25:
    Prime=[2,3,5]
else:
    input_list=era(int(N**0.5)+1)
    Prime=[i for i, b in enumerate(input_list) if b == True]

Fac={}
for p in Prime:
    while N%p==0:
        N//=p
        if p in Fac:
            Fac[p]+=1
        else:
            Fac[p]=1
    if N==1:
        break
if N!=1:
    Fac[N]=1
ans=0

for k in Fac:
    nec=1
    while True:
        if Fac[k]>=nec:
            ans+=1
            Fac[k]-=nec
            nec+=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

import sys
N = int(input())
count = 0
if N == 1:
    print(count)
    sys.exit()

for i in factorization(N):
    a = 1
    while i[1] >= a*(a+1)/2:
        a += 1
        count += 1
        
print(count)

Submission status: Accepted

Solution code:
import math


def is_prime(n):
    if n == 1:
        return False

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

    return True


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 = int(input())
divisors = make_divisors(N)

cnt = 0
for d in divisors:
    if d == 1:
        continue

    if N < d:
        break

    if is_prime(d):
        dd = d
        while True:
            if N < dd:
                break
            if N % dd == 0:
                N //= dd
                cnt += 1
                dd *= d
            else:
                break
print(cnt)

Submission status: Accepted

Solution code:
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
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 = INT()
counter = list(dict(Counter(prime_factorize(n))).values())

res = 0
for ele in counter:
    res += int(math.sqrt(2*ele+0.25)-0.5)
print(res)

Submission status: Accepted

Solution code:
import math

n = int(input())

factors = []

m2 = 0
while n > 1 and n % 2 == 0:
	m2 += 1
	n //= 2
if m2:
	factors.append((2,m2))

m3 = 0
while n > 1 and n % 3 == 0:
	m3 += 1
	n //= 3
if m3:
	factors.append((3,m3))

i = 5
l = int(math.sqrt(n)) + 1

while n > 1 and i < l:
	if n % i == 0:
		m = 0
		while n > 1 and n%i == 0:
			m += 1
			n //= i
		factors.append((i, m))
	i += 2

if n != 1:
	factors.append((n,1))

ans = 0

for _, m in factors:
	count = 0
	s = 0
	while s < m:
		count += 1
		s += count
	ans += count if s == m else count - 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())
#print(factorization(N))

ans = factorization(N)
#print(ans)
if ans == [[1,1]]:
    print(0)
else:
    sum = 0
    for i in range(len(ans)):
        n = 1
        while ans[i][1] >= n:
            ans[i][1] -= n
            sum += 1
            n += 1
    print(sum)

Submission status: Accepted

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

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

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

    return arr

n = int(input())
count = 0
primelist = factorization(n)
#print(primelist)

if primelist[0][0]==1:
  print(0)
else:
  for i in range(len(primelist)):
    for j in range(40):
      if j*(j+1)/2 > primelist[i][1]:
        count += (j-1)
        break
  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())
used = list()
count = 0
while N > 1:
    operated = False
    factor = factorization(N)
    candidate = list()
    for f in factor:
        base = f[0]
        for e in range(1, f[1]+1):
            candidate.append(pow(base, e))
    candidate.sort()

    for z in candidate:
        if z in used or N % z != 0:
            continue
        count += 1
        operated = True
        used.append(z)
        N //= z

    if not operated:
        break

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

A=factorization(N)
ans=0
for a in A:
    n=a[1]#これが素因数の数
    i=1
    while n-i>=0 :
        ans+=1
        n-=i
        i+=1
print(ans)

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N = ri()

def get_divisors(n):
    divs = []
    for i in range(2, int(n**0.5)+1):
        c = 0
        while n % i == 0:
            n = n // i
            c += 1
        if c > 0:
            divs.append((i, c))
    if n > 1:
        divs.append((n, 1))
    return divs

divs = get_divisors(N)

ans = 0
for p, c in divs:
	i = 1
	while c >= i:
		c -= i
		ans += 1
		i += 1

print(ans)