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 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 main():
    N = int(input())
    
    primes = prime_factorize(N)
    u, counts = np.unique(primes, return_counts=True)
    
    ans = 0
    for c in counts:
        i = 1
        while c - i >= 0:
            c -= i
            i += 1
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())


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

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

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

    return arr


fcl = factorization(N)

result = 0
count = len(fcl)

for i in range(count):
    num = 1
    while fcl[i][1] >= num:
        fcl[i][1] = fcl[i][1] - num
        num += 1
        if fcl[i][0] > 1:
            result += 1
print(result)

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
c = collections.Counter(prime_factorize(int(input())))
# c = prime_factorize(int(input()))
a = 0
# print(c)
for i in c.values():
    # print(i)
    x = 1
    while i > 0:
        i -= x
        a += 1
        x += 1
        # print(i,x,a)
        if i < 0 :
            a -= 1

# a,z = 0,0
# for i in c:
#     if z == i :
#         z = 0
#     else :
#         z = i
#         a += 1
print(a)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

N = int(input())

#nの約数を全て求める
def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

# import numpy as np
# def make_prime(U):
#     """素数判定（エラトステネスの篩）"""
#     is_prime = np.zeros(U, np.bool)
#     is_prime[2] = 1
#     is_prime[3::2] = 1  # 3以上の奇数を一旦すべて素数としてマーク
#     M = int(U**.5) + 1
#     for p in range(3, M, 2):  # 倍数のふるい落とし
#         if is_prime[p]:
#             is_prime[p*p::p+p] = 0  # 奇数*奇数+奇数は偶数になり無駄なのでstepをp+pにして回避
#     return is_prime, is_prime.nonzero()[0]

from functools import lru_cache
#nの素数判定
@lru_cache(None)
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

ans = 0
used = []
while True:
    # print("N: {}".format(N))
    yakusu_table = divisor(N)
    sosu = []
    for yakusu in yakusu_table:
        if is_prime(yakusu):
            sosu.append(yakusu)
    
    yakusu_table.sort()
    # print("yakusu_table: {}".format(yakusu_table))
    # print("sosu: {}".format(sosu))

    is_ok = False
    for n in yakusu_table:
        if n in used:
            continue
        # print("n: {}".format(n))
        for p in sosu:
            i = 1
            z = 0
            while z <= n:
                z = p ** i
                # print("z: {}".format(z))
                if z == n:
                    # print("z!!: {}".format(z))

                    is_ok = True
                    break
                i += 1
            if is_ok:
                break
        if is_ok:
            break
    if is_ok:
        # print("z: {}".format(z))
        N = N / z
        used.append(z)
        ans += 1
        continue

    break  # Nが見つからなければ終了

print(ans)

Submission status: Accepted

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

d = factorization(n)
ins = []
for i in range(len(d)):
    for j in range(1,d[i][1]+1):
        ins.append(d[i][0]**j)
ins.sort()
cnt = 0
for z in ins:
    if n>1:
        if n%z==0:
            n = n//z
            cnt += 1
    else:
        break
print(cnt)

Submission status: Accepted

Solution code:
n=int(input())
i=1
facts = []
ans = 0
Number  =n
import math 
def factorize(n): 
    count = 0
    while ((n % 2 > 0) == False):  
        n >>= 1;  
        count += 1
    if (count > 0): 
        facts.append(2)
    for i in range(3, int(math.sqrt(n)) + 1): 
        count = 0
        while (n % i == 0):
            count += 1 
            n = int(n / i)
        if (count > 0): 
            facts.append(i)
        i += 2
    if (n > 2): 
        facts.append(n)
factorize(n)
facts = sorted(facts)
for i in range(len(facts)):
    cnt = 1
    while(n >= facts[i]**cnt):
        if(n%(facts[i]**cnt)==0):
            n//=(facts[i]**cnt)
            ans+=1
        cnt+=1
print(ans)

Submission status: Accepted

Solution code:
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 main():
    N=int(input())
    ans=0
    if N==1:
        print(ans)
        return 
    t=prime_decomposition(N)
    if len(t)==1:
        print(1)
        return 
    dic={}
    for a in t:
        if not a in dic.keys():
            dic[a]=1
            continue
        else:
            dic[a]+=1
    ans=0
    for i in dic.keys():
        num=dic[i]
        tmp=1
        c=1
        while True:
            if num >=c:
                num-=c
                c+=1
                ans+=1
            else:
                break
    print(ans)
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

def cnt(a,b):
    if a >= b:
        return cnt(a-b,b+1)
    else:
        return b - 1
    

c = collections.Counter(prime_factorize(n))
cn = 0
for i in c.values():
    cn += cnt(i,1)

print(cn)

# print(list(c.values()))

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 main():
    import sys
    N = int(input())
    fact = factorization(N)
    if fact[0][0] == 1:
        print(0)
        sys.exit()
    ans = 0
    for f, num in fact:
        for i in range(1, num+1):
            if num < i:
                break
            num -= i
            ans += 1
    print(ans)
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

N = int(input())

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

c = collections.Counter(prime_factorize(N))

ans = 0
for m in c.values():
	n = 1
	while (n*(n+1))//2 <= m:
		ans += 1
		n += 1
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right
a = int(input())

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


f = fctr1(a)
ans = 0
# for i,j in f:
#     if 

for i in range(2,45):
    l.append(i+l[-1])
# print(l)
for i,j in f:
    a = bisect_right(l,j)
    # print(a)
    ans +=a

print(ans)

Submission status: Accepted

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

import collections
 
n=int(input())
 
memo = prime(n)

c = collections.Counter(memo)

memo = sorted(c.items(), key=lambda x:-x[0])

if len(memo) == 0:
  print(0)
else: 
  ans = 0
  for i ,j in memo:
    count_kazu = 1
    while 0 <= j-count_kazu:
      j -= count_kazu
      ans += 1
      count_kazu += 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())
count = 0

soinsuu = prime_factorize(n)

soinsuu_set = set(soinsuu)
soinsuu_list = list(soinsuu_set)


for i in range(len(soinsuu_set)):
    z = soinsuu_list[i]
    while n % z == 0:
        n = n / z 
        z = z*soinsuu_list[i]
        count = count + 1
    
print(count)

Submission status: Accepted

Solution code:
N = int(input())
a = [int(0.5*i*(i+1)) for i in range(10)]
import math
res = 0
top = int(math.sqrt(N))
for i in range(2,top+1):
    count = 0
    while N%i == 0:
        N = N//i
        count += 1
    for j in range(10):
        if count < a[j]:
            res += (j-1)
            break
if N != 1:
    print(res+1)
else:
    print(res)

Submission status: Accepted

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

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 = 0
for a, b in factorization(N):
  if a == 1:
    print(0)
    exit()
  # print()
  # print((a, b))
  t = 0
  for i in range(1, 10+b):
    t += i
    if t > b:
      ans += (i-1)
      break

print(ans)

Submission status: Accepted

Solution code:
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


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

    if M != 1:
        fact.append([M, 1])

    if fact == []:
        fact.append([M, 1])

    return fact


def pert(L):
    cnt = [0 for i in range(L*2)]
    tot = 0
    i = 0
    while tot < L:
        i += 1
        tot += i
        cnt[tot] = i

    temp = 1
    for j in range(1,L+1):
        if cnt[j] == 0:
            cnt[j] += temp
        else:
            temp = 0 + cnt[j]

    return cnt


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

    fact = factorization(N,N,0,[])

    cnt = pert(40)

    M = len(fact)

    res = 0

    for i in range(M):
        now = fact[i]
        if now[0] == 1:
            continue
        res += cnt[now[1]]

    print(res)




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)
    
else:
    a = factorization(n)
    result = 0
    
    for i in range(len(a)):
        j = 1
        while(1):
            a[i][1] -= j
            if a[i][1] < 0:
                break
            result += 1
            j += 1
            
    print(result)

Submission status: Accepted

Solution code:
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 arr == []:
        arr.append([n, 1])
    return arr


def cal(num):
    D = 1 + 8 * num
    return (-1 + math.sqrt(D))/2


N = int(input())
n_f = factorization(N)
if N == 1:
    print(0)
    exit()
ans = 0
for i in n_f:
    ans += math.floor(cal(i[1]))
print(ans)

Submission status: Accepted

Solution code:
from math import sqrt
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:
    ans = 0
else:
    A = factorization(N)
    B = []
    for a in A:
        B.append(a[1])
        ans = 0
    for b in B:
        n = int((-1 + sqrt(8*b + 1)) / 2)
        ans += n
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
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

L = factorization(n)
#print(L)
ans = 0
#print(len(L))
for i in range(len(L)):
    b = L[i][1]
    s = 0
    for j in range(1,b+1):
        s += j
        if s == b:
            ans += j
            break
        elif s > b:
            ans += j-1
            break
    #print(b, s)
if n == 1:
    ans = 0
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)
    exit()
L = factorization(N)
res = 0
for l in L:
    a = int(l[1])
    count = 1
    while True:
        if a >= count:
            a -= count
            res += 1
            count += 1
        else:
            break
print(res)

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.values():
    tmp = i
    cnt=0
    val=1
    while True:
        tmp = tmp-val
        val+=1

        if tmp > 0:
            cnt+=1
        
        if tmp == 0:
            cnt+=1
            ans+=cnt
            break
        
        if tmp < 0:
            ans+=cnt
            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


def main():
    n = int(input())
    if n == 1:
        print(0)
    else:
        x = factorization(n)
        #print(x)
        ans = 0
        for lis in x:
            num = lis[1]
            tmp = 0
            while num > tmp:
                tmp += 1
                ans += 1
                num -= tmp
        print(ans)

    
    
 
 
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# https://qiita.com/snow67675476/items/e87ddb9285e27ea555f8

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 resolve():
  N = int(input())
  prime_factors = factorization(N)
  tri_dict = {
    1 :  1,
    2 :  1,
    3 :  2,
    4 :  2,
    5 :  2,
    6 :  3,
    7 :  3,
    8 :  3,
    9 :  3,
    10 :  4,
    11 :  4,
    12 :  4,
    13 :  4,
    14 :  4,
    15 :  5,
    16 :  5,
    17 :  5,
    18 :  5,
    19 :  5,
    20 :  5,
    21 :  6,
    22 :  6,
    23 :  6,
    24 :  6,
    25 :  6,
    26 :  6,
    27 :  6,
    28 :  7,
    29 :  7,
    30 :  7,
    31 :  7,
    32 :  7,
    33 :  7,
    34 :  7,
    35 :  7,
    36 :  8,
    37 :  8,
    38 :  8,
    39 :  8,
    40 :  8,
    41 :  8,
    42 :  8,
    43 :  8,
    44 :  8,
    45 :  9,
    46 :  9,
    47 :  9,
    48 :  9,
    49 :  9,
    50 :  9,
    51 :  9,
    52 :  9,
    53 :  9,
    54 :  9,
    55 :  9,
    56 :  9,
    57 :  9,
    58 :  9,
    59 :  9
  }
  result = 0

  for prime_factor in prime_factors:
    if prime_factor[0] > 1:
      result += tri_dict[prime_factor[1]]

  print(result)


if __name__ == "__main__":
    resolve()

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))
d = list(c.items())
cnt = 0
for i in range(len(d)):
  for j in range(10 ** 8):
    if j * (j + 1) <= 2 * d[i][1] < (j + 1) * (j + 2):
      cnt += j
      break
    else:
      pass
print(cnt)

Submission status: Accepted

Solution code:
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(n)
  return table


a = prime_decomposition(n)


d ={}
for i in a:
    if i not in d:
        d[i] = int(0)
    d[i] += 1
    


c = list(d.values())


l =[]
for i in c:
    e = 1
    count = 1
    f = 0
    while i >=  e:
        count += 1
        f += 1 
        e = e + count
    l.append(f)
    
print(sum(l))

Submission status: Accepted

Solution code:
import math 

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

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

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

    return arr

factorization(24) 
if __name__ == "__main__":
    s = int(input())
    a = factorization(s) #行列
    if a[0][0] == 1:
        print(0)
    else:
        an = 0
        for list1 in a: #[3,6]の形
            z = 0
            check = 0
            count = list1[1]
            while True:
                z += 1
                count -= z
                if count < 0:
                    break
                check += 1
            an += check
        print(an)

Submission status: Accepted

Solution code:

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

N = int(input())

c = collections.Counter(prime_factorize(N))
sum = 0

for i in c.keys():
    a = c[i]
    for n in range(c[i]):
        if a<n+1:
            break
        else:
            a-=n+1
            sum+=1

print(sum)

Submission status: Accepted

Solution code:
import sys


def I(): return int(sys.stdin.buffer.readline())


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()
if n == 1:
    print(0)
    sys.exit()

# 素因数分解
facts = factorization(n)
# print(facts)
ans = 0
for prime, e in facts:
    # print(f'{prime=}')
    i = 1
    while e > 0:
        # print(f'while内 {e=}, {i=}, {ans=}')
        if e - i < 0:
            break
        e -= i
        ans += 1
        # print(f'加算{ans=}')
        i += 1
print(ans)

Submission status: Accepted

Solution code:
import bisect
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) 
#print(arr)
ans = 0

tosa = [0 for _ in range(1000)]
for i in range(1000):
    tosa[i] = int(i*(i+1)/2)

#print(tosa)
for s in arr:
    if(s[0] == 1):
        continue
    num = s[1]
    cnt = bisect.bisect_right(tosa, num) - 1
    #print(cnt)
    ans += cnt

print(ans)

Submission status: Accepted

Solution code:
import collections


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 solve():
    N = int(input())
    if N == 1:
        return 0
    D = factorization(N)
    R = primes()

    result = 0
    for d in D:
        result += R[d[1]]

    return result


def primes():
    R = [0 for i in range(41)]
    for i in range(40, 0, -1):
        tmp_R = R[:]
        for j in range(i, 41):
            tmp_R[j] = max(R[j], R[j - i] + 1)
        R = tmp_R

    return R


if __name__ == "__main__":
    print(solve())

Submission status: Accepted

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


np = factorization(n)


def cont(x):
    a = 0
    c = 0
    while True:
        c += 1
        a += c

        if x >= a and x < a + c + 1:
            break

    return c


ans = 0
for i in np:
    if i[0] == 1:
        continue
    else:
        # print(cont(i[1]))
        ans += cont(i[1])
# print(np)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())

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 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 is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1

k=make_divisors(n)
c=0
for i in range(len(k)):
    if i==0:pass
    else:
        l1=factorization(k[i])
        seigo=is_prime(l1[0][0])
        if len(l1)==1 and seigo==True and n%k[i]==0:
            n//=k[i]
            c+=1
        
print(c)

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


a = int(input().split()[0])
prime_res = prime_factorize(a)

prime_dict = {}
for prime_i in prime_res:
    if prime_i not in prime_dict:
        prime_dict[prime_i] = 1
    else:
        prime_dict[prime_i] += 1

res = 0
for key in prime_dict:
    base = 1
    while True:
        if prime_dict[key] < base:
            break
        else:
            prime_dict[key] -= base
            base += 1
            res += 1

print(res)

Submission status: Accepted

Solution code:
import math
def c(x):
    global yaku
    now=x
    for i in range(2,int(math.sqrt(now))+1):
        while now%i==0:
            if i in sosu.keys():
                v=sosu[i]
                sosu[i]=v+1
            else:
                sosu[i]=1
            now=now//i
            yaku+=1
    if(now!=1):
        sosu[now]=1
        yaku+=1
def d(x):
    global ans
    q=x
    cur=1
    while(q>0):
        q=q-cur
        if q>=0:
            ans+=1
        cur+=1
    
n=int(input())
sosu={}
yaku=0
c(n)
if n==1:
    print(0)
else:
    if(yaku==1):
        print(1)
    else:
        ans=0
        #print(sosu)
        for i in sosu.keys():
            d(sosu[i])
        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



fac = factorization(n)
ans = 0
if n == 1:
    print(0)
else:
    for i in fac:
        tem = 1
        while tem*(tem+1)//2 < i[1]:
            if i[1] >= (tem+1)*(tem+2)//2:
                tem += 1
            else:
                break
        ans += tem

    print(ans)

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

count = 0

for k in arr:
    if k[0] == 1:
        continue
    now = 1
    while k[1] >= now:
        k[1] -= now
        now += 1
        count += 1

print(count)

Submission status: Accepted

Solution code:
import numpy as np
import math
import collections
import bisect
from decimal 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 collections.Counter(a)


N = int(input())
ruisekiwa = [0]
for i in range(1, 50):
    ruisekiwa.append(i + ruisekiwa[i - 1])
PF = prime_factorize(N)

ans = 0
for v in PF.values():
    ans += bisect.bisect_right(ruisekiwa, v) - 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

facts = Counter(prime_factorize(N))
cnt = 0

def pattern_cnt(n):
  res = 0
  cur = 1
  while n - cur >= 0:
    n -= cur
    res += 1
    cur += 1
  return res

for k in facts:
  cnt += pattern_cnt(facts[k])
  #print(k, cnt)

print(cnt)

Submission status: Accepted

Solution code:
N = int(input())


#整数N以下の素数を#素因数分解
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 = prime_factorize(N)
b = set(a)

dic = {}
for i in b:
    n = 0
    while True:
        n += 1
        if a == []:
            break
        a.pop(0)
        if a == []:
            break
        if a[0] != i:
            break
    dic[i] = n


an = 0
for k, v in dic.items():
    num = int((-1+(1+8*v)**(1/2))/2)
    an += num

print(an)

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

a = factorization(n)
cnt = 0

for i in range(len(a)):
    b = a[i]
    c = b[1]
    for j in range(1, 100):
        c = c - j
        cnt += 1
        if c <= j:
            break

print(cnt)