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())
nn=N
import math
sq=round(math.sqrt(N))+1

i=2
ans=0
count1=0
count2=1
while sq>=i:
    if nn%i==0:
        nn//=i
        count1+=1
        if count1==count2:
            ans+=1
            count2+=1
            count1=0
    else:
        i+=1
        count1=0
        count2=1

if nn>sq:
    ans+=1

print(ans)

Submission status: Accepted

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

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


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([i, cnt])

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

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

    return arr


li = fac(n)
kaijo = [0, 1, 3, 6, 10, 15, 21, 28, 36, 45]

for i in range(len(li)):
    for j in range(len(kaijo)):
        if kaijo[j] <= li[i][1] < kaijo[j + 1]:
            ans += j

print(ans)

Submission status: Accepted

Solution code:
import math

def factorization(n):
    r = []
    temp = n
    for i in range(2,int(math.sqrt(n))+1):
        m = 0
        while temp % i == 0:
            temp /= i
            m += 1
        if m > 0:
            r.append((i,m))
    if temp != 1:
        r.append((temp,1))
    if len(r) == 0:
        r.append((n,1))
    return r

n = int(input())
p = factorization(n)
ans = 0
if p[0][0] == 1:
    ans = 0
else:
    for x in p:
        i = 1
        s = x[1]
        while s >= i:
            s -= i
            i += 1
        ans += (i-1)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

def get_count(c):
  ans = 0
  _max = c
  for i in range(1,c+1):
    if i <= _max:
      ans += 1
      _max -= i
    else:
      break
  return ans
a = int(input())
counter = Counter(prime_factor(a))
ans = 0
for i in counter:
  ans += get_count(counter[i])
print(ans)

Submission status: Accepted

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N = int(input())

    #output
    #ある整数nの素因数を列挙

    import math
    from collections import Counter

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

    s = Counter(prime_factors(N))

    def triangle(n):
        i = 1
        while i*(i+1)//2 <= n:
            i += 1
        return i-1

    answer = 0
    for l in s.values():
        answer += triangle(l)

    print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

def pri_me(x):
    if x == 2:
        return True
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            return False
    return True
#print(pri_me(n))


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

n = int(input())
if n==1 or n == 0:
    print(0)
    exit()
if pri_me(n):
    print(1)
    exit()
N = n
ans = 0
from collections import Counter
d=prime_factorize(n)
d = sorted(d)
for i in set(d):
    cnt = d.count(i)
    now = 1
    k = 1
    while now <=cnt:
        ans += 1
        k+=1
        now += k
print(ans)

Submission status: Accepted

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

element = int(math.sqrt(n))
nk = n
i = 2
p = []
while nk>1 and i <= element:
    if nk % i == 0:
        p.append(i)
        while nk % i == 0:
            nk //= i
    i += 1
if nk > 1:
    p.append(nk)
ans = 0
option = [[k, k] for k in p]
heapq.heapify(option)
while n>1 and option:
    val, p = heapq.heappop(option)
    #print(n, ans, val, option)
    if val*p <= n:
        heapq.heappush(option, [val*p, p])
    if n % val == 0:
        ans += 1
        n //= val
print(ans)

Submission status: Accepted

Solution code:
import math
n = int(input())
if n == 1:
  print(0)
  exit(0)
  
pows = []
upto = int(math.sqrt(n))
for i in range(2, upto+1):
  if n % i == 0:
    cc = 0
    while n % i == 0:
      n //= i
      cc += 1
    pows.append(cc)
    

if n != 1:
  pows.append(1)
    
if len(pows) == 0:
  print(1)
  exit(0)
  
ans = 0
for pp in pows:
  start = 1
  cc = 0
  while pp - start >= 0:
    cc += 1
    pp -= start
    start += 1

  ans += cc

print(ans)

Submission status: Accepted

Solution code:
#D
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
def suretu(n):
    a = []
    i = 1
    while True:
        n  = n - i
        if n >= 0:
            a.append(i)
            i += 1
        else:
            break
    return a
f = factorization(n)
flg = True
#print(f)
cnt = 0
if f == [[1,1]]:
    print(0)
else:
    for i in range(len(f)):
        cnt += len(suretu(f[i][1]))
    print(cnt)

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

def cnt(num):
    i=1
    co=0
    while num>=0:
        num-=i
        co+=1
        i+=1
    return co-1

n=int(input())
c=Counter(prime_factorize(n))
l=list(c.values())
r=0
for x in l:
    r+=cnt(x)
print(r)

Submission status: Accepted

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

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

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

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

    return arr

N=int(input())

if N==1:
    print(0)
else:
    a=factorization(N)

    ans=0

    for j in range(len(a)):
        for k in range(1000000000000000):
            a[j][1]-=k
            ans+=1
            if a[j][1]-(k+1)<0:
                ans-=1
                break
    print(ans)

Submission status: Accepted

Solution code:
from math import sqrt
import itertools

def factorization(n):
    factors = []
    temp = n
    for i in range(2, int(sqrt(n))+1):
        if temp % i == 0:
            count = 0
            while temp % i == 0:
                count += 1
                temp //= i
            factors.append((i, count))
    if temp != 1:
        factors.append((temp, 1))
    if not factors:
        factors.append((n, 1))

    return factors


N = int(input())
factors = factorization(N)
count = 0
for a, b in factors:
    c = 0
    for i in itertools.count(1):
        c += i
        if c > b:
            break
        else:
            count += 1

if N == 1:
    print(0)
else:
    print(count)

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 not arr:
        arr.append([n, 1])

    return arr


n = int(input())
cnt = 0
z_list = []
f = factorization(n)
for fact in f:
    for j in range(1, fact[1] + 1):
        z = fact[0] ** j
        if z < 2:
            print(0)
            exit()
        if str(z) not in z_list:
            if n % z == 0:
                n = n // z
                cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import math
def check(n):
    count = 0
    end = int(math.sqrt(n)+1)
    for i in range(2,end):
        if n%i==0:
            count += 1
            n/=i
        if n%i==0:
            l = 2
            count2 = 0
            while n%i==0:
                n/=i
                count2+=1
                if count2==l:
                    count+=1
                    count2=0
                    l+=1
        if n==1:
            return count
    if n==1:
        return 0
    if count==0:
        return 1
    else:
        return count+1   
n = int(input())
ans = check(n)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import math
import copy 

N = np.int64(input())

p = []
x  = 2
xen = np.sqrt(N)
while N > 1 : 
    if N%x == 0 :
        p.append(x)
        N = N/x
    else :
        x = x + 1
        if x > xen :
            p.append(int(N))
            break
e = []
while p!=[]:
    i = p[0]
    n = p.count(i)
    p = p[n:]
    e.append(n)
    if p==[]:break

i = 0
m = 0
e = np.array(e)
ans = 0
while True:
    i += 1
    e = e-i
    e = e[e>=0]
    ans = ans + len(e)
    if len(e)==0 : break

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
C=[0]*(10**6+1)
n=[i for i in range(50)]
n[0]=1
for i in range(40):
    n[i+1]+=(n[i]+1)
for i in range(2,int(N**0.5)+1):
    if N%i==0:
        while N%i==0:
            C[i]+=1
            N//=i
res=0
for c in C:
    if c>0:
        for i in range(50):
            if c<n[i]:
                res+=i
                break
print(res+1 if N>1 else res)

Submission status: Accepted

Solution code:
#-------------------------------------------------------------------
import sys
def _p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
import math

def factorize(n):
  ret, a = [], n
  for i in range(2, int(n**0.5)+1):
    if a%i>0: continue
    c=0
    while a%i==0:
      a//=i
      c+=1
    else:
      ret.append((i,c))
  if a!=1: ret.append((a,1))
  return ret


n = int(input())
N = factorize(n)

ans=0
for p,i in N:
  for j in range(i):
    a = pow(p,j+1)

    if a > n: break

    if n % a == 0:
      n /= a
      ans += 1


print(ans)

Submission status: Accepted

Solution code:
N=int(input())
C=[]
n=[i for i in range(50)]
n[0]=1
for i in range(49):
    n[i+1]+=(n[i]+1)
for i in range(2,int(N**0.5)+1):
    if N%i==0:
        while N%i==0:
            C.append(i)
            N//=i
D=set(C)
E=[]
for d in D:
    E.append(C.count(d))
res=0
for e in E:
    for i in range(50):
            if n[i]<=e<n[i+1]:
                res+=i+1
                break
                
print(res+1 if N>1 else res)

Submission status: Accepted

Solution code:
n = int(input())
t = []
for i in range(2,int(-(-n**0.5//1))+1):
    if(n%i == 0):
        cmp = 0
        while(n%i == 0):
            cmp += 1
            n //= i
        t.append([i,cmp])
    if(n == 1):
        break
if(n != 1):
    z = 1
else:
    z = 0
z -= len(t)
for i in range(len(t)):
    j = 1
    while(t[i][1] >= 0):
        t[i][1] -= j
        j += 1
        z += 1
print(z)

Submission status: Accepted

Solution code:
#-------------------------------------------------------------------
import sys
def _p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
import math

def factorize(n):
  ret, a = [], n
  for i in range(2, int(n**0.5)+1):
    if a%i>0: continue
    c=0
    while a%i==0:
      a//=i
      c+=1
    else:
      ret.append((i,c))
  if a!=1: ret.append((a,1))
  return ret


n = int(input())
N = factorize(n)

ans=0
for p,i in N:
  for j in range(i):
    a = pow(p,j+1)
    if n % a == 0:
      n /= a
      ans += 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import math
import copy 
N = input()
N = np.int64(N)
# print(np.sqrt(N))
l = []
x  = 2
xen = np.sqrt(N)
while N>1:
    if N%x ==0:
        l.append(x)
        N = N/x
    else:
        x = x + 1
        if x > xen:
            l.append(int(N))
            break
# l = [2, 2, 2, 3, 3, 3, 5, 5, 5, 6079, 6079]
# l = [2, 2, 2, 3]
l2 = []
while l!=[]:
#     print(l)
    i = l[0]
    n = l.count(i)
    l = l[n:]
    l2.append(n)
    if l==[]:break
# print(l2)
# print('///')

i = 0
m = 0
l2 = np.array(l2)
# print(l2)
ans = 0
while True:
    i += 1
#     m = m + i
#     print(m)
    l2 = l2-i
    l2 = l2[l2>=0]
    ans = ans + len(l2)
#     print(l2)
    if len(l2)==0:break
print(ans)

Submission status: Accepted

Solution code:
import collections
import math

n = int(input())
B = [1,3,6,10,15,21,28,36,45,55,66,78,91,105]
ans = 0

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True
if is_prime(n) == True:
  print(1)
  exit()

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

c = collections.Counter(prime_factorize(n))  
for v in c.values():
  for j in range(len(B)):
    if v < B[j]:
      ans += j
      break
      
print(ans)

Submission status: Accepted

Solution code:
def prime_factorize(n):
    if 2 <= n < 4:
        return [n]
    res = []
    i = 2
    while i * i <= n:
        while n % i == 0:
            res.append(i)
            n //= i
        i += 1
    if n != 1:
        res.append(n)
    # res.sort()
    return res

from itertools import groupby
def resolve():
    N = int(input())
    P = prime_factorize(N)
    ans = 0
    grp_P = groupby(P)
    for v, g in grp_P:
        n = len(list(g))
        for i in range(1, 100000):
            n -= i
            if n >= 0:
                ans += 1
            else:
                break
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import math
"nの約数列挙"
def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return ass

"nの素因数分解"
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

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


import collections
N = int(input())
A = prime_factor(N)
A.sort()
c = collections.Counter(A)
ans = 0
for x in c.values():
  count = 1
  while x > 0:
    x -= count
    if x >= 0:
      count +=1
      ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
tmp = n
d = []
for i in range(2, int(n ** 0.5) + 1):
    if tmp % i == 0:
        while tmp % i == 0:
            d.append(i)
            tmp //= i
if tmp != 1:
    d.append(tmp)

dv = Counter(d)

cnt = 0
for p in dv.keys():
    for e in range(1, dv[p]+1):
        z = p ** e
        if n % z == 0:
            cnt += 1
            n //= z

print(cnt)

Submission status: Accepted

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

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

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

    return arr


n = int(input())
if n == 1:
    print(0)
    exit()
z = factorization(n)
cnt = 0
for item in z:
    p = item[0]
    e = item[1]
    num = 1
    while e >= num:
        e -= num
        cnt += 1
        num += 1

print(cnt)

Submission status: Accepted

Solution code:


import math
from collections import Counter
n = int(input()) # 24
val = n
l = []

i = 2
while i <= int(math.sqrt(n)):
    if n % i == 0:
        n //= i
        l.append(str(i))
    else:
        i += 1
#print(l)
if n != 1:
    l.append(str(n))
# print(Counter(ans))
answer = 0
#print("counter", Counter(l))
for a, b in Counter(l).items():
    z = 0
    for i in range(1, b+1):
        z += i
        if b - z < 0:
            break
        answer += 1
print(answer)

Submission status: Accepted

Solution code:
from collections import Counter
 
def factorize(N):
    p = 2
    PRIME = []
    while p * p <= N:
        if N % p == 0:
            N //= p
            PRIME.append(p)
        else:
            p += 1
    if N > 1:
        PRIME.append(N)
    return Counter(PRIME)
 
n = int(input())
 
prime = factorize(n)
ans=0
for i in prime:
  for j in range(1,prime[i]+1):
    if n % i**j==0:
      n//=i**j
      ans+=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

n = int(input())

cnt = 0
a = factorization(n)
if n == 1:
  print(0)
  exit()

for i in range(len(a)):
  a[i][1] -= 1
  cnt += 1
  b = 2
  while a[i][1] > 0:
    a[i][1] -= b
    if a[i][1] >= 0:
      cnt += 1
    b += 1
 
print(cnt)

Submission status: Accepted

Solution code:
from collections import Counter

def Eratosthenes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

n = int(input())
n2 = n

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

prime_factors = [] #素因数
for i in Eratosthenes(int(n ** 0.5)):
    if i**2 > n2:
        break
    while n2 % i == 0:
        prime_factors.append(i)
        n2 //= i
if n2 > 1:
    prime_factors.append(n2)

#↑までで素因数分解

cntr = Counter(prime_factors)
cnt = 0
#for k, v in cntr.items():
for v in cntr.values():
    sisuu = v
    sub = 1
    while sisuu - sub >= 0:
        sisuu -= sub
        cnt += 1
        sub += 1
print(cnt)
"""
ans = []
list = []
for i in prime_factors:
    for j in list:
        if j % i == 0:
            tmp = list.pop(list.index(j)) * i
            if tmp in ans:
                list.append(tmp)
                continue
            ans.append(tmp)
    if i in list:
        tmp = list.pop(list.index(i)) * i
        if tmp in ans:
            list.append(tmp)
            continue
        ans.append(tmp)
    elif i in ans:
        list.append(i)
    else:
        ans.append(i)

print(len(ans))
"""

Submission status: Accepted

Solution code:

def prime_factorize(n):
    if 2 <= n < 4:
        return [n]
    res = []
    i = 2
    while i * i <= n:
        while n % i == 0:
            res.append(i)
            n //= i
        i += 1
    if n != 1:
        res.append(n)
    # res.sort()
    return res

from itertools import groupby
def resolve():
    N = int(input())
    P = prime_factorize(N)
    ans = 0
    grp_P = groupby(P)
    for v, g in grp_P:
        n = len(list(g))
        for i in range(1, 100000):
            n -= i
            if n >= 0:
                ans += 1
            else:
                break
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
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 renzoku(n):
    x = (-1+(1+8*n)**(0.5))//2
    return int(x)
      
N = int(input())
if N == 1:
  print("0")
  sys.exit()
oriN = N*1
A = factorization(N)
#print(A)
M = len(A)
 
ans = 0
for i in range(M):
  temp = A[i][1]
  f = renzoku(temp)
  ans += f
print(ans)

Submission status: Accepted

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

while d ** 2 <= 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:
import math
n = int(input())
prime_list = []

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

for i in range(2, int(math.sqrt(n)) + 1):
    if n % i == 0:
        prime_list.append(i)
        n /= i
        index = 2
        counter = 0
        while 1:
            if n % i == 0:
                counter += 1
                n /= i
                if(counter == index):
                    prime_list.append(i ** index)
                    index += 1
                    counter = 0
            else:
                break
if n > 1:
    prime_list.append(n)

print(len(prime_list))

Submission status: Accepted

Solution code:
def d_div_game():
    def prime_factorization_dict(n):
        """n を素因数分解したときの素数とその指数の辞書"""
        from collections import defaultdict
        if n == 1:
            return {2: 0}  # 1 は素数の 0 乗の積とみなす
        i, table = 2, defaultdict(int)
        while i**2 <= n:
            while n % i == 0:
                table[i] += 1
                n //= i
            i += 1
        if n > 1:
            table[n] = 1
        return table

    def sub_calc(n):
        """t = 1 + ... + e <= n となる最大の e を求め、そのときの項数を返す"""
        t, e = 0, 1
        while True:
            t += e
            if t > n:
                return e - 1
            e += 1

    return sum(sub_calc(v) for v in prime_factorization_dict(int(input())).values())

print(d_div_game())

Submission status: Accepted

Solution code:
from math import floor, sqrt


def func(x):
    return floor((sqrt(1 + 8 * x) - 1) / 2)


N = int(input())
limit = floor(sqrt(N))

primes = [2]

count = 0
flag = True
p = 2
while 1:
    #print(p,N)
    isprime = True
    if N == 1:
        break
    if p > sqrt(N):
        count += 1
        break
    
    a = 0
    while N % p == 0:
        #print("while",p, a)
        a += 1
        N = N // p
    count += func(a)
    if p == 2:
        p = 3
    else:
        p += 2
print(count)

Submission status: Accepted

Solution code:
import math
N = int(input())
# A, B = [i for i in input().split()]


def prime_factorization(n):
    # n = p1**e1 * p2**e2... pm**emのように素因数分解を行う。リストが空の場合は素数ということ
    fact_list = []
    for p in range(2, int(math.sqrt(n)) + 1):
        e = 0
        while n % p == 0:
            n //= p
            e += 1
        if e > 0:
            fact_list.append((p, e))
    if n != 1:
        fact_list.append((n, 1))
    return fact_list


prime_list = prime_factorization(N)
if len(prime_list) == 0:
    print(0)
else:
    count = 0
    for p, e in prime_list:
        a = 1
        sum_a = 0
        while True:
            sum_a += a
            if e < sum_a:
                break
            a += 1
        count += a - 1
    print(count)

Submission status: Accepted

Solution code:
def gen_prime_decompositon(n):
    x = n
    d = 2
    cnt = 0
    while x % d == 0:
        x //= d
        cnt += 1
    if cnt != 0: yield cnt

    d = 3
    while d * d <= n:
        cnt = 0
        while x % d == 0:
            x //= d
            cnt += 1
        if cnt != 0: yield cnt
        d += 2

    if x > 1:
        yield 1


def main():
    from bisect import bisect_left
    from itertools import accumulate

    N = int(input())

    *acc, = accumulate(range(1, 40 + 1))

    ans = 0
    for cnt in gen_prime_decompositon(N):
        ans += bisect_left(acc, cnt + 1)  # acc上でcnt未満の個数=引ける回数

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def prime_f(n,p=2):
    if n==1:
        return []
    while True:
        if n<p**2:
            return [n]
        if n%p==0:
            l=prime_f(n//p,p)
            l.append(p)
            return l
        p+=1


def histo_list(lis):
    if lis==[]:
        return []
    new=[[lis[0],1]]
    d=lis[0]
    for c in range(1,len(lis)):
        if lis[c]!=d:
            new.append([lis[c],1])
            d=lis[c]
        else:
            new[-1][1]+=1
    return new


n=int(input())
a=prime_f(n)
a=a[::-1]
b=histo_list(a)
c=[b[x][1] for x in range(len(b))]
s=0
for x in c:
    s+=((8*x+1)**0.5-1)//2
print(int(s))

Submission status: Accepted

Solution code:
from collections import Counter
 
def factorize(n):
    a = 2
    fct = []
    while a*a <= n:
        # print('-------')
        while n % a == 0:
            n = n // a
            fct.append(a)
        a += 1
    if n > 1:
        fct.append(n)
    return fct
 
 
n = int(input())
c = Counter(factorize(n))
# print(factorize(n))
# print(c.values())


ans = 0
for v in c.values():
    t = 1
    while v >= t:
        v -= t
        t += 1
        ans += 1
print(ans)

Submission status: Accepted

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

n = int(input())
pl = factorization(n)
if len(pl) == 0: exit(print(0))
count = 0
for a,b in pl:
    if a==1 and b==1: exit(print(0))
    t=1
    while True:
        if b < t: break
        count += 1
        b-=t
        t+=1
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):
    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
#                temp = (temp+0.5)//i
            arr.append([i, cnt])

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

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

    return arr

fact_N = factorization(N)
#fact_N = np.array(fact_N)
#num_sosuu = fact_N[:,1]

num_sosuu = []
for row in fact_N:
    num_sosuu.append(row[1])

#num_sosuu_max = num_sosuu.max()
#num_sosuu_max = max(num_sosuu)

ans = 0
for i in range(len(num_sosuu)):
    num_i = num_sosuu[i]
#    for j in range(np.uint64(np.sqrt(2*num_sosuu_max))):
#    for j in range(int((2*num_sosuu_max)**0.5)):
    j = 0
    judge = True
    while judge:
        if num_i >= j+1:
            ans += 1
            num_i -= j+1
            j+=1
        else:
#            break
            judge = False

if N == 1:
    ans = 0
    
print(str(ans))

Submission status: Accepted

Solution code:
N = int(input())

# import math
#
# def sieve_of_eratosthenes(n):
#     candidate = [i for i in range(2, n+1)]
#     prime = []
#     limit = math.sqrt(n) + 1
#
#     while True:
#         p = min(candidate)
#         if limit <= p:
#             prime.extend(candidate)
#             break
#         prime.append(p)
#
#         candidate = [i for i in candidate if i % p != 0]
#
#     return prime
#
#
# if N == 1:
#     print(0)
#     exit()
#
# rn = math.ceil(math.sqrt(N))
# L = sieve_of_eratosthenes(rn)
# print('hoge')
#
# n = N
# c = 0
# used = {}
#
# for l in L:
#     if n % l == 0:
#         i = 1
#         l2 = l
#         while n % l2 == 0:
#             c += 1
#             i += 1
#             used[l2] = True
#             n = n // l2
#             l2 = l ** i
#
# if c == 0:
#     print(1)
# else:
#     if n != 1:
#         # x = sieve_of_eratosthenes(n)
#         if n not in used:
#             c += 1
#     print(c)

# if N == 1:
#     print(0)
#     exit()
#
# ans = 0
# used = {}
#
# n = N
# i = 1
# p = 2
# while n % p == 0:
#     ans += 1
#     n = n // p
#     used[p] = True
#     i += 1
#     p = 2**i
#
#
# i = 1
# p = 3
# k = p
# while p * p <= N:
#     while n % k == 0:
#         if k in used:
#             i += 1
#             k = k ** i
#         else:
#             ans += 1
#             i += 1
#             n = n // k
#             used[k] = True
#             k = k ** i
#     i = 1
#     p += 2
#     k = p
#
# if n not in used and n != 1:
#     ans += 1
# print(ans)

def factorize(n):
    a = []
    # 2で割り切れるまでnを割り続ける
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    # 3からはじめて各奇数で割り切れるまでnを割り続ける
    # nの最大約数は√nなので、f*fで計算
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

fs = factorize(N)

from collections import Counter
c = Counter(fs)

ans = 0
i = 1
for k, v in c.items():
    k2, v2 = k,v
    while v2 >= i:
        ans += 1
        v2 -= i
        i += 1
    i = 1

print(ans)