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
import math

def fuctrization(n):
    arr = []
    tmp = n
    for i in range(2,math.ceil(n**(1/2))+1):
        if tmp%i==0:
            j = 0
            while tmp%i==0:
                j += 1
                tmp //= i
            arr.append([i,j])
    if tmp != 1:
        arr.append([tmp,1])
    if arr:
        pass
    else:
        arr.append([n,1])
            
    return arr
            
        
        
n = int(input())
if n == 1:
    print(0)
else:
    arr = fuctrization(n)
    nn = 0
    for i in range(len(arr)):
        k = arr[i][1]
        nnn = 1
        while k-nnn>=0:
            k -= nnn
            nnn += 1
            nn +=1
    print(nn)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

readline = sys.stdin.readline


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


def isqrt(n):
    if n > 0:
        x = 1 << (n.bit_length() + 1) // 2
        y = (x + n // x) // 2
        while y < x:
            x = y
            y = (x + n // x) // 2
        return x
    elif n == 0:
        return 0
    else:
        raise ValueError("isqrt() argument must be nonnegative")


def main():
    N = int(readline())
    c = prime_factorize(N)

    ans = 0
    for power in c.values():
        ans += (isqrt(1 + 8 * power) - 1) // 2

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
F={}
for i in range(2,int(N**0.5)+1):
    if N%i==0:
        F[i]=1
        N//=i
    while N%i==0:
        N//=i
        F[i]+=1
if N>1:
    F[N]=1

ans=0
for f in F:
    j=1
    while True:
        F[f]-=j
        j+=1
        if F[f]>=0:
            ans+=1
        else:
            break
print(ans)

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())
sum = 0
c = collections.Counter(prime_factorize(n))
index = 1
for i in c.values():
    tmp = i
    # print(str(tmp) + " tmp")
    for j in range(i):
        if j+1 > tmp:
            break
        tmp -= j+1
        sum += 1
print(sum)
# print(c)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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 isqrt(n):
    if n > 0:
        x = 1 << (n.bit_length() + 1) // 2
        y = (x + n // x) // 2
        while y < x:
            x = y
            y = (x + n // x) // 2
        return x
    elif n == 0:
        return 0
    else:
        raise ValueError("isqrt() argument must be nonnegative")


def main():
    N = int(readline())
    c = Counter(prime_factorize(N))

    ans = 0
    for power in c.values():
        ans += (isqrt(1 + 8 * power) - 1) // 2

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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

    ans = 0
    for power in c.values():
        tmp = power
        for j in range(1, power + 1):
            if j > tmp:
                break
            tmp -= j
            ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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

    ans = 0
    for power in a.values():
        tmp = power
        for j in range(1, power + 1):
            if tmp >= j:
                tmp -= j
                ans += 1
            else:
                break

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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


def main():
    N = int(readline())
    a = prime_factorize(N)

    ans = 0
    for power in a.values():
        tmp = power
        for j in range(1, power + 1):
            if tmp >= j:
                tmp -= j
                ans += 1
            else:
                break

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

    return arr

a=int(input())
if a==1:
  print(0)
else:
  lis=factorization(a)
  ans=0
  for i in range(len(lis)):
    k=1
    while lis[i][1]>=k:
      lis[i][1] -= k
      k+=1
      ans+=1
  print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
def main():
    n = int(input())

    def is_prime(n):
        for i in range(2, n + 1):
            if i * i > n:
                break
            if n % i == 0:
                return False
        return n != 1

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


    if is_prime(n):
        print(1)
        sys.exit()

    pd = prime_dec(n)
    pdc = Counter(pd)
    pdcl = [pdc[i] for i in pdc]
    r = 0
    for pse in pdcl:
        num = pse
        cnt = 1
        while num > 0:
            if cnt > num:
                break
            else:
                r += 1
                num -= cnt
                cnt += 1
    print(r)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#D
N=int(input())
N_C=N
P={}
for i in range(2,10**6+1):
    if N%i==0:
        P[i]=0
        while True:
            N=N/i
            P[i]+=1
            if N%i!=0:
                break
    if N==1:
        break
if N_C==1:
    print(0)
elif P=={}:
    print(1)
else:
    ans=0
    for key,v in P.items():
        z=key**v
        L=[0]+[True for i in range(v)]
        for i in range(1,v+1):
            if L[i]:
                if z%(key**i):
                    break
                z=z/(key**i)
                L[i]=False
                ans+=1
    if N!=1:
        ans+=1
    print(ans)

Submission status: Accepted

Solution code:
from math import sqrt, ceil, floor

def factorize(x):
    result = []
    for p in range(2, floor(sqrt(x))):
        exp = 0
        while x % p == 0:
            exp += 1
            x = x // p
        if exp > 0:
            result.append((p, exp))
    if x > 1:
        result.append((x, 1))
    return result

N = int(input())
factors = factorize(N)
ans = sum([floor((sqrt(exp * 8 + 1) - 1) / 2) for p, exp in factors])
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

ans = 0

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

if tmp != 1:
    factor.append(1)
if factor == []:
    factor.append(1)

for i in factor:
    j = 1
    while True:
        i -= j
        if i < 0:
            break
        j += 1
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import math

def answerCounter(N, i, answer):
    counter = 0
    power = 2
    sumPower = 1

    while N % i == 0:
        counter = counter + 1

        if sumPower == counter:
            answer = answer + 1
            sumPower = sumPower + power
            power = power + 1

        N = N // i

    return answer, N

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

    answer, N = answerCounter(N, 2, 0)

    for i in range(3, int(math.sqrt(N)) + 1, 2):
        answer, N = answerCounter(N, i, answer)

        if N < i:
            break

    if N > 2:
        answer, N = answerCounter(N, N, answer)

    print(answer)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math

N=int(input())

ans=0
arr=[]

tmp=1

#print(int(math.sqrt(N))+5)

for i in range(int(math.sqrt(N))+5):
    tmp=1

    while N % ((i+2)**tmp) == 0:
        N=N / ((i+2)**tmp)
        #print((i+2)**tmp)
        ans+=1
        tmp+=1

    while N % (i+2) == 0:
        N = N // (i+2)

if N > 1 :
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
N=int(input())

A=[]
B=[]
X=0
for i in range(1,20):
    X+=i
    A.append(X)
    B.append(i)
#print(A)
#print(B)
A=A[::-1]
B=B[::-1]
#print(A,B)
D={}
for i in range(2,10**6+1):
    while N%i==0:
        if i not in D:
            D[i]=1
            N//=i
        else:
            D[i]+=1
            N//=i
if N>1:
    D[N]=1

ans=0
for k,v in D.items():
    for j in range(len(A)):
        if A[j]<=v:
            ans+=B[j]
            break
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
 
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60

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

def main():
    N = int(readline())
    a = Counter(prime_factorize(N))
 
    ans = 0
    for power in a.values():
        ans += int(((1 + 8 * power) ** 0.5 - 1) / 2)
 
    print(ans)
    return
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

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

L_f = prime_factorize(L)
for p in L_f.values():
    k = 1
    while p  >= k :
        p -= k
        k += 1
        ans += 1
print(ans)

Submission status: Accepted

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

index = 2
array = [0] * math.ceil(math.sqrt(n)+1)
while index <= math.sqrt(n):
  while n % index == 0:
    array[index] += 1 
    n //= index
    
  index += 1
  
ans = 0
if n >= len(array):
  ans += 1
elif n != 1:
  array[n] += 1
  
for i in range(len(array)):
  index = 1
  while index <= array[i]:
    array[i] -= index
    index += 1
    ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
#N=10**18

lst=defaultdict(int)

for i in list(range(2,int(N**.5)+100)):
    while N>1 and N%i==0:
        N//=i
        lst[i]+=1
c=0
if N!=1:
    lst[N]+=1
#print(lst)
for s in lst:
    l=lst[s]
    i=1
    while l>=i:
        l-=i
        c+=1
        i+=1
print(c)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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

    ans = 0
    for power in a.values():
        ans += int(((1 + 8 * power) ** 0.5 - 1) / 2)

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

    for i in factorization(N):
        ans += num(i[1])
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
#素因数分解　#大きい数を数回
def prime_factorize(n):
    a = [] #素数が入る
    a.append(1)
    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)
    
    b = [[],[]]
    cnt = 1
    for i in range(len(a)+1):
        if i > 0 and i < len(a):
            if a[i] == a[i-1]:
                cnt += 1
            else:
                b[0].append(a[i-1])
                b[1].append(cnt)
                cnt = 1
        if i == len(a) and i > 0:
            b[0].append(a[i-1])
            b[1].append(cnt)
        elif i == len(a) and i == 0:
            b[0].append(a[i])
            b[1].append(cnt)
    return b #b[0]:素数, b[1]:肩の数字  #ex) 2^2*3 -> [[1,2,3][1,2,1]]


n = int(input())
a = prime_factorize(n)
ans = 0
for i in range(1, len(a[1])):
    ans += int((-1 + pow(1 + 8*a[1][i], 0.5)) / 2)
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

c = collections.Counter(prime_factorize(n))
A = list(c.values())

def dg(x):
    x = int(x)
    y = ((x * 8 + 1) ** (1 / 2) - 1) // 2
    return y

ans = 0
for v in A:
    ans += int(dg(v))

print(ans)

Submission status: Accepted

Solution code:
import itertools
import copy

N = int(input())
# N = (2 ** 4) * (3 ** 5) * (5 ** 2) * (7 ** 5)

# 素因数分解
# 戻り値: リスト
def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass

pf = prime_factor(N)
if len(pf) == 0:
    print(0)
    exit()

d = {}
for i in pf:
    if i not in d:
        d[i] = 1
        continue
    d[i] += 1

exist_num = []
ans = 0
for k in d.keys():
    for c in range(1, 100):
        if d[k] >= c:
            exist_num.append(k ** c)
            ans += 1
            d[k] -= c

# l = []
# for k in d.keys():
#     if d[k] > 0:
#         for _ in range(d[k]):
#             l.append(k)
# for i in range(1, len(l)+1):
#     combs = list(itertools.combinations(l, i))
#     if len(combs) > 0:
#         for comb in combs:
#             d_tmp = copy.copy(d)
#             if max(d_tmp, key=d.get) not in comb:
#                 continue
#             n = 1
#             for j in comb:
#                 d_tmp[j] -= 1
#                 if d_tmp[j] < 0:
#                     break
#                 n *= j
#             if n not in exist_num and n != 1:
#                 print(n)
#                 ans += 1
#                 d = copy.copy(d_tmp)
#                 exist_num.append(n)
print(ans)

Submission status: Accepted

Solution code:
import math

n=int(input())
cnt=0

for i in range(2,int(math.sqrt(n))+1):
  c=0
  while n%i==0:
    c+=1
    n//=i
  for j in range(1,c+1):
    c-=j
    if c<0:
      break
    cnt+=1
if n!=1:
  cnt+=1

print(cnt)

Submission status: Accepted

Solution code:
def fact(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 = int(input())
li = []
li = fact(a)
count = 0
i = 0
dif = 1

while i < len(li):
    if a == 1:
        break
    
    if li[i][1] >= dif:
        count += 1
        li[i][1] -= dif
        dif += 1
    else:
        dif = 1
        i += 1
print(count)

Submission status: Accepted

Solution code:
from collections import Counter


def prime_factorization(n):
    counter = Counter()
    max_pp = n
    while n % 2 == 0:
        counter[2] += 1
        n //= 2
    p = 3
    while p ** 2 <= max_pp:
        if n % p == 0:
            counter[p] += 1
            n //= p
        else:
            p += 2
    if n != 1:
        counter[n] += 1
    return counter


N = int(input())
prime_counter = prime_factorization(N)
ans = 0
for key in prime_counter.keys():
    for e in range(1, N):
        if prime_counter[key] >= e:
            prime_counter[key] -= e
            ans += 1
            e += 1
        else:
            break

print(ans)

Submission status: Accepted

Solution code:
import sys
N = int(sys.stdin.readline().rstrip())

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

primes = prime_factorize(N)

from collections import Counter

cnts = Counter(primes)
ans = 0
for p, cnt in cnts.items():
    tmp = 1
    while cnt - tmp >= 0:
        cnt -= tmp
        tmp += 1
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60

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

def main():
    N = int(readline())
    a = prime_factorize(N)
    
    ans = 0
    for power in a.values():
        ans += int(((1 + 8 * power) ** 0.5 - 1 ) / 2)
        
    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math


import math
import numpy as np
from collections import deque
def sieve_of_erastosthenes(num):
    """
    エラストネスの篩
    :param num:
    :return:
    """
    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 = math.sqrt(num)

    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
    return input_list

N=int(input())

def factorization(n):
    """

    素因数分解
    :param n:
    :return:
    """
    arr = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i]= cnt

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

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

    return arr

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]

input_ = make_divisors(N)
cnt = 0
# for i in input_:
#     n = N
#     _cnt =1
#     stack = deque([i])
#     seen= [i]
#     while stack:
#         s =stack.pop()
#         hoge= stack[-1]
#         for s
#         if math.log(hoge,)  and not hoge in seen:
#             stack.append(n/i)
#         else:
#             stack.pop
# prime_list = np.array(range(1,N+1))[sieve_of_erastosthenes(N)]
if N ==1:
    print(0)
    exit()
prime_dict = factorization(N)
# print(prime_dict)
searched = []
count=0
for prime, val in prime_dict.items():
    for e in range(1 ,val+1):

        z = prime ** e

        if N%z == 0 and not z in searched:
            searched.append(z)
            N = N//z
            count += 1
print(count)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())

n = N
counter = Counter()
while n % 2 == 0:
    counter[2] += 1
    n //= 2
p = 3
while p ** 2 <= N:
    if n % p == 0:
        counter[p] += 1
        n //= p
    else:
        p += 2
if n != 1:
    counter[N] += 1

ans = 0
for key in counter.keys():
    e = 1
    while counter[key] >= e:
        ans += 1
        counter[key] -= e
        e += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [1] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            p[2 * i * (i + 1) :: 2 * i + 1] = [0] * (((m - 1) - 2 * i * (i + 1)) // (2 * i + 1) + 1)

    a = [2 * i + 1 for i in range(m) if p[i]]
    a[0] = 2
    return a


def prime_factorize(n):
    a = defaultdict(int)
    primes = prime_numbers(int(n ** 0.5) + 1)
    for p in primes:
        while n % p == 0:
            a[p] += 1
            n //= p
        if n == 1:
            break
    if n != 1:
        a[n] += 1
    return a


def main():
    N = int(readline())
    a = prime_factorize(N)

    ans = 0
    for power in a.values():
        ans += int(((1 + 8 * power) ** 0.5 - 1) / 2)

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

def factorization(n):
    a = []
    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
            a.append([i, cnt])

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

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

    return a

result = factorization(N)

count = 0
for p, i in result:
    if p == 1:
        continue
    s = 0
    for k in range(1, i+1):
        if s + k > i:
            break
        else:
            N /= p ** k
            count += 1
            s += k
print(count)

Submission status: Accepted

Solution code:
n = int(input())
res = 0
for i in range(2, int(n**0.5)+1):
    if n%i == 0:
        e = 0
        while n%i == 0:
            n //= i
            e += 1
        tmp = 0
        for i in range(1, e+1):
            if e >= i:
                e -= i
                tmp += 1
        res += tmp
if n > 1: res += 1
print(res)

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
from collections import Counter
import itertools
import fractions
from decimal import *
#import numpy as np
#from functools import reduce

# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SR(): return sys.stdin.readline().rstrip()

ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_uppercase2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'

# リストを改行区切りで出力する
p2D = lambda x: print(*x, sep="\n")
p2E = lambda x: print(''.join(x))
p2S = lambda x: print(*x, sep=" ")

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

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

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

    return arr


N=II()


ans = factorization(N)

cnt = 0

for an in ans:
    if an[0] != 1:
        k = an[1]
        i = 1
        flg = True
        while flg:
            if k - i >= 0:
                k-=i
                cnt+=1
                i+=1
            else:
                flg = False
        


print(cnt)

Submission status: Accepted

Solution code:
#
import math

n=int(input())
N=n
if n==1:
    print(0)
    exit()
ans=0
z=[]
for i in range(2,int(math.sqrt(N))+1):
    if n%i==0:
        x=i#xは素数
        s=0
        while n>=1:
            if n%x==0:
                #print(n)
                n=n//x
                s+=1
                
            else:
                #print(n)
                z.append(s)
                break
    if n==1:
        break

#print(z)#各素数でわれる回数
if len(z)==0:
    print(1)
    exit()
for i in range(len(z)):
    j=1
    while z[i]>0:
        ans+=1
        z[i]-=j
        j+=1
        if z[i]<j:
            break
if n>math.sqrt(N):
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def prime_factorization(n):
    d = {}
    i = 2
    while i * i <= n:
        if n % i == 0:
            d[i] = 1
            n //= i
            while n % i == 0:
                n //= i
                d[i] += 1
        i += 1
    if n > 1:
        d[n] = 1
    return d

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

    d = prime_factorization(N)
    
    ans = 0
    for k, v in d.items():
        e = 0
        for i in range(1, v+1):
            e += i
            if e > v:
                break
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys 
from collections import Counter
input = sys.stdin.readline
n = int(input())
m = int(n**0.5)

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 n == 1:
    ans = 0
else:
    ans = 0
    a = prime_factorize(n)
    c = Counter(a)
    for val in c.values():
        j = 1
        while j*(j+1)//2 <= val:
            j += 1
        ans += j-1
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
from collections import Counter
import itertools
import fractions
from decimal import *
#import numpy as np
#from functools import reduce

# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SR(): return sys.stdin.readline().rstrip()

ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_uppercase2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'

# リストを改行区切りで出力する
p2D = lambda x: print(*x, sep="\n")
p2E = lambda x: print(''.join(x))
p2S = lambda x: print(*x, sep=" ")

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

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

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

    return arr


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

ans = factorization(N)

cnt = 0

for an in ans:
    p = an[0]
    e = an[1]
    num = 1
    while e >= num:
        e -= num
        cnt += 1
        num += 1
        


print(cnt)