Problem:


Score : 400 points

Problem Statement

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

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

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

z divides N;

z is different from all integers chosen in previous operations.

Then, replace N with N/z.

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

Constraints

All values in input are integers.

1 \leq N \leq 10^{12}

Input

Input is given from Standard Input in the following format:

N

Output

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

Sample Input 1

24

Sample Output 1

3

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

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

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

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

Sample Input 2

1

Sample Output 2

0

We cannot apply the operation at all.

Sample Input 3

64

Sample Output 3

3

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

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

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

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

Sample Input 4

1000000007

Sample Output 4

1

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

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

Sample Input 5

997764507000

Sample Output 5

7



Sample input:
24


Sample output:
3

Submission status: Accepted

Solution code:
from bisect import bisect
from itertools import accumulate as acc
N = int(input())

d = dict()
for i in range(2, int(N**(1/2))+2):
    if N%i == 0:
        d[i] = 0
    while N%i == 0:
        d[i] += 1
        N //= i
if N != 1:
    d[N] = 1

a = list(acc(range(1, 100)))

r = 0
for v in d.values():
    r += bisect(a, v)

print(r)

Submission status: Accepted

Solution code:
import bisect
from collections import defaultdict
from typing import Dict, List


def prime_factorization(n: int) -> Dict[int, int]:
    factorized = defaultdict(int)
    if n == 1:
        return factorized

    if n in {2, 3}:
        factorized[n] += 1
        return factorized

    i: int = 2
    while i * i <= n:
        if n % i == 0:
            factorized[i] += 1
            n = n // i
        else:
            i += 1
    if n != 1:
        factorized[n] += 1
    return factorized


def main():
    n: int = int(input())
    factorized: Dict[int, int] = prime_factorization(n)
    # print(factorized)
    # largest k that satisfies 0.5 * k * (k * 1) <= count
    # 1 + 2 + ... + k
    # 1 + 2 + ... + k + alpha -> 1 + 2 + ... + (k + alpha)
    # count -> k
    # 1 -> 1
    # 2 -> 1
    # 3 -> 2
    ans: int = 0
    thresholds: List[int] = [k * (k + 1) // 2 for k in range(1, 14 * 10 ** 5)]
    for v in factorized.values():
        thresh: int = bisect.bisect_right(thresholds, v)
        ans += thresh
        # print(thresh)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math

N=int(input())

criterion=math.sqrt(N)
divisor=[]
for i in range(2,int(criterion+1)):
    if N%i==0:
        times=0
        while True:
            times+=1
            N//=i
            if (N%i)!=0:
                divisor.append((i,times))
                break

if N>criterion:
    divisor.append((N,1))

ans=0
for i in range(len(divisor)):
    num=1
    times=1
    while True:
        num+=1
        if  divisor[i][1]<times+num:
            ans+=num-1
            break
        times+=num

print(ans)

Submission status: Accepted

Solution code:

from collections import defaultdict


def prime_factor(n):
    d = defaultdict(int)
    for i in range(2, n + 1):
        if i * i > n:
            break

        while n % i == 0:
            d[i] += 1
            n //= i

    if n != 1:
        d[n] += 1

    return d


N = int(input())
d = prime_factor(N)
ans = 0
for v in d.values():
    i = 1
    cur = 1
    cnt = 0
    while cur <= v:
        cnt += 1
        i += 1
        cur += i
    ans += cnt

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# 整数の入力
n = int(input())

#素因数分解
def PrimeFactorization(n):
    ret = []
    for i in range(2, int(n ** 0.5)+1):
        if n % i != 0:
            continue
        
        exp = 0
        while n % i == 0:
            exp += 1
            ret.append(i**exp)
            n //= i

    if n != 1:
        ret.append(n)

    ret.sort()
    return ret

a = PrimeFactorization(n)
ans = 0
for i in a:
    if n % i == 0:
        ans += 1
        n //= i

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
ans=0

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


#12だったら[[2,2],[3,1]]みたいな、[素因数、次数]みたいに格納したい

import sys
import math
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#######ここから天ぷら########
from math import sqrt
def eratosu(n):
  if not isinstance(n,int):
    raise TypeError("nがint型になってねえぞ")
  if n<2:
    raise ValueError('nが2よりちっちぇえぞ')
  prime = []
  limit = sqrt(n)
  data = [i+1 for i in range(1, n)]  #2,3,4,...,n
  while True:
    p = data[0]
    if limit <= p:
        return prime + data
    prime.append(p)
    data = [e  for e in data if e % p != 0]
def bunkai(n):
    if n==2:
        return [[2,1]]
    if n==3:
        return [[3,1]]
    ans=[]
    temp=n
    #そんな早くしなくてよかったり、何回もするわけじゃないなら、
    #for i in range(2,int(sqrt(n))+1): とかで
    primelist=eratosu( int(sqrt(n)) )
    for i in primelist:
        if temp % i ==0:
            ji=0
            while temp%i==0:
                ji+=1
                temp//=i
            ans.append([i,ji])
    if ans==[]:return([[n,1]])  #素数のとき
    if temp!=1:
        ans.append([temp,1])  #4*5882353とか
    return ans

a=bunkai(n)

ans=0
import bisect as bi
p=[1,3,6,10,15,21,28,36,45,55]
for l in a:
  q=l[1]
  ans+=bi.bisect_right(p,q)
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

candidates = factorization(N)
# print(candidates)
li = []

for item in candidates:

    for i in range(item[1]):
        li.append(item[0]**(i+1))

li.sort()
# print(li)

cnt = 0
for i in range(len(li)):
    if N % li[i] == 0:
        N /= li[i]
        cnt += 1

print(cnt)

Submission status: Accepted

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


n = int(input())
ans = 0
r = f(n)
for p,k in r:
    tmp = 0
    cur = 1
    while(k>=cur):
        tmp += 1
        k -= cur
        cur += 1
    ans += tmp
print(ans)

Submission status: Accepted

Solution code:
a=int(input())
d=0
for i in range(2,int(a**0.5)+1):
    c=0
    while a%i==0:
        c+=1
        a//=i
    for i in range(1,60):
        if c>=i:
            c-=i
            d+=1
        else:
            break
    if a==1:
        break
if a!=1:
    d+=1
print(d)

Submission status: Accepted

Solution code:
n = int(input())

def factorize(x):
    res = {}
    p = 2
    while p * p <= x:
        if x % p != 0: 
            p += 1
            continue
        cnt = 0
        while x % p == 0:
            x //= p
            cnt += 1
        res[p] = cnt
        p += 1
    if x != 1:
        res[x] = 1
    return res

f = factorize(n)

ans = 0
for pe in f.items():
    for e in range(1, pe[1] + 1):
        z = pe[0] ** e
        if n % z == 0:
            n //= z
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
A = [a for a in range(1,41)]
A = list(accumulate(A))

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

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

def inc(n):
  ans = 0
  i = 1
  while True:
    if n - i >= 0:
      n -= i
      i += 1
      ans += 1
    else:
      break
  return ans

import collections

n = int(input())

c = collections.Counter(prime_factorize(n))

num = c.values()

ans = 0

for i in num:
  ans += inc(i)

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 f(n):
  for i in range(50,-1,-1):
    if n>=(i*(i+1)//2):
      return i
      break
n=int(input())
cnt=0
alist=factorization(n)
for i in range(len(alist)):
  cnt+=f(alist[i][1])
if n==1:
  cnt=0
print(cnt)

Submission status: Accepted

Solution code:
from itertools import accumulate
A = [a for a in range(1,41)]
A = list(accumulate(A))

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

Submission status: Accepted

Solution code:
import collections
N=int(input())
if N==1:
    print(0)
    exit()
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)) 
s=list(set(prime_factorize(N)))
ans=0
def a(n):
    return (1/2)*n*(n+1)
def f(n):
    ans=0
    x=1
    while n>=a(x):
        x+=1
        ans+=1
    return ans
for i in s:
    x=c[i]
    ans+=f(x)
print(ans)

Submission status: Accepted

Solution code:
import sys
#import string
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18
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():
    x = int(stdin.readline().rstrip())
    p = factorization(x)
    num = []
    if x == 1:
        print(0)
        exit()
    for i in p:
        for j in range(i[1]):
            if x%(i[0] ** (j+1)) == 0:
                num.append(i[0] ** (j+1))
                x = x/(i[0] ** (j+1))
            else:
                break
    print(len(num))
    exit()



if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import math
 
N = int(input())
Prime = []
ans = 0
 
def func(n):
    while n % 2 == 0:
        n = n // 2
        Prime.append(2)
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        while n % i == 0:
            n = n //i
            Prime.append(i)
    if n > 2:
        Prime.append(n)
 
func(N)
 
for i in set(Prime):
    c = i
    while N % c == 0:
        N = N // c
        ans += 1
        c = c * i
 
print(ans)

Submission status: Accepted

Solution code:
import logging
logging.basicConfig(level=logging.DEBUG, format=' %(asctime)s - %(levelname)s - %(message)s')
#logging.debug("デバッグスタート")  #

n = int(input())
a = []
b = 1
while n % 2**b == 0:
    a.append(2**b)
    n /= 2**b
#    logging.debug("n = {},b = {}".format(n,2 ** b))  #
    b += 1

while n % 2 == 0:
    n /= 2

f = 3
b = 1
while f * f <= n:
    if n % f**b == 0:
        a.append(f**b)
        n /= f**b
        b += 1
    else:
        while n % f == 0:
            n /= f
        f += 2
        b = 1
#    logging.debug("n = {},f = {},f**b = {}".format(n, f, f**b))  #
if n != 1:
    a.append(n)

#print(a)
print(len(set(a)))
#logging.debug("デバッグ終了")#

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

def triangle(n):
  i=1
  while i*(i+1)/2<=n:
    i+=1
  return i-1
  
import collections
prime_prod=collections.Counter(prime_factorize(int(input())))
print(sum([triangle(i) for i in list(prime_prod.values())]))

Submission status: Accepted

Solution code:
from math import sqrt

n = int(input())

i = 2

c = []

while i*i <= n:
    j = 0
    while n%i == 0:
        j += 1
        n //= i   
    else:
        if j != 0:
            c.append(j)
    i += 1
if n > 1:
    c.append(1)
             
d = 0        
if c == []:
    print(d)
else:
    for k in c:
        d += int((sqrt(1 + 8*k)-1)/2)
    print(d)

Submission status: Accepted

Solution code:
n=int(input())
from collections import defaultdict
def factorization(n):
    arr = defaultdict(int)
    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[i]+=cnt

    if temp!=1:
        arr[temp]=1

    if arr==[]:
        arr[n]=1

    return arr
l=factorization(n)
ans=0
for v in l.values():
    i=1
    while i<=v:
        ans+=1
        v-=i
        i+=1
print(ans)

Submission status: Accepted

Solution code:
import math

N = int(input())

A_max = int(math.sqrt(N) + 1)
A = list(range(2, A_max))

prime_check = [0] * (A_max + 1)
multi_list = []

def multi_x(X, n):
    i = 1
    result = 0
    while X % (n**i) == 0:
        result = i
        i += 1
    return result

for a in A:
    if prime_check[a] == 0:
        i = 2
        x = multi_x(N, a)
        if x != 0:
            multi_list.append(x)
            N = N // a**x
        while a * i <= A_max:
            prime_check[a * i] = 1
            i += 1

if N > A_max:
    ans = 1
else:
    ans = 0

for m in multi_list:
    i = 1
    buf = m
    while buf >= i:
        buf -= i
        i += 1
        ans += 1

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
if N==1:
    print(0)
else:
    arr=factorization(N)
    count=0
    for i in range(len(arr)):
        c=math.floor((-1+math.sqrt(1+8*arr[i][1]))/2)
        count+=c
    print(count)

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

def inc(n):
  ans = 0
  i = 1
  while True:
    if n - i >= 0:
      n -= i
      i += 1
      ans += 1
    else:
      break
  return ans

import collections

n = int(input())

c = collections.Counter(prime_factorize(n))

num = c.values()

ans = 0

for i in num:
  ans += inc(i)

print(ans)

Submission status: Accepted

Solution code:
# ABC169 D

import math


def factorization(n):
    """
    素因数分解した結果を[(要素, 数)]のリストで返す
    """
    arr = []
    temp = n
    for i in range(2, int(math.ceil(n ** 0.5))):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

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

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

    return arr


n = int(input())

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

fact_li = factorization(n)

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

print(res)

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


primes = factorization(N)

count = 0
for p in primes:
    c = 0
    t = 0
    for i in range(1, 10 ** 9):
        c += i
        t += 1
        if c > p[1]:
            count += t - 1
            break
        elif c == p[1]:
            count += t
            break

print(count)

Submission status: Accepted

Solution code:
n=int(input())
p=[]

for i in range(2,int(-(-n**0.5//1))+1) :
    if n%i==0 :
        count=0
        while n%i==0 :
            count+=1
            n//=i
        p.append([i,count])

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


ans=0
for i in range(len(p)) :
    m=p[i][1]
    j=1
    while m>0 :
        m-=j
        if m>=0 :
            j+=1
            ans+=1

print(ans)

Submission status: Accepted

Solution code:
import math
N = int(input())

list = []


while(N%2==0):
  list.append(2)
  N = N//2
  
f = 3

while(f*f <= N):
  if(N%f==0):
    list.append(f)
    N = N // f
  else:
    f += 2
if(N!=1):
  list.append(N)
count = 0
while(len(list)>0):
  k=0
  #mu = []
  max_num = list.count(list[0])
  num = 1
  while(num <= max_num):
    count += 1
    max_num -= num
    num += 1
  for i in range(list.count(list[k])):
    list.remove(list[k])
  
print(count)

Submission status: Accepted

Solution code:
n = int(input())
N = n
arr = [n]
while n % 2 == 0:
    arr.append(2)
    n //= 2
f = 3
while f * f <= n:
    if n % f == 0:
        arr.append(f)
        n //= f
    else:
        f += 2
if n != 1:
    arr.append(n)


arr.sort()

import collections
c = collections.Counter(arr)
k = list(c.keys())
v = list(c.values())

x = []
for i in range(len(k)):
    for p in range(1,v[i]+1):
        x.append(k[i]**p)

x.sort()

ans = 0
n = N
while n != 1 and len(x) != 0:
    if n % x[0] == 0:
        n //= x[0]
        x.pop(0)
        ans += 1
    else:
        x.pop(0)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
ans = 0
d = 2
while d*d <= N:
  e = 0
  while N%d == 0:
    e+=1
    N//=d
  i=1
  while i<=e:
    ans+=1
    e-=i
    i+=1
  d+=1

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

Submission status: Accepted

Solution code:
N = int(input())
number = N
List = [0 for i in range(1000000)]
answer = 0

def cul(x):
    number = 1
    while x >= (number+2)*(number + 1)//2:
        number += 1
    return number

i = 2
while number > 1:
    while number % i == 0:
        number //= i
        List[i] += 1
    i +=1

    if i == 1000001:
        answer = 1
        break

for x in List:
    if x == 0:
        continue
    else:
        answer += cul(x)

print(answer)

Submission status: Accepted

Solution code:
N = int(input())


def factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors


p = list(set(factors(N)))
ans = 0
e = 0
i = 0
for i in range(len(p)):
    e = 1
    while 1 < N:
        z = p[i] ** e
        if N % z == 0:
            N //= z
            ans += 1
        else:
            break
        e += 1
print(ans)

Submission status: Accepted

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


class Eratos:
  def __init__(self, n):

    self.is_prime = [True]*(n+1)
    self.is_prime[0] = False
    self.is_prime[1] = False
    self.primes = []

    # for i in range(2, int(math.sqrt(n))+1):
    for i in range(2, n):
      if self.is_prime[i]:
        self.primes.append(i)
        j = i + i
        while j <= n:
          self.is_prime[j] = False
          j += i

  def all(self):
    return self.primes


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

  MAX = 10**6
  primes = Eratos(MAX).all()

  cnt = 0
  for p in primes:
    if N < p: break
    e = 1
    while not(N % p**e):
      N //= (p**e)
      cnt += 1
      e += 1

  if N > MAX:
    for p in primes:
      while N % p == 0:
        N //= p
    if N > MAX:
      print(cnt+1)
    else:
      print(cnt)
  else:
    print(cnt)


if(__name__ == '__main__'):
  main()

Submission status: Accepted

Solution code:
N = int(input())
n = min(N, 10**6)
is_Prime = [True] * (n + 1)
is_Prime[0] = False
is_Prime[1] = False
for i in range(2, int(n**(1/2)+1)):
    for j in range(2*i, n+1, i):
        if j % i == 0:
            is_Prime[j] = False
P = [i for i in range(n+1) if is_Prime[i]]

count = 0
for p in P:
    count_p = 0
    while N % p == 0:
        count_p += 1
        N /= p
    count += int((-1+(1+8*count_p)**(1/2))/2)
    if p == P[-1] and N != 1:
        count += 1
print(count)

Submission status: Accepted

Solution code:
n = int(input())

from collections import Counter

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=list(Counter(prime_factorize(n)).values())

if len(c)==0:
	print(0)
	exit()
ans=0

for i in c:
	for j in range(1,10**7):
		i-=j
		if i>=0:
			ans+=1
		else:
			break

print(ans)

Submission status: Accepted

Solution code:
from math import sqrt
from math import ceil
n = int(input())
if n == 1:
    print (0)
    exit()
isP = [True] * (int(ceil(sqrt(n))))
op = 0
i = 2
n2 = n
for i in range(2, int(ceil(sqrt(n)))):
    if isP[i]:
        for j in range(2*i, int(ceil(sqrt(n))), i):
            isP[j] = False
for i in range(2, int(ceil(sqrt(n)))):
    if isP[i] and n % i == 0:
        j = i
        while n % j == 0:
            n //= j
            j *= i
            op += 1
if n > 1 and n > int(ceil(sqrt(n2))):
    op += 1

print (op)

Submission status: Accepted

Solution code:
def p_fact(n):
  m=n
  i=2
  a=[]
  while n>1:
    if i>m**.5:
      a+=[n]
      break
    if n%i==0:
      n//=i
      a+=[i]
    else:i+=1
  return a
a=p_fact(int(input()))
d={}
for i in a:
  if d.get(i):d[i]+=1
  else:d[i]=1
ans=0
for i in d:
  j=1
  while d[i]-j>=0:
    ans+=1
    d[i]-=j
    j+=1
print(ans)

Submission status: Accepted

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

N = int(input())
if N == 1:
    print(0)
else:
    A = prime_decomposition(N)

    c = collections.Counter(A)
    values, counts = zip(*c.most_common())


    cnt = 0
    for i in range(len(counts)):
        for j in range(10,0,-1):
            if counts[i] >= j * (j + 1)//2:
                cnt += j
                break
    print(cnt)

Submission status: Accepted

Solution code:
n = int(input())

lst = []
while n % 2 == 0:
  lst.append(2)
  n //= 2
f = 3
while f * f <= n:
  if n % f == 0:
    lst.append(f)
    n //= f
  else:
    f += 2
if n != 1:
  lst.append(n)
#print(lst)
count = 0
while lst:
  s = 0
  i = 1
  num = lst[0]
  for ele in lst:
    if ele == num:
      s += 1
  for j in range(s):
    lst.remove(num)
  while s > 0:
    s -= i
    i += 1
    if s >= 0:
      count += 1
  #print(lst)
print(count)

Submission status: Accepted

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

    a = prime_factorize(N)

    count_dict = {}
    total_key = 0
    for i in range(1024):
        total_key += i
        for j in range(total_key-i, total_key):
            count_dict[j] = i-1

    a_element_counter = {}
    for i in a:
        if i not in a_element_counter:
            a_element_counter[i] = 0
        a_element_counter[i] += 1

    ans = 0
    for e in a_element_counter.values():
        ans += count_dict[e]
    print(ans)

if __name__ == "__main__":
    resolve()

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

l = prime_factorize(N)

ans = 0
for prime in set(l):
    n_prime = l.count(prime)
    i = 1
    while (i + 2) * (i + 1) / 2 <= n_prime:
        i += 1
    ans += 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
ans=0
l=len(factorization(n))
s=factorization(n)
for i in range(l):
    for j in range(1,1000):
        if s[i][1]>=j:
            ans+=1
            s[i][1]-=j
        else:
            break
if n==1:
    print(0)
else:
    print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(math.sqrt(n)) + 2):
        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(stdin.readline().rstrip())
a = factorization(n)

m = 0
for b in a:
    bb = b[1]
    i = 0
    while True:
        bb -= i+1
        if bb >= 0:
            i += 1
        else:
            break
    m = m + i

if n != 1: print(m)
if n == 1: print(0)

Submission status: Accepted

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

def primeryNum(n):
    border=int(n**0.5)+1
    ary=list(range(int(n**0.5)+2))
    ary[1]=0
    for a in ary:
        if a>border: break
        elif a==0: continue
        for i in range(a*2,int(n**0.5)+2,a):
            ary[i]=0           
    return ary

primeryNumL=primeryNum(N)
# print(primeryNumL)
ans=0
N_=N
for x in primeryNumL:
    if x==0 or N%x!=0:
        continue
    n=N
    cnt=0
    while n%x==0:
        cnt+=1
        n/=x
    N_//=x**cnt
    buf=cnt-1
    res=1
    # print(x,cnt)
    for i in range(2,cnt+1):
        if buf<i:
            break
        buf-=i
        res+=1
    ans+=res
if N_>1:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import numpy as np
from collections import defaultdict
input = sys.stdin.readline


def log(*args):
    print(*args, file=sys.stderr)


def main():
    np.set_printoptions(threshold=20)
    N = int(input())
    d = defaultdict(int)
    for i in range(2, math.ceil(math.sqrt(N))):
        while N % i == 0:
            d[i] += 1
            N //= i
    if N != 1:
        d[N] += 1

    ans = 0
    for key in d:
        val = d[key]
        tmp = 0
        count = 0
        for i in range(1, val):
            tmp += i
            count += 1
            if tmp == val:
                break
            elif tmp > val:
                count -= 1
                break
        ans += max(count, 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(cnt)

    if temp!=1:
        arr.append(1)

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

    return arr

A = []
t = 0
for i in range(50):
    t += i
    A.append(t)
import bisect

B = factorization(n)
total = 0

for i in B:
    if i == A[bisect.bisect(A, i)]:
        total += bisect.bisect(A, i)
    else:
        total += bisect.bisect(A, i)-1
if n == 1:
    print(0)
else:
    print(total)

Submission status: Accepted

Solution code:

from collections import defaultdict

def prime_factor(n):
    d = defaultdict(int)
    for i in range(2, n + 1):
        if i * i > n:
            break

        while n % i == 0:
            d[i] += 1
            n //= i

    if n != 1:
        d[n] += 1

    return d


N = int(input())
d = prime_factor(N)
ans = 0
for v in d.values():
    i = 1
    res = 0
    while res + i <= v:
        res += i
        i += 1
    ans += i - 1

print(ans)

Submission status: Accepted

Solution code:
import math
from collections import Counter

def get_prime_factors(n):
    if n == 1:
        return []
    else:
        limit = int(math.sqrt(n))
        for i in range(2, limit + 1):
            if n % i == 0:
                return [i] + get_prime_factors(n // i)
        return [n]


N = int(input())

operations = 0
prime_factors = get_prime_factors(N)
for p, count in Counter(prime_factors).items():
    for i in range(1, count + 1):
        if i <= count:
            operations += 1
            count -= i
        else:
            break
print(operations)