Problem:


Score : 400 points

Problem Statement

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

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

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

z divides N;

z is different from all integers chosen in previous operations.

Then, replace N with N/z.

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

Constraints

All values in input are integers.

1 \leq N \leq 10^{12}

Input

Input is given from Standard Input in the following format:

N

Output

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

Sample Input 1

24

Sample Output 1

3

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

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

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

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

Sample Input 2

1

Sample Output 2

0

We cannot apply the operation at all.

Sample Input 3

64

Sample Output 3

3

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

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

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

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

Sample Input 4

1000000007

Sample Output 4

1

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

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

Sample Input 5

997764507000

Sample Output 5

7



Sample input:
24


Sample output:
3

Submission status: Accepted

Solution code:
import 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())
if N == 1:
  print(0)
  exit()
cnt = 0
insulist = factorization(N)
for i in range(len(insulist)):
  for j in range(1, insulist[i][1] + 1):
    if N % (insulist[i][0] ** j) == 0:
      N //= insulist[i][0] ** j
      cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import math
import collections

n = int(input())
s = 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

m = 0
l = collections.Counter(prime_factorize(n))
l2 = list(dict.values(l))
#for i in range(len(l2)):
#    s += int((math.sqrt(1 + 9 * l2[i])-1)/2)
for i in range(len(l2)):
    for j in range(n):
        if l2[i] >= j*(j+1)/2:
            m = j
        else:
            break


    s += m


print(s)

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
a = list()
ans = 0
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)
m = list(Counter(a).values())
for i in range(len(m)):
    j, k = 1, 1
    while m[i] >= j:
        k += 1
        j += k
        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

a = int(input())
b = factorization(a)
countation = 0
for i in range(len(b)):
    t = b[i][1]
    k = 1
    n = 1
    while t >= n:
        countation += 1
        k = k + 1
        n = k*(k+1)/2
if a != 1:
    print(countation)
else:
    print(0)

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())
ans = 0
# print(factorization(N))
for num, count in factorization(N):
    if num == 1:
        continue
    this_count = count
    start_x = 1
    while this_count - start_x >= 0:
        this_count -= start_x
        ans += 1
        start_x += 1
print(ans)

Submission status: Accepted

Solution code:
import math
n = int(input())
prime = []
insu = {}
max_itr = math.ceil(math.sqrt(n))+1
try_range = [2] + list(range(3, max_itr, 2))
for i in try_range:
    if i > max_itr:
        break
    if n%i == 0:
        flag = 0
        for p in prime:
            if i%p == 0:
                flag = 1
                break
        if flag == 0:
            prime.append(i)
            while n%i == 0:
                if i in insu:
                    insu[i] += 1
                else:
                    insu[i] = 1
                n //= i
            if n < max_itr:
                max_itr = n

if n != 1:
    insu[n] = 1
# print(insu)

count = 0
for v in insu.values():
    i = 1
    while v >= i:
        v -= i
        i += 1
        count += 1

print(count)

Submission status: Accepted

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

c = collections.Counter(prime_factorize(N))

ans = 0
for j in c:
    for i in range(1,c[j]+1):
        if c[j] == 1:
            ans += 1
        elif i*(i+1)<= 2*c[j] < (i+1)*(i+2):
            ans += i

print(ans)

Submission status: Accepted

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

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

x = make_divisors(n)[1:]
if len(x)==1:
  print(1)
  exit()

cnt = 0
numbers = []
for a in x:
  if is_prime(a):
    n //= a
    b = 2
    cnt += 1
    while n%(a**b)==0:
      numbers.append(a**b)
      b += 1
  if a in numbers:
    if n%a==0: 
      n //= a
      cnt += 1
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])
    return arr

z = factorization(int(input()))
i = 1
ans = 0
flag = True
while flag:
    flag2 = False
    for j in range(len(z)):
        if z[j][1] >= i:
            z[j][1] -= i
            ans += 1
            flag2 = True

    i += 1
    if flag2 == False: flag = False
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

a = factorization(n)

cnt = 0
for i in range(len(a)):
    tmp = a[i][1]
    for j in range(1,100):
        tmp -= j
        if tmp >= 0:
            cnt += 1
        else:
            break

print(cnt)

Submission status: Accepted

Solution code:
def f(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())
ct=0
a=f(n)
for i in range(len(a)):
    ct2=0
    ct3=1
    c=a[i][1]
    while 1:
        ct2+=ct3
        if ct2==c:
            ct+=ct3

            break
        elif ct2>c:
            ct+=ct3-1
            break
        ct3+=1
if n==1:
    ct=0
print(ct)

Submission status: Accepted

Solution code:
import collections

n=int(input())

p=n
e=1
count=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

for i in list(set(prime_factorize(n))):
    #print(i)
    e=1
    while i**e<=p:
        a=i**e
        #print("aは",a)
        #print("nは",n)
        if n%a==0:
            n=n/a
            count+=1
        e+=1

print(count)

Submission status: Accepted

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

def is_prime(num):
    if num == 2:
        return True
    elif num <  3 or num % 2 == 0:
        return False
    for i in range(3, int(math.sqrt(num)) + 1, 2):
        if num % i == 0:
            return False
    return True


c = []
for i in range(1, int(math.sqrt(n))+1):
    if n%i == 0:
        k = n//i
        if is_prime(k):
            c.append(k)
        if is_prime(i):
                c.append(i)

d = {}
ans = 0
for i in set(c):
    while n%i == 0:
        n //= i
        if i in d:
            d[i] += 1
        else:
            d[i] = 1

ans = 0
for v in d.values():
    for i in range(1, 41):
        if v >= i:
            v -= i
            ans += 1
        else:
            break
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
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

f = list(set(prime_factors(n)))
ans = 0
for i in f:
    e = 1
    while n % i**e == 0:
        n = n//(i**e)
        ans += 1
        e+=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())
A=factorization(N)
B=len(A)
k=0

for i in range(B):
    a=1
    while A[i][1]>=a*(a+1)/2:
        a+=1
    k=k+a-1
if N==1:
    print(0)
else:
    print(k)

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

arr2=factorization(n)
ans=0
for i in range(len(arr2)):
    count=1
    count2=1
    while arr2[i][1]>=count2:
        ans+=1
        count+=1
        count2+=count
if n==1:
    print(0)
else:
    print(ans)

Submission status: Accepted

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

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

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

    return arr

def get_z(factor):
    for f_list in factor:
        for i in range(f_list[1]):
            z = f_list[0] ** (i + 1)
            if z not in choice_list:
                choice_list.append(z)
                return z

choice_list = []
n = int(input())
factor = factorization(n)

while n > 1:
    z = get_z(factor)
    if z is None:
        break
#     print(z)
#     print(choice_list)
    n //= z
    factor = factorization(n)
#     print(z)
print(len(choice_list))

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(5000)
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 sum_():
    sum_list = [0]
    i = 0
    x = 1
    while(sum_list[-1] <=1000000007):
        sum_list.append(x+sum_list[i])
        i +=1
        x +=1
    # print(sum_list)
    return sum_list
N = int(input())
if(N == 1):
    print(0)
else:
    ans = 0
    sum_list = sum_()
    f = factorization(N)
    for i in range(len(f)):
        count =0
        while(sum_list[count]<=f[i][1]):
            
            count += 1
        ans += count-1
    # print(f)
    print(ans)

Submission status: Accepted

Solution code:
dim = 7
prime = [1]*(10**dim+1)
from collections import Counter
p = Counter()
p_set = []
for i in range(2,10**dim+1):
    j = i
    if prime[i] != 0:
        p[i] += 1
        p_set.append(i)
        while(j <= 10**dim):
            prime[j] = 0
            j += i

N = int(input())
cnt = 0
for n in p_set:
    if n > N:
        break
    while(1):
        if N%(n**p[n])==0:
            N //= n**p[n]
            cnt += 1
            p[n] += 1
        else:
            break
for n in p_set:
    if n > N:
        break
    while(1):
        if N%n == 0:
            N //= n
        else:
            break
if N > 1:
    cnt += 1
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(cnt)

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

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

    return arr

n = int(input())
ln = factorization(n)
ans = 0
for i in range(1, max(ln) + 1):

    ln = [x for x in ln if x >= i]
    ans += len(ln)
    ln = list(map(lambda x: x - i, ln))
    if sum(ln)==0:
        break
import sys

if n == 1:
    print(0)
    sys.exit()
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
from bisect import bisect_right
def prime_factorize_dict(n):
    d = dict()
    while not n & 1:
        d[2] = d.get(2, 0) + 1
        n >>= 1
    f = 3
    while f * f <= n:
        if not n % f:
            d[f] = d.get(f, 0) + 1
            n //= f
        else:
            f += 2
    if n != 1:
        d[n] = d.get(n, 0) + 1
    return d

N = int(input())
l = list(prime_factorize_dict(N).values())
L = list(accumulate(range(10 ** 6)))
print(sum(bisect_right(L, item) - 1 for item in l))

Submission status: Accepted

Solution code:
import math
n = int(input())
count = 0
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
kon = math.sqrt(n)
kon = math.floor(kon)+1
a = factorization(n)
sc = len(a)
if n==1:
  print(0)
else:
  for i in range(sc):
    for j in range(kon):
      if a[i-1][1]>=j+1:
        count=count+1
        a[i-1][1]=a[i-1][1]-j-1
  print(count)

Submission status: Accepted

Solution code:
import collections
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
n=int(input())
c=collections.Counter(prime_factorize(n))
d=list(c.values())
s=0
x=1
for i in d:
  while i>=x*(x+1)/2:
    s+=1
    x+=1
  x=1
print(s)

Submission status: Accepted

Solution code:
import math
import itertools
import sys

N = int(input())
N_copy = N

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


def prime_factors(n):
    # https://codereview.stackexchange.com/a/121869
    # i ranges over 2 and odd numbers 3, 5, 7, ...
    # returns each prime as many times as it divides n
    """Find prime factorization of n"""
    for i in itertools.chain([2], itertools.count(3, 2)):
        if n <= 1:
            break
        while n % i == 0:
            n //= i
            yield i

primes = {}

for p in range(2, int(math.sqrt(N))+1):
    while N % p == 0:
        N //= p
        if p in primes:
            primes[p] += 1
        else:
            primes[p] = 1

def find_k(E):
    k = 1
    while k**2 + k <= 2*E:
        k += 1
    return k-1

total = 0

# for p in range(2, N+1):
#     E = 0
#     while N % p == 0:
#         N //= p
#         E += 1
#     total += find_k(E)

# print(total)

for p in primes:
    total += find_k(primes[p])


prod = 1
for p in primes:
    prod *= p ** primes[p]

# print(prod)

if prod != N_copy:
    print(total + 1)
else:
    print(total)

# print(primes)
# if not primes:
#     print(1)
# else:
#     print(total)

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

factor = factorization(n)

ans = 0
for a in factor:
    if a[0] == 1:
        print(0)
        exit(0)
    else:
        for i in range(1,10000):
            a[1] -= i
            if a[1]>=0:
                ans += 1
            else:
                break

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n = int(input())

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

import math

prime_factorization = []

copy_n = n
for i in range(2, math.ceil(math.sqrt(n)) + 1):
    if copy_n % i != 0:
        continue
    else:
        ex = 0
        while copy_n % i == 0:
            ex += 1
            copy_n = copy_n // i
        prime_factorization.append((i, ex))
if copy_n != 1:
    prime_factorization.append((copy_n, 1))

ans = 0
memo = dict()
for p in prime_factorization:
    if p[1] in memo:
        ans += memo[p[1]]
        continue
    count = 0
    total = 1
    while total <= p[1]:
        count += 1
        memo[total] = count
        total = total + (count + 1)
    memo[p[1]] = count
    ans += count
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=p=1
while p<6**8:
 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:
import collections

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

l = collections.Counter(prime_decomposition(N))

ans = 0
for p,c in l.items():
    i = 1
    while c >= i :
        c -=i
        i += 1
        ans +=1

print(ans)

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
N = int(input())
if N==1:
    print(0)
    sys.exit(0)

s = factorization(N)
ans = 0
for i,j in s:
    k = 1
    while j-k>=0:
        j -= k
        k += 1
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def factorize(n):
    fct = []
    b, e = 2, 0
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append([b, e])
        b, e = b + 1, 0
    if n > 1:
        fct.append([n, 1])
    return fct
N=int(input())
fct = factorize(N)
count=0
if fct :
    for i in range(len(fct)):
        tmp=1
        while True:
            if fct[i][1]>=tmp:
                fct[i][1]=fct[i][1]-tmp
                tmp+=1
                count+=1
            else:
                break
    print(count)
else:
    print("0")

Submission status: Accepted

Solution code:
n = int(input())
a = set()
i = 2
res = 0
while i * i <= n:
    if (n % i) == 0:
        count = 0
        while n % i == 0:
            count += 1
            n //= i
        dif = 1
        while count >= dif:
            res += 1
            count -= dif
            dif += 1
    i += 1
if n != 1:
    res += 1
print(res)

Submission status: Accepted

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

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(n**0.5)+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
  
fact = factorization(n)
vals = []
for f in fact:
  for e in range(1, f[1]+1):
    vals.append(f[0]**e)
vals.sort()
if n==1:
  print(0)
else:
  ans = 0
  for d in vals:
    if n%d == 0:
      ans += 1
      n /= d
  print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
c = Counter(prime_factorize(N))
n = 0
for i, v in c.items():
    t = 1
    a = 2
    while t <= v:
        n += 1
        t += a
        a += 1
print(n)

Submission status: Accepted

Solution code:
import math
import sys

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]

n = int(input())

if n <= 1:
    print(0)
    sys.exit()

yakusu = set(make_divisors(n))
yakusu.discard(1)

sosu = set([min(yakusu)])
tansaku = set(yakusu)
kari = set(tansaku)



while 1:
    for var in tansaku:
        if var % max(sosu) == 0:
            kari.discard(var)
    tansaku = set(kari)
    if len(tansaku) == 0:
        break
    sosu.add(min(tansaku))
sosu = sosu | tansaku

i = 1
j = 0
kari = set(sosu)

while n != 1:
    for var in sosu:
        if n % (var ** i) == 0:
            n = n / (var ** i)
            j += 1
        else:
            kari.discard(var)
    sosu = set(kari)

    i += 1
    if i > 1000:
        break

print(j)

Submission status: Accepted

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


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

    if tmp != 1:
        retval.append([tmp, 1])
        # retval.append(tmp)
    # if not retval:
        # retval.append((n, 1))
    return retval


fact = factorization(n)
used = set()
m = len(fact)
ans = 0
left = []
# # iこずつとっていく
# for j in range(m):
#     fact[j][1] -= 1
#     ans += 1
#     used.add(fact[j][0])
#     left.extend([fact[j][0] for _ in range(fact[j][1])])

# print(left, used, ans)


for i in range(1, 1000):
    # iこずつとっていく
    for j in range(m):
        if i <= fact[j][1]:
            fact[j][1] -= i
            ans += 1
            used.add(fact[j][0]**i)
    # 組み合わせて、iこ取れるか確かめる
print(ans)

Submission status: Accepted

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

n = int(input())
if n == 1:
    print(0)
else:
    l = prime_factorize(n)
    # print(l)
    cnt = 2

    tem = l[0]
    for i in range(1, len(l)):
        if l[i] == tem:
            l[i] = tem ** cnt
            cnt += 1
        else:
            tem = l[i]
            cnt = 2

    l.sort()
    # print(l)

    cnt = 0
    i = 0
    while n != 1 and i < len(l):
        if n % l[i] == 0:
            n /= l[i]
            cnt += 1
        i += 1

    print(cnt)

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


N=int(input())

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

A=factorization(N)

numlist=range(2,50)
sinsa=1
ans=0
for i in range(len(A)):
    beki=A[i][1]
    sosu=A[i][0]
    sinsa=1
    for j in range(1,beki+1):
        N=N/(sosu**j)
        ans+=1
        sinsa=sinsa+j+1
        if sinsa>beki:
            sinsa=1
            break
print(ans)

Submission status: Accepted

Solution code:
import math
import collections


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


n = int(input())
l = trial_division(n)
if n == 1:
    print(0)
    exit(0)
if l == -1:
    print(1)
    exit(0)
if l[len(l) - 1] == 1:
    l = l[:-1]
c = collections.Counter(l)

ans = 0
for k, v in c.items():
    s = 1
    for i in range(1, v):
        if i * (i + 1) <= v * 2:
            s = max(s, i)
    ans += s
print(ans)

Submission status: Accepted

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

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

for i in factorization(n):
  for j in range(1,100000):
    if (j-1)*j<=2*i[1]<j*(j+1):
      c+=j-1
if n!=1:
  print(c)
else:
  print(0)

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))
ans=0
N=n
for k,v in c.items():
	x=v
	d=1
	while x-d>=0:
		ans+=1
		x-=d
		d+=1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

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

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

    return arr

def co(n):
  i=1
  c=0
  while True:
    n=n-i
    #print(n)
    if n>=0:
      c+=1
    else:
      break
    i+=1
  return c

a=factorization(n) 
#print(a)

ans=0
for i,j in a:
  if i==1:
    continue
  ans += co(j)

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

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

count = 0
n = int(input())
d = defaultdict(int)
ans = prime_factorize(n)
for i in ans:
    d[i] += 1
for j in d.values():
        if j < 3:
            count +=1
        elif j < 6:
            count +=2
        elif j < 10:
            count +=3
        elif j < 15:
            count +=4
        elif j < 21:
            count +=5
        elif j < 28:
            count +=6
        elif j < 36:
            count +=7
        elif j < 45:
            count +=8
        elif j < 55:
            count +=9
print(count)

Submission status: Accepted

Solution code:
N=int(input())
ans=0
p=2

while N>1 and p*p<=N:
  if N%p==0:
    c=0
    while N%p==0:
      N=N/p
      c=c+1
    Y=1
    U=2
    while c>=Y:
      ans=ans+1
      Y=Y+U
      U=U+1
  p=p+1

if N>1:
  ans=ans+1

print(ans)

Submission status: Accepted

Solution code:
import sys
import copy
import collections

# 素因数分解の結果をlistで返す
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def main():
    n = int(input())
    n_prime = prime_factorize(n)
    unique_n_prime = []
    unique_n_prime = [x for x in n_prime if x not in unique_n_prime and not unique_n_prime.append(x)]

    ans = 0
    ans += len(unique_n_prime)

    unique_c = collections.Counter(unique_n_prime)

    c = collections.Counter(n_prime)
    c = c - unique_c
    t = 1
    while len(c) > 0:
        for _ in range(t):
            c = c - unique_c
        ans += len(c)
        c = c - unique_c
        t += 1

    print(ans)



if __name__ == '__main__':
    main()

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
b=prime_factorize(N)
if b==1:
    print(0)
else:
    number=0
    c=list(set(b))
    for i in tuple(c):
        d=b.count(i)
        if 1<=d<=2:
            number+=1
        elif 3<=d<=5:
            number+=2
        elif 6<=d<=9:
            number+=3
        elif 10<=d<=14:
            number+=4
        elif 15<=d<=20:
            number+=5
        elif 21<=d<=27:
            number+=6
        elif 28<=d<=35:
            number+=7
        elif 36<=d<=45:
            number+=8
    print(number)