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 collections import defaultdict

N = int(input())

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

p = defaultdict(int)

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

ans = 0

for v in p.values():
    n = 1
    i = 1
    while n <= v:
        ans += 1
        i += 1
        n += i

print(ans)

Submission status: Accepted

Solution code:
import math
from collections import defaultdict
from itertools import accumulate
N=int(input())
data=defaultdict(int)
result=0
for i in range(2,int(math.sqrt(N))+1):
    while N%i==0:
        N//=i
        data[i]+=1
if N!=1:
    data[N]+=1
cumsum=list(accumulate(range(1,10**6*2)))
for value in data.values():
    for i in range(10**6*2):
        if value<cumsum[i]:
            result+=i
            break
if result==0:
    if N!=1:
        result=1
print(result)

Submission status: Accepted

Solution code:
import math
import numpy as np
n = int(input())

s = math.sqrt(n)
i = 2
f = {}
while i <= s:
    while n % i == 0:
        f[i] = f.get(i,0)+1
        n = n // i
    i += 1

ans = 0
for x in f.values():
    e = 0
    cumsum = 0
    while e + cumsum + 1 <= x:
        e += 1
        cumsum += e
    ans += e
print(ans+(n>1))

Submission status: Accepted

Solution code:
N = int(input())
D = {}

for k in range(2,10**6):
  while N%k<1:
    N//=k
    D[k]=D.get(k,0)+1

a = 0
for i in D.values():
  t = 0
  c = 0
  while t+c<i:
    c+=1
    t+=c
  a+=c
print(a+(N>1))

Submission status: Accepted

Solution code:
N=int(input())
arr=[]
temp=N
for i in range(2, int(N**0.5//1+1)):
    if temp%i==0:
        cnt=0
        while temp%i==0:
            cnt+=1
            temp=temp//i
        # arr.append([i,cnt])
        arr.append(cnt)
if temp!=1:
    # arr.append([temp,1])
    arr.append(1)
if arr==[] and N!=1:
    # arr.append([N,1])
    arr.append(1)
# print(arr)
ans=0
for i in range(len(arr)):
    for n in range(1,100):
        if arr[i]>=n:
            ans+=1
            arr[i]-=n
        else:
            break
print(ans)

Submission status: Accepted

Solution code:
import math
def factrization_prime(number):
    factor = {}
    div = 2
    s = math.sqrt(number)
    while div < s:
        div_cnt = 0
        while number % div == 0:
            div_cnt += 1
            number //= div
        if div_cnt != 0:
            factor[div] = div_cnt
        div += 1
    if number > 1:
        factor[number] = 1
    return factor

N = int(input())
v = list(factrization_prime(N).values())
ans = 0
for i in range(len(v)):
    k = 1
    while(True):
        if v[i] >= k:
            v[i] -= k
            k += 1
            ans += 1
        else:
            break
print(ans)

Submission status: Accepted

Solution code:
import math
import random

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

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

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

def get_prime(number):
    prime_list = []
    search_list = list(range(2,number + 1))
    while search_list[0] <= math.sqrt(number):
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        search_list = [num for num in search_list if num % head_num != 0]
    prime_list.extend(search_list)
    return prime_list

l = get_prime(10**6+10)
N = int(input())
ans = 0
k = 1
i = 0
l2 = []
while(l[i]**2 <= N):
    if N % (l[i]**k) == 0:
        N //= (l[i]**k)
        l2.append(l[i]**k)
        k += 1
        ans += 1
    else:
        i += 1
        k = 1
index = 0
while(index < len(l2)):
    if N % (l2[index]) == 0:
        N //= l2[index]
    else:
        index += 1
if is_prime3(N) and N not in l2:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
#a, b, c, x, y = map(int, input().split())
#al = list(map(int, input().split()))
#al=[list(input()) for i in range(n)]


def prime_factorize(n):
    n_origin = n+0
    primelist = []
    a = 2
    while a*a <= n_origin:
        if n % a != 0:
            a += 1
            continue
        ex = 0
        while n % a == 0:
            ex += 1
            n = n//a
        primelist.append([a, ex])
        a += 1
    if n != 1:
        primelist.append([n, 1])
    return primelist


def sumf(n):
    return n*(n+1)//2


primes = prime_factorize(n)
ans = 0
for pl in primes:
    a, ex = pl
    i = 0
    while True:
        if sumf(i+1) > ex:
            break
        i += 1
    ans += i
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
M = N
pf = []
K = 2

while K*K <= M:
  while N%K == 0:
    pf.append(K)
    N = N//K
  K += 1
  
if N != 1:
  pf.append(N)

ans = 0

for i in set(pf):
  C = pf.count(i)
  for j in range(20):
    if j*(j+1)//2 <= C < (j+1)*(j+2)//2:
      ans += j
  
print(ans)

Submission status: Accepted

Solution code:
memo = [[None for i in range(50)] for j in range(50)]
def opt(n,k): # exponents must be >= k
	if n < k:
		return 0
	else:
		if memo[n][k]==None:
			memo[n][k] = max(1+opt(n-k,k+1),opt(n,k+1))
		return memo[n][k]

def prime_factorize(n):
	pf = {}
	d = 2
	orig_n = n
	while d*d <= orig_n:
		while n%d==0:
			pf[d] = pf.get(d,0)+1
			n //= d
		d += 1

	if n > 1:
		pf[n] = 1
	return pf 

print(sum([opt(e,1) for e in prime_factorize(int(input())).values()]))

Submission status: Accepted

Solution code:
n = int(input())
m = n
primes = {}
 
for i in range(2, int(n**0.5+2)):
  while m % i == 0:
    m //= i
    if i not in primes:
      primes[i] = 1
    else:
      primes[i] += 1
  if i > m:
    break
 
if m != 1:
  primes[m] = 1
 
cnt = 0
num = 0
flag = True
 
while flag == True:
  num += 1
  flag = False
  for i in primes:
    if 0 < primes[i] <= num*2:
      cnt += 1
      primes[i] = 0
    elif primes[i] > num*2:
      cnt += 1
      flag = True
      primes[i] -= num
 
print(cnt)

Submission status: Accepted

Solution code:
import collections
N = int(input())
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
def 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
use_list = []
cnt = 0
while True:
    flag = 0
    div_list = make_divisors(N)
    if len(div_list) == 1:
        break
    for i in range(1,len(div_list)):
        if (len(collections.Counter(prime_factorize(div_list[i]))) == 1) and (div_list[i] not in use_list):
            use_list.append(div_list[i])
            N = N //div_list[i]
            cnt +=1
            flag = 1
            break
    if flag == 0:
        break
print(cnt)

Submission status: Accepted

Solution code:
import math
from decimal import *
import random

def pf(n):
    rn = int(n)
    ans = []
    while(n%2==0):
        if(2 not in ans):
            ans.append(2)
        n//=2
    for i in range(3, int(math.sqrt(rn)), 2):
        while(n%i==0):
            if(i not in ans):
                ans.append(i)
            n//=i
            if(n==1):
                break
        if(n==1):
            break
    if(n>2):
        ans.append(n)
    return sorted(ans)
n = int(input())
d = pf(n)
if(d=={}):
    print(1)
else:
    ans = 0
    for i in range(len(d)):
        cnt = 1
        while(n >= d[i]**cnt):
            if(n%(d[i]**cnt)==0):
                n//=(d[i]**cnt)
                ans+=1
            cnt+=1
    print(ans)

Submission status: Accepted

Solution code:
import bisect

N=int(input())
ans=0
i=2
a=[j*(j+1)//2 for j in range(64)]
while i*i<=N:
    cnt=0
    while N%i==0:
        N//=i
        cnt+=1
    ans+=bisect.bisect_right(a,cnt)-1
    i+=1
if N>1:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
def div(n):
    i = 2
    a = n
    D = {}
    tmp = 1
    while i*i <= n:
        cnt = 0
        while a%i == 0:
            a = a // i
            tmp *= i
            cnt += 1
        if cnt > 0:
            D[i] = cnt
        i += 1
    if tmp != n:
        D[n] = 1
    return D

N = int(input())
D = div(N)
ans = 0
for v in D.values():
    i = 1
    total = 1
    while v >= total+(i+1):
        i += 1
        total += i
    ans += i

print(ans)

Submission status: Accepted

Solution code:
import math , sys

def fac(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
def sta ( x ):
    return int( 0.5* (-1 + math.sqrt(1+8*x)))
N = int( input() )

if N == 1:
    print(0)
    sys.exit()
if N == 2 or N ==3:
    print(1)
    sys.exit()
Is = fac( N )
ans = sum( [ sta(j) for j in Is])
print(max(ans,1))

Submission status: Accepted

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

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

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

    return arr

N = int(input())
fac = factorization(N)
result = 0
for div in fac:
    if div[0] == 1:
        continue
    i = 1
    count = 1
    while i <= div[1]:
        result += 1
        count += 1
        i += count

print(result)

Submission status: Accepted

Solution code:
N=int(input())

def divisor(x):
    div=[]
    for i in range(1,int(x**(1/2))+1):
        if x%i==0:
            div.append(i)
            if i!=x//i:
                div.append(x//i)
    return sorted(div)

def factorization(n):
    arr=[]
    temp=n
    for i in range(2,int(n**(1/2))+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

zt=[1]
ans=0
while N>1:
    for i in divisor(N):
        if i not in zt:  
            if len(factorization(i))==1:
                z=i
                zt.append(z)
                break
    if z==0:
        break
    N=N//z
    ans+=1
    z=0

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
 
from collections import Counter
 
f = Counter()

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

factors.sort()

for factor in factors:
    while n % factor == 0:
        n //= factor
        f[factor] += 1

 
    
def bsearch(test, lo, hi):
  while lo != hi:
    mid = (lo + hi + 1) // 2
    if test(mid):
      lo = mid
    else:
      hi = mid - 1
  return lo
 
ans = 0
for p, q in f.items():
  ans += bsearch(lambda w: w * (w + 1) // 2 <= q, 0, 10 ** 12)
 
if ans == 0 and n > 1:
    print(1)
else:
    print(ans)

Submission status: Accepted

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

#Prime factoring
pf = []
for i in range(2,math.ceil(n**0.5)+1):
    temp = 0
    while n%i==0:
        n /= i
        temp += 1
    if temp:
        pf.append(temp)
    if n==1:
        break
if n!=1:
    pf.append(1)

ans =  0
for i in range(len(pf)):
    j = 1
    while pf[i]-j>=0:
        ans += 1
        pf[i] -= j
        j += 1
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
ans = 0
l = factorization(N)
for i,j in l:
    k = 1
    while j >= k:
        ans += 1
        j -= k
        k += 1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
def solve():
    n = int(stdin.readline())
    ans = 0
    if n == 1: return 0
    prime = {}
    i = 2
    while i**2 <= n:
        if n%i != 0:
            i += 1
            continue
        ex = 0
        while n%i == 0:
            ex += 1
            n //= i
        prime[i] = ex
    if n != 1: prime[n] = 1
    for key in prime:
        cur = 1
        while prime[key] >= cur:
            ans += 1
            prime[key] -= cur
            cur += 1
    return ans

print(solve())

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
#import numpy as np
from math import sqrt, floor
def main():
    def factorization(n):
        l = []
        t = n
        for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
            if t % i == 0:
                cnt = 0
                while t % i == 0:
                    cnt += 1
                    t = t // i
                l.append([i, cnt])
        if t != 1:
            l.append([t, 1])
        if not l:
            l.append([n, 1])
        return l
    n = int(input())
    if n == 1:
        print(0)
        sys.exit()
    p = factorization(n)
    r = 0
    for pe in p:
        pe1 = pe[1]
        cnt = 1
        while pe1 >= cnt:
            pe1 -= cnt
            cnt = cnt + 1
            r += 1
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
def aprime_factorize(n: int) -> list:
    return_list = []
    while n % 2 == 0:
        return_list.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            return_list.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        return_list.append(n)
    return return_list

judge = []
cnt = 0
while len(judge) <= 40:
    for i in range(cnt+1):
        judge.append(cnt)
    cnt += 1
N = int(input())
list = Counter(aprime_factorize(N)).most_common()
res = 0
for i, li in enumerate(list):
    res += judge[li[1]]
print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict
from math import sqrt

def main():
    n = int(input())
    wi = 2
    cnt = 0
    d = defaultdict(lambda:0)
    fi = int(sqrt(1e12)+1)
    for i in range(2, fi):
        while n % i == 0:
            d[i] += 1
            n //= i
    if n != 1:
        d[n] = 1

    for val in d.values():
        x = val
        wi = 1
        while(x >= wi):
            x -= wi
            wi += 1
            cnt += 1
    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def factorize(n):
    lst = []
    tmp = n

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

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

    return lst


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

    lst = factorize(n)
    ans = 0

    for l in lst:
        for i in range(1, 10 ** 6 + 1):
            if i * (i + 1) // 2 > l[1]:
                ans += i - 1
                break

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC169 D
N=int(input())

def factorization(N):
    res=[]
    for i in range(2,int(N**(1/2))+2):
        if not N%i:
            r=0
            while not N%i:
                N//=i
                r+=1
            res.append((i,r))
    if N>1:
        res.append((N,1))
    return res

fact=factorization(N)

res=0
for p,r in fact:
    i=1
    while 1:
        if i*(i+1)//2<= r < (i+1)*(i+2)//2:
            break
        else:
            i+=1
    res+=i
print(res)

Submission status: Accepted

Solution code:
import collections

n = int(input())

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

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

c = collections.Counter(prime_factorize(n))
counts = c.values()
ans = 0

for i in counts:
    x = 0
    for j in range(i):
        x += j + 1
        if i >= x:
            ans += 1
        else:
            break

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

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

c = collections.Counter(prime_factorize(n))
_, counts = zip(*c.most_common())

l = list(counts)
ans = 0

if l == [1]: # prime number
    print(1)
    exit()

for i in l:
    for j in range(1, i+1):
        if i >= j:
            i -= j
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
def find_primes(n):
    ps = []
    t = [True] * n
    t[0] = t[1] = False
    for i in range(2, n):
        if not t[i]:
            continue
        ps.append(i)
        for j in range(i, n, i):
            t[j] = False
    return ps


def solve(string):
    n = int(string)
    if n == 1:
        return "0"
    rn = int(n**0.5 + 1)
    ps = find_primes(rn)
    ans = 0
    for i in ps:
        k = 1
        while n % (i**k) == 0:
            ans += 1
            n //= i**k
            k += 1
    return str(ans + (n >= rn))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
n = int(input())

def divGame(N=n):
  if N == 1:
    return 0
  if N == 2:
    return 1
  
  factors = []

  for i in range(2, int(N**0.5 + 1)):
    count = 0
    while N % i == 0:
      N /= i
      count += 1
    if count != 0:
      factors.append(count)
  if N != 1:
    factors.append(1)

  factors.sort()

  answer = 0
  accum = 1
  count = 1
  for i in range(len(factors)):
    while factors[i] >= accum:
      count += 1
      accum += count
    answer += count - 1

  return answer

print(divGame())

Submission status: Accepted

Solution code:
N = int(input())

d = 2

ans = 0

while d*d <= N:
    if N % d != 0:
        d += 1
        continue
        # Nがdで割り切れないとき，何もせずdを一歩進める。例えば d = 4 のときは，それ以前に d = 2 の時でNを割り切ってしまっているので，N % 4 != 0 と出る。

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

pf = {}


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

num_group = [0]*11 #2**50 > 10**12  55=1+2+...+10
for i in range(10):
    num_group[i+1] = num_group[i] + (i+1)
#print(num_group)

ans = 0
for prime in pf.keys():
    for i in range(1,11):
      if pf[prime]<num_group[i]:
          break
    ans += i-1
print(ans)

Submission status: Accepted

Solution code:
import copy
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)
M=L.copy()
M=list(set(M))

cnt=0
for x in M:
    m=L.count(x)
    for i in range(L.count(x)):
        if m-i-1 >= 0:
            m -= i+1
            cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import collections

#https://note.nkmk.me/python-prime-factorization/
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 f(n):
    for i in range(1,20):
        if n<(i*(i+1))//2:
            return i-1

n = int(input())
c = collections.Counter(prime_factorize(n))
ans = 0
for i in c.keys():
    ans += f(c[i])
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

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

c = collections.Counter(prime_factorize(n))
_, counts = zip(*c.most_common())

l = list(counts)
ans = 0

for i in l:
    x = 0
    for j in range(i):
        x += j + 1
        if i >= x:
            ans += 1
        else:
            break

print(ans)

Submission status: Accepted

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

#l = list(map(int, input().split()))
#import numpy as np
#arr = np.array([int(i) for i in input().split()])
'''
a,b=[],[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''

n=int(input())
def soinsuu(n):
    #素因数分解リスト生成,collections.Counter(a)で個数取得
    #1に対しては[]をreturn
    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 collections import Counter
a=Counter(soinsuu(n))
if n==1:
    print(0)
    sys.exit()
#print(a)
cnt=0
for i in range(1,1+max(a.values())):
    for item in a.keys():
        #print(i,item)
        if n%(item**i)==0:
            n//=item**i
            #print(n,item)
            cnt+=1
            if n==1:
                break

print(cnt)

Submission status: Accepted

Solution code:
import math

def prime(num):
	array=[]
	tmp=int(math.sqrt(n))+1
	for i in range(2,tmp):
		while num % i == 0:
			num/=i
			array.append(i)
	# リストが空なら入力(num)は素数
	
	if array==[]:
		return [num]
	else:
		if num>1:
			array.append(int(num))
		return array

n=int(input())
P=prime(n)
P=sorted(P)
num=n
if 1 in P:
	print(0)
else:
	ans=0
	tmp=0
	for i in range(0,len(P)):
		if i==0:
			tmp=P[i] 
		elif P[i]==P[i-1]:
			tmp*=P[i]
		else:
			tmp=P[i]
			num=n
		if num%tmp==0:
			num/=tmp
			ans+=1
			
	print(ans)

Submission status: Accepted

Solution code:
n = int(input())
m = n
primes = {}

for i in range(2, int(n**0.5+2)):
  while m % i == 0:
    m //= i
    if i not in primes:
      primes[i] = 1
    else:
      primes[i] += 1
  if i > m:
    break

if m != 1:
  primes[m] = 1

cnt = 0
num = 0
flag = True

while flag == True:
  num += 1
  flag = False
  for i in primes:
    if 0 < primes[i] <= num*2:
      cnt += 1
      primes[i] = 0
    elif primes[i] > num*2:
      cnt += 1
      flag = True
      primes[i] -= num

print(cnt)

Submission status: Accepted

Solution code:
'''
Created on 2020/08/23

@author: harurun
'''
def f(n):
  arr=[]
  temp=n
  for c in range(2,int(-(-n**0.5//1))+1):
    if temp%c==0:
      cnt=0
      while temp%c==0:
        cnt+=1
        temp//=c
      arr.append([c,cnt])
  if temp!=1:
    arr.append([temp,1])
  return arr

def main():
  import math
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  N=int(pin())
  r=f(N)
  ans=0
  for i in r:
    ans+=int((math.sqrt(1+8*i[1])-1)/2)
  print(ans)
  return 
main()

Submission status: Accepted

Solution code:
n=int(input())
def f(x):
    z=1
    while not(z*(z+1)<=2*x<(z+1)*(z+2)):
        z+=1
    return z

x=[-1]*(10**6+1) #2以上の自然数に対して最小の素因数を表す
x[0]=0
x[1]=1
i=2
prime=[]
while i<=10**6:
    if x[i]==-1:
        x[i]=i
        prime.append(i)
    for j in prime:
        if i*j>10**6 or j>x[i]:break
        x[j*i]=j
    i+=1
if n==1:
    print(0)
    exit()

a=[]
q=0
for i in range(len(prime)):
    p=prime[i]
    while n%p==0:
        q+=1
        n=n//p
    if q>0:a.append(q)
    q=0

ans=0
for i in range(len(a)):
    ans+=f(a[i])
print(ans if n==1 else ans+1)

Submission status: Accepted

Solution code:
n=int(input())
def f(x):
    z=1
    while not(z*(z+1)<=2*x<(z+1)*(z+2)):
        z+=1
    return z

x=[-1]*(10**6+1) #2以上の自然数に対して最小の素因数を表す
x[0]=0
x[1]=1
i=2
prime=[]
while i<=10**6:
    if x[i]==-1:
        x[i]=i
        prime.append(i)
    for j in prime:
        if i*j>10**6 or j>x[i]:break
        x[j*i]=j
    i+=1
if n==1:
    print(0)
    exit()
y=0
j=2
while j*j<=n:
    if n%j==0:
        y=1
    j+=1
if y==0:
    print(1)
    exit()
a=[]
q=0
for i in range(len(prime)):
    p=prime[i]
    while n%p==0:
        q+=1
        n=n//p
    if q>0:a.append(q)
    q=0

ans=0
for i in range(len(a)):
    ans+=f(a[i])
print(ans if n==1 else ans+1)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
class Sieve2: #√nまでの素因数で試し割り 前処理O(√nloglogn+√n/logn)
    def __init__(self,n):
        self.primes=[]
        self.f=[0]*(int(n**0.5)+1) #ふるい（素数ならその値）
        self.f[0]=self.f[1]=-1
        for i in range(2,int(n**0.5)+1): #素数リスト作成
            if self.f[i]: continue
            self.primes.append(i)
            self.f[i]=i
            for j in range(i*i,int(n**0.5)+1,i):
                if not self.f[j]:
                    self.f[j]=i  #最小の素因数を代入

    def prime_fact(self,x): #素因数分解 {2:p,3:q,5:r,...}
        fact_dict=dict()
        for p in self.primes:
            if p*p>x:break
            while x%p==0:
                x//=p
                fact_dict[p]=fact_dict.get(p,0)+1
        if x>1:fact_dict[x]=fact_dict.get(x,0)+1
        return fact_dict

def main():
    n = int(input())
    Sieve = Sieve2(n)
    prime_dict = Sieve.prime_fact(n)
    ans = 0
    for fact in prime_dict.values():
        f = fact
        x = 1
        while f > 0:
            if f >= x:
                ans += 1
            f -= x
            x += 1
    print(ans)


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import collections
import sys
def input(): return 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

N = int(input())
count = 0
prime_list = collections.Counter(prime_factorize(N))

for key in prime_list:
    num = prime_list[key]
    for i in range(1, num+1):
        if i <= num:
            num -= i
            count += 1
        else:
            break

print(count)

Submission status: Accepted

Solution code:
def prime_fact(n):
    primes = []
    i = 2
    while i * i <= n:
        cnt = 0
        while n % i == 0:
            n //= i
            cnt += 1
        if cnt:
            primes.append([i, cnt])
        i += 1

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

n = int(input())

primes = prime_fact(n)

cnt = 0
for i, j in primes:
    k = 1
    while k <= j:
        j -= k
        k += 1
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import math

def main():
	N = int(input())
	f = prime_factorize(N)
	cnt = 0
	if N == 1:
		print(cnt)
		return 0

	for p in f:
		prime = p[0]
		power = p[1]
		tmp = math.floor((math.sqrt(1 + 8 * power) - 1) / 2)
		cnt += tmp
	print(cnt)


def prime_factorize(n):
	ret = []
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			cnt = 0
			while n % i == 0:
				cnt += 1
				n = n // i
			ret.append([i, cnt])
	if n != 1:
		ret.append([n, 1])
	if len(ret) == 0:
		ret.append([n, 1])

	return ret

main()

Submission status: Accepted

Solution code:
n=int(input())

big = 10**6+10

furui = [0]*big
furui[0]=1
furui[1]=1

for i in range(2,big):
    if furui[i]==0:
        for j in range(i,len(furui),i):
            furui[j] = 1
            furui[i]=0
        
prime = [i for i in range(len(furui)) if furui[i]==0]

soinsuu=[]
for p in prime:

    while n%p==0:
        n //= p
        soinsuu.append(p)

if n!=1:
    soinsuu.append(n)
    
# print(soinsuu)

ans=0

for i in set(soinsuu):
    
    kai = ((8*soinsuu.count(i)+1)**0.5 -1)/2
    ans += int(kai)
    
print(ans)

Submission status: Accepted

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

n = int(input())
c = Counter(prime_factorize(n))
v = list(c.values())

ans = 0
for i in v:
    k = i
    s = 0
    for j in range(1, i+1):
        s += j
        if s <= k:
            ans += 1
        else:
            break
print(ans)

Submission status: Accepted

Solution code:
import math

def solve():
    N = int(input())
    ans = 0
    for i in range(2, int(math.sqrt(N)) + 2):
        n = 1
        cnt = 0
        while N % i == 0:
            N //= i
            cnt += 1
            if cnt == n:
                cnt = 0
                n += 1
                ans += 1
    if N != 1:
        ans += 1
    return ans

print(solve())