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


bunkai = factorization(N)
count = 0

prime_flag = False
for x in bunkai:
    if x[0] == 1:
        prime_flag = True
        break
    else:
        check = x[1]
        current = 2
        while True:
            check -= current
            if check > 0:
                current += 1
            else:
                break
        count += current - 1
if prime_flag:
    print(0)
else:
    print(count)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = []
    x = N
    l = int(N ** 0.5)
    for t in range(2, l + 1):
        while x % t == 0:
            A.append(t)
            x //= t

    if x > 1:
        A.append(x)

    import collections
    ans = 0
    for v in collections.Counter(A).values():
        for n in range(1, 41):
            if v < n * (n + 1) // 2:
                ans += n - 1
                break

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
from collections import defaultdict

def main2():
    N = int(input())
    fac = defaultdict(int)
    lim = int(math.sqrt(N))

    for i in range(2, lim + 1):
        while N % i == 0:
            is_p = False
            fac[i] += 1
            N = N // i

        if i == lim:
            if N != 1:
                fac[N] += 1

    ans = 0
    for k, v in fac.items():
        e = 1
        for i in range(10000000):       
            if e <= v:
                ans += 1
                v -= e
                e += 1
            else:
                break
    print(ans)

if __name__ == "__main__":
    main2()

Submission status: Accepted

Solution code:
from collections import Counter
import math

def div(n):
    prime = []
    tmp = int(math.sqrt(n)) + 1
    
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            prime.append(num)
    
    if n != 1:
        prime.append(n)
    return prime

n = int(input())
prime_div = Counter(div(n))
ans = 0

for p, ex in prime_div.items():
    k = 1
    while ex >= k:
        ex -= k
        ans += 1
        k += 1

print(ans)

Submission status: Accepted

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

for i, j in pf.items():
  temp = j
  for k in range(1, j+1):
    temp   -= k
    if temp < 0:
      break
    else:
      answer += 1
      
print(answer)

Submission status: Accepted

Solution code:
from math import sqrt
n=int(input())
rn=int(sqrt(n))
s=[0]*(rn+1)
s[0]=-1
s[1]=-1
t=[0]*(rn+1)
for i in range(2,rn+1):
    if s[i] != 0:
        continue
    s[i] = i
    j = i
    while j < rn + 1:
        t[j] = 1
        j *= i
    for j in range(i * i, rn + 1,i):
        if s[j] == 0:
            s[j] = i

result = 0
last = -1
for i in range(2,rn+1):
    if t[i] == 0:
        continue
    if n % i == 0:
        result += 1
        n //= i
        last =i
if n != 1 and n > rn:
    result += 1
print(result)

Submission status: Accepted

Solution code:
import math
from collections import defaultdict

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

    for i in range(2, int(math.sqrt(N))+1):
        while N % i == 0:
            is_p = False
            fac[i] += 1
            N = N // i

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

    ans = 0
    for k, v in fac.items():
        e = 1
        for i in range(10000000):       
            if e <= v:
                ans += 1
                v -= e
                e += 1
            else:
                break
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(math.sqrt(n))+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())
factors = factorization(n)
res = 0
for j,cnt in factors:
  if j == 1: continue
  i = 1
  while cnt >= i:
    cnt -= i
    i += 1
    res += 1

print(res)

Submission status: Accepted

Solution code:
import collections as ct

n = int(input())

def calc(x):
    num = 1
    ref = 0

    while num <= x:
        x -= num
        ref += 1
        num += 1
    
    return ref

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 = ct.Counter(prime_factorize(n))
d = list(c.values())
ans = list(map(calc,d))

print(sum(ans))

Submission status: Accepted

Solution code:
def f(exponent):
	#reurns how many times a prime raised to exponent can be used
	lo,hi = 1, exponent + 1
	while(lo < hi):
		med = (lo + hi)/2
		if med * (med + 1)/2 > exponent:
			hi = med
		else:
			lo = med +1
	return lo -1

def answer(n):
	if n == 1: return 0
	res = 0
	for d in range(2, int(n ** 0.5) + 2):
		if n % d == 0:
			e = 0
			while(n%d == 0): 
				e +=1
				n/=d
			res+= f(e)
	if n > 1: res += 1
	return res

print answer(int(raw_input()))

Submission status: Accepted

Solution code:
def f(exponent):
	#reurns how many times a prime raised to exponent can be used
	step = 1
	cumul = 0
	count = 0
	while( cumul <= exponent):
		cumul += step
		count +=1
		step +=1
	return count - (1 if cumul > exponent else 0)

def answer(n):
	if n == 1: return 0
	res = 0
	for d in range(2, int(n ** 0.5) + 2):
		if n % d == 0:
			e = 0
			while(n%d == 0): 
				e +=1
				n/=d
			res+= f(e)
	if n > 1: res += 1
	return res

print answer(int(raw_input()))

Submission status: Accepted

Solution code:
def f(exponent):
	#reurns how many times a prime raised to exponent can be used
	step = 1
	cumul = 0
	count = 0
	while( cumul <= exponent):
		cumul += step
		count +=1
		step +=1
	return count - (1 if cumul > exponent else 0)

def answer(n):
	if n == 1: return 0
	res = 0
	on = n
	p = True
	for d in range(2, int(on ** 0.5) + 2):
		if n % d == 0:
			p = False
			e = 0
			while(n%d == 0): 
				e +=1
				n/=d
			res+= f(e)
	if n > 1: res += 1
	return res

print answer(int(raw_input()))

Submission status: Accepted

Solution code:
from math import sqrt

N = int(input())

rn = int(sqrt(N))
sieve = [0] * (rn + 1)
sieve[0] = -1
sieve[1] = -1
t = [0] * (rn + 1)
for i in range(2, rn + 1):
    if sieve[i] != 0:
        continue
    sieve[i] = i
    j = i
    while j < rn + 1:
        t[j] = 1
        j *= i
    for j in range(i * i, rn + 1, i):
        if sieve[j] == 0:
            sieve[j] = i

result = 0
last = -1
for i in range(2, rn + 1):
    if t[i] == 0:
        continue
    if N % i == 0:
        result += 1
        N //= i
        last = i
if N != 1 and N > rn:
    result += 1
print(result)

Submission status: Accepted

Solution code:
def sieve(x):
    """
    Sieve of Eratosthenes
    :param x: max value
    :return: list of bool
    """

    is_prime = [True] * (x + 1)
    is_prime[0] = is_prime[1] = False

    for i in range(2, x + 1):
        if is_prime[i]:
            for j in range(i * 2, x + 1, i):
                is_prime[j] = False

    return is_prime


n = int(input())

is_prime = sieve(10 ** 6)
primes = [i for i, e in enumerate(is_prime) if e]

ans = 0
for e in primes:
    div = e
    while n % div == 0:
        n //= div
        ans += 1
        div *= e

    while n % e == 0:
        n //= e

ans += n != 1

print(ans)

Submission status: Accepted

Solution code:
def sieve(x):
    """
    Sieve of Eratosthenes
    :param x: max value
    :return: list of bool
    """

    is_prime = [True] * (x + 1)
    is_prime[0] = is_prime[1] = False

    for i in range(2, x + 1):
        if is_prime[i]:
            for j in range(i * 2, x + 1, i):
                is_prime[j] = False

    return is_prime


n = int(input())

is_prime = sieve(10 ** 6)
primes = [i for i, e in enumerate(is_prime) if e]

ans = 0
for e in primes:
    div = e
    while n % div == 0:
        n //= div
        ans += 1
        div *= e

    while n % e == 0:
        n //= e


def f(x):
    if x < 2:
        return False

    for e in primes:
        if x % e == 0:
            return False

    return True


ans += n != 1

print(ans)

Submission status: Accepted

Solution code:
from math import ceil
n = int(input())
pf = []
t = n
if n == 1:
    print(0)
    exit()
for i in range(2, ceil(n ** 0.5) + 1):
    c = 0
    while t % i == 0:
        c += 1
        t //= i
    if c > 0: pf.append(c)
if t != 1: pf.append(1)

ans = 0
for i in pf:
    tmp = i
    j = 1
    while j <= tmp:
        tmp -= j
        ans += 1
        j += 1
print(ans)

Submission status: Accepted

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

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

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

    return arr

a=int(input())
b=factorization(a)
#print(b)
sum=0

for i in b:
    counter=0
    for j in range(1,100):
        #print(1+(j+2)*(j-1)//2)
        if i[1]>=1+(j+2)*(j-1)//2:
            counter=j
        else:
            break
    sum+=counter
if a==1:
  print(0)
else:
  print(sum)

Submission status: Accepted

Solution code:
ans = 0
N = int(input())
x = 2
while not N % x:
    ans += 1
    N //= x
    x *= 2
    
while not N % 2:
    N //= 2
    
i = 3

while i*i <= N:
    x = i
    while not N % x:
        ans += 1
        N //= x
        x *= i
        
    while not N % i:
        N //= i
        
    i += 2
    
if N > 1: ans += 1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import math
def I(): return int(stdin.readline().rstrip())

n = I()
m = n
l = []
for i in range(2,int(math.sqrt(n))+1):
    if n==1 or n<i:
        break
    if n%i==0:
        c = 0
        while n%i==0:
            n//=i
            c += 1
        for j in range(1,c+1):
            l.append(i**j)
    i += 1
if n!=1:
    l.append(n)

l.sort()
ans = 0
for i in l:
    if m==1 or m<i:
        break
    else:
        if not m%i:
            m/=i
            ans += 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:
from collections import Counter
def factorization(n):
    a=[]
    for i in range(2,int(n**.5)+1):
        while n%i==0:
            n//=i
            a.append(i)
    if n!=1:
        a.append(n)
    return a
n=int(input())
A=factorization(n)
B=Counter(A)
count=0
for key,value in B.items():
    for i in range(1,value+1):
        if n%(key**i)==0:
            count+=1
            n//=(key**i)
        else:break
print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import accumulate


def main():
    n = int(input())
    prime_counter = defaultdict(int)
    acc = tuple(accumulate(range(1, 42)))  # 10^12 < 2^39

    f = 2
    while n % f == 0:
        n //= f
        prime_counter[f] += 1
    f = 3
    while f * f <= n:
        if n % f == 0:
            n //= f
            prime_counter[f] += 1
        else:
            f += 2
    if n != 1:
        prime_counter[n] += 1

    ans = 0
    for c in prime_counter.values():
        for accum_index, x in enumerate(acc):
            if c < x:
                break
        ans += accum_index
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import accumulate


def main():
    n = int(input())
    prime_counter = defaultdict(int)
    acc = tuple(accumulate(range(1, 42)))  # 10^12 < 2^39

    f = 2
    while f * f <= n:
        if n % f == 0:
            n //= f
            prime_counter[f] += 1
        else:
            f += 1
    if n != 1:
        prime_counter[n] += 1

    ans = 0
    for c in prime_counter.values():
        for i, x in enumerate(acc):
            if c < x:
                tmp = i
                break
        ans += tmp
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import accumulate


def main():
    n = int(input())
    prime_counter = defaultdict(int)
    acc = tuple(accumulate(range(1, 42)))  # 10^12 < 2^39

    f = 2
    while n % f == 0:
        n //= f
        prime_counter[f] += 1
    f = 3
    while f * f <= n:
        if n % f == 0:
            n //= f
            prime_counter[f] += 1
        else:
            f += 2
    if n != 1:
        prime_counter[n] += 1

    ans = 0
    for c in prime_counter.values():
        for i, x in enumerate(acc):
            if c < x:
                tmp = i
                break
        ans += tmp
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
from collections import Counter
#a,b = map(int,input().split())
#L = list(map(int,input().split()))
def pr(n):
    L = []
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            L.append(i)
            n = n//i
    if n != 1:
        L.append(n)
    return L
dic = {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,27:6,28:7,29:7,30:7,31:7,32:7,33:7,34:7,35:7,36:8,39:8,40:8}
L = pr(n)
#print(L)
L = Counter(L)
num = 0
for k,v in L.items():
    num +=dic[v]
print(num)

Submission status: Accepted

Solution code:
n = int(input())

d = 2
ans = 0

while d * d <= n:
    if n % d != 0:
        d += 1
        continue
    
    z  = d
    
    while n % z == 0:
        n //= z
        z *= d
        ans += 1
        
    while n % d == 0:
        n /= d

if n != 1:
    ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

from collections import Counter

f = prime_factor(n)
c = Counter(f)
res = 0
for k, v in c.items():
    num = c[k] # 指数
    i = 1
    while num >= i:
        num -= i
        res += 1
        i += 1

print(res)

Submission status: Accepted

Solution code:
N = int(input())
def factorize(N):
    n = N
    r = []
    for i in range(2,int(N**0.5)+1): # intに変換すること
        cnt = 0
        while(n%i==0):
            cnt += 1
            n //= i #  整数除算(//)を使うこと
        if cnt!=0:
            r.append((i,cnt))
    if n!=1:
        r.append((n,1))
    return r

ans = 0
for _, cnt in factorize(N):
    i = 1
    while(i <= cnt):
        cnt-=i
        i+=1
        ans+=1
print (ans)

Submission status: Accepted

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

def factorization(n):
    arr = []
    for i in range(2,int(math.sqrt(n))+1):
        cnt = 0
        if n % i == 0:
            while n % i ==0:
                n //= i
                cnt +=1
            #arr.append([i,cnt])
            arr.append(cnt)
    if n != 1:
        #arr.append([n,1])
        arr.append(1)
    return arr
N = int(read())
arr = factorization(N)
ans = 0 
for a in arr:
  for i in range(1,50):
    if a-i>=0:
      a -=i
      ans +=1
    else:
      break
print(ans)

Submission status: Accepted

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

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

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

    return factorization_list


if __name__ == "__main__":
    N = int(input())

    if N == 1:
        print(0)

    else:
        factorization_list = factorization(N)
        count = 0
        for factor in factorization_list:
            e = factor[1]
            i = 1
            while True:
                e -= i
                i += 1
                count += 1
                if e < i:
                    break
        print(count)

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
    cnt = 0
    for l in arr:
        factor = l[0]
        i = l[1]
        if factor != 1:
            div = 0
            while 1:
                div += 1
                i -= div
                if i >= 0:
                    cnt += 1
                else:
                    break

    return cnt


print(factorization(N))

Submission status: Accepted

Solution code:
n = int(input())
import math
import numpy as np
t = []
b = n
# print(int(math.sqrt(n)))
for i in range(int(math.sqrt(n))):
    if b >= i+2:
        flag = True
        if b % (i + 2) == 0 and flag == True:
            flag = False
            t.append(0)
            while b % (i + 2) == 0:
                t[-1] += 1
                b /= (i+2)
                # print(i+2)
                # print(b)
    # print('a')
ans = 0
# print(b)
# print(t)
# exit()

tt = t

for i in range(len(t)):
    count = 1
    while t[i] >= count:
        ans += 1
        t[i] = t[i] - count
        count += 1

# for i in range(len(t)):
#     count = 1
#     while t[i]

if n != 1 and ans == 0:
    print('1')
    exit()

if n!= 1 and b != 1:
    ans += 1
# print(t)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())

n=10**6
#primeに素数を保管する下準備
prime = {i for i in range(2,n)}
for i in range(2,n):
    if i in prime:
        for j in range(i*2,n,i):
            if j in prime:
                prime.remove(j)
from collections import defaultdict
def prime_factorization(N):
    dic=defaultdict(int)
    for some in prime:
        if N%some==0:
            while N%some==0:
                N=N//some
                dic[some]+=1
        else:
            pass
    if N!=1:
        dic[N]=1
    return dic
ans=0
K=prime_factorization(N)
import bisect
H=[i*(i-1)//2 for i in range(10**4)]

for value in K.values():
    ans+=bisect.bisect_right(H,value)-2
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
    
a=factorization(int(input()))

b=[1,3,6,10,15,21,28,36,43]

ans=0
if len(a)==1 and a[0][0]==1:
    print(0)
    exit()

for i in a:
    for j in range(len(b)):
        if i[1]<b[j]:
            ans+=j
            break
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
from math import gcd
from random import randint


def brent(N):
    if N % 2 == 0:
        return 2
    y, c, m = randint(1, N-1), randint(1, N-1), randint(1, N-1)
    g, r, q = 1, 1, 1
    while g == 1:
        x = y
        for i in range(r):
            y = ((y*y) % N+c) % N
        k = 0
        while (k < r and g == 1):
            ys = y
            for i in range(min(m, r-k)):
                y = ((y*y) % N+c) % N
                q = q*(abs(x-y)) % N
            g = gcd(q, N)
            k = k + m
        r = r*2
    if g == N:
        while True:
            ys = ((ys*ys) % N+c) % N
            g = gcd(abs(x-ys), N)
            if g > 1:
                break
    return g


def factorize(n1):
    if n1 == 0:
        return []
    if n1 == 1:
        return [1]
    n = n1
    b = []
    p = 0
    mx = 1000000
    while n % 2 == 0:
        b.append(2)
        n //= 2
    while n % 3 == 0:
        b.append(3)
        n //= 3
    i = 5
    inc = 2
    while i <= mx:
        while n % i == 0:
            b.append(i)
            n //= i
        i += inc
        inc = 6-inc
    while n > mx:
        p1 = n
        while p1 != p:
            p = p1
            p1 = brent(p)
        b.append(p1)
        n //= p1
    if n != 1:
        b.append(n)
    return sorted(b)


n = int(input())
if n == 1:
    print(0)
    quit()
li = factorize(n)


def sums(factors):
    dicc = {}
    for factor in set(factors):
        n = factors.count(factor)
        dicc[factor] = [1]
        n -= 1
        while n > dicc[factor][-1]:
            dicc[factor].append(dicc[factor][-1] + 1)
            n -= dicc[factor][-1]
    return dicc


# print(li)
# print(sums(li))
count = 0
for i in sums(li).values():
    count += len(i)
print(count)

Submission status: Accepted

Solution code:
n=int(input())
a=p=1
while p<1e6:
 c=t=0;p+=1
 while n%p<1:n/=p;c+=1;x=c>t;t+=x;c-=t*x;a+=x
print(a-(n<2))

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 pop(stack):
	return stack[0],stack[1:]

def push(stack,x):
	stack.append(x)
	s = set(stack)
	p = list(s)
	p.sort()
	return p

n = int(input())
#a = sympy.factorint(n)
a = factorization(n)
ans = 0
if n != 1:
	for i in a:
		t = 1
		k = 1
		while t <= i[1]:
			#print(t,k,i[1])
			ans += 1
			k += 1
			t += k
			#print(t,k,i[1])
	
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
primes = dict()
p = 2

while p * p < n:
  if n % p == 0:
    primes[p] = 0
    while n % p == 0:
      n //= p
      primes[p] += 1
  p += 1
if p * p == n:
  primes[p] = 2
elif n >= p:
  primes[n] = 1

count = 0
for e in primes.values():
  c = 1
  while c * (c + 1) // 2 <= e:
    c += 1
  count += c - 1
  
print(count)

Submission status: Accepted

Solution code:
import sys
import collections
#import cython

    
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():
    read = lambda: sys.stdin.readline().rstrip()
    
    #N: cython.longlong = 0
    a = int(read())
    cnt = collections.Counter(prime_factorize(a))
    tot = 0
    for val in cnt.values():
        cnt = 0
        while val > 0:
            cnt += 1
            val -= cnt
            if val < 0:
                cnt -= 1
                break
            if val == 0: break
        tot += cnt
    print(tot)
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import math

def soi(num_ref):
    arr = []
    num = num_ref
    for i in range(2, int(math.sqrt(num))+1):
        if num%i == 0:
            cnt = 0
            while num%i == 0:
                cnt += 1
                num //= i
            arr.append([i, cnt])
    if num != 1:
        arr.append([num, 1])
    if arr == []:
        arr.append([num_ref, 1])
    return arr

N = int(input())
if N == 1:
    print(0)
    exit()
arr = soi(N)
cnt = 0
for i in arr:
    minus = 1
    tmp = i[1]
    while(tmp - minus >= 0):
        tmp -= minus
        minus += 1
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
cnt=0
factor=[]
for i in range(2, int(n**.5)+1):
    j=1
    while n%i==0:
        n//=i
        factor.append(i)
if n>1:
    cnt+=1

# 1->1, 3->2, 6->3, 10->4 ...を返す
def f(x):
    i=1
    cnt=0
    while x>=i:
       x-=i
       i+=1
       cnt+=1
    return cnt

from itertools import groupby
for k,v in groupby(factor):
    cnt+=f(len(list(v)))
print(cnt)

Submission status: Accepted

Solution code:
import collections

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

def func(a,b):
    cnt = 0
    exp = 1
    borg = b
    while True:
        b = pow(borg, exp)
        if(a%b != 0):
            break
        a = a/b
        exp = exp + 1
        cnt = cnt + 1

    return cnt

input = input()
c = collections.Counter(prime_factorize(int(input)))
L = list(c.values())
K = list(c.keys())
ans = 0
k = 0
for i in range(len(L)):
    k = int(K[i])
    f = func(int(input),k)
    ans = ans + f

print(ans)

Submission status: Accepted

Solution code:
import math
import numpy as np
n = int(input())
fac = []
sqrt_n = math.sqrt(n)
for i in range(2, int(sqrt_n)):
    if not n % i:
        fac.append(0)
    while not n % i:
        n /= i
        fac[-1] += 1
if n > sqrt_n:
    fac.append(1)
num = 0
for f in fac:
    num += np.count_nonzero(f >= np.cumsum(range(1, f+1)))
print(num)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    n=int(input())
    def prime_factorize1(N):
        l = []
        x = N
        y = 2
        while y*y <= x:
            while x % y == 0:
                l.append(y)
                x //= y
            y += 1
        if x > 1:
            l.append(x)
        return l

    from collections import Counter
    c=Counter(prime_factorize1(n))
    num=list(c.values())
    ans=0
    for i in num:
        x=i
        for j in range(1,i+1):
            if x-j>=0:
                ans+=1
                x-=j
            else:
                break
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import math
import decimal


def main():

    N = int(input())
    ans = 0
    A = int(math.ceil(N**0.5)+1)
    explist = []
    flag = False
    if N >= 3:
        for L in range(2, A):
            if N < L:
                break
            d = L
            cnt = 0
            while(True):
                if N % d == 0:
                    N /= d
                    cnt += 1
                    flag = True
                else:
                    break
            explist.append([d, cnt])
        for i in explist:
            c = i[1]
            for j in range(1, A):
                if c >= j:
                    ans += 1
                    c -= j
                else:
                    break
        if N >= A:
            ans += 1
        if flag:
            print(ans)
            return
        else:
            print(1)
            return
    elif N == 2:
        print(1)
        return
    else:
        print(0)
        return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections
n=int(input())
ans=0
d=1
m=0
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))
for i in range(len(list(c.values()))):
    while d*(d+1)/2<list(c.values())[i]+1:
        if m<=d:
            m=d
            d+=1
    if d*(d+1)/2>=list(c.values())[i]+1:
        ans+=m
        d=1
        m=0
print(ans)

Submission status: Accepted

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





from math import sqrt
def solve(x):
    return int((sqrt(1 + 8 * x) - 1)/2)



count = 0
for i in Counter(prime_factorize(m)).values():
    count += solve(i)
print(count)

Submission status: Accepted

Solution code:
n = int(input())
if n == 1:
    print(0)
    exit()
F = {}
tmp = n
i = 2
while i**2 <= tmp:
    cnt = 0
    while tmp % i == 0:
        cnt += 1
        tmp //= i
    if cnt > 0:
        F[i] = cnt
    i += 1
if tmp != 1 or F == {}:
    F[tmp] = 1
ans = 0
for p in F:
    a = 1
    while F[p] >= a:
        F[p] -= a
        ans += 1
        a += 1
print(ans)

Submission status: Accepted

Solution code:
N=int(input())

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

import collections
c = collections.Counter(prime_factorize(N))

X=list(c.values())
ans=0
for i in range(len(c.values())):
    for j in range(1,100):
        if X[i]<(j+1)*j/2:
            ans+=j-1
            break

print(ans)