Problem:


Score : 400 points

Problem Statement

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

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

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

z divides N;

z is different from all integers chosen in previous operations.

Then, replace N with N/z.

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

Constraints

All values in input are integers.

1 \leq N \leq 10^{12}

Input

Input is given from Standard Input in the following format:

N

Output

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

Sample Input 1

24

Sample Output 1

3

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

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

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

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

Sample Input 2

1

Sample Output 2

0

We cannot apply the operation at all.

Sample Input 3

64

Sample Output 3

3

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

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

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

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

Sample Input 4

1000000007

Sample Output 4

1

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

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

Sample Input 5

997764507000

Sample Output 5

7



Sample input:
24


Sample output:
3

Submission status: Accepted

Solution code:
n = int(input())

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

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

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

    if arr == [[1, 1]]:
        return []
    else:
        return arr

prime_factor = factorization(n)

result = 0

for _, count in prime_factor:
    i = 1
    while count >= i:
        result += 1
        count -= i
        i += 1

print(result)

Submission status: Accepted

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

def gen_primes():
    D = {}
    q = 2
    while True:
        if q not in D:
            yield q
            D[q * q] = [q]
        else:
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]

        q += 1
PRIMES=[]

for p in gen_primes():
    if p < 1000000:
        PRIMES.append(p)
    else:
        break

N=II()
cnt = 0
for PR in PRIMES:
    for i in range(1,64):
        v = PR**i
        if N % v == 0:
            # print("PR:{} i:{}".format(PR, i))
            cnt += 1
            N //= v
            # print(N)
        else:
            while N % PR == 0: N //= PR
            break

# print(N)
if N > 1: cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import math 
  
def formula(y):
    return int(((8 * y + 1) ** 0.5 - 1) / 2)

def factorize(n): 
    count = 0; 
    ans = 0
    while ((n % 2 > 0) == False):  
          
        n >>= 1;  
        count += 1; 
  
    if (count > 0): 
        ans += formula(count)
  
    for i in range(3, int(math.sqrt(n)) + 1): 
        count = 0; 
        while (n % i == 0):  
            count += 1; 
            n = int(n / i); 
        if (count > 0): 
            ans += formula(count)
        i += 2; 
  
    if (n > 2): 
        ans += 1
    return ans

n = int(input())            
print(factorize(n))

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

d = []
for i in range(1, 40):
    for j in range(i+1):
        d.append(i)

lis = prime_factorize(n)
lis_s = set(lis)
ans = 0
for el in lis_s:
    ans += d[lis.count(el) - 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
ans = 0

if(N>1):
    Q = factorization(N)
    A = [ b for [a,b] in Q]
    for a in A:
        i = 1
        while(a >= i):
            a -= i
            i += 1
            ans += 1
    print(ans)

else:
    print(0)

Submission status: Accepted

Solution code:
N = int(input())

def fac(n):
    org = n

    fac = []
    i = 2
    while i * i <= org:
        if n % i == 0:
            ex = 0 # 指数
            while n % i == 0:
                ex += 1
                n //=  i
            fac.append([i, ex])
        i += 1

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

def k(c):
    d = (1 + 8*c) ** (1/2)
    return (d - 1) / 2

print(sum(int(k(i[1])) for i in fac(N)))

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)

ans = 0
for a in A:
    cnt = 1
    b = a[1]
    while (b-cnt) >= 0:
        b -= cnt
        cnt += 1
        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())

arr = factorization(N)
cdic = {}
for ar in arr:
  cdic[ar[0]] = 1
  sum = 1
  while sum+cdic[ar[0]]+1 <= ar[1]:
    #print(cdic[ar[0]], sum)
    sum += cdic[ar[0]]+1
    cdic[ar[0]] += 1
ans = 0
for c in cdic.values():
  ans += c

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

Submission status: Accepted

Solution code:
def resolve():
    import sys
    input = sys.stdin.readline
    # 整数 1 つ
    N = int(input())
    # 整数複数個
    # a, b = map(int, input().split())
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    P = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    # A = [list(map(int, input().split())) for i in range(H)]

    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

    List = factorization(N)
    #sosuList = [List[i][0] for i in range(len(List))]

    numList = []
    for x in List:
        for i in range(1, x[1]+1):
            numList.append(x[0]**i)

    numList = sorted(numList)
    num = N
    cnt = 0
    if N != 1:
        for i in numList:
            if num % i == 0:
                num = num // i
                cnt += 1
                if num == 1:
                    break

    print(cnt)

resolve()

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

P = factorization(N)

flag = 0

for i in range(len(P)):
  for j in range(40):
    P[i][1] = P[i][1] - (j + 1)
    if P[i][1] >= 0:
      flag += 1
    else:
      break
if N == 1:
  print(0)
else:
  print(flag)

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
  
fact = factorization(N)

import math

ans = 0

if N != 1:

    for f in fact:

        X = f[1]
        n = math.ceil(math.sqrt(2*X) - 1)
        if n * (n+1) > 2*X:
            n = n-1

        ans += n

print(ans)

Submission status: Accepted

Solution code:
# 2130~
N=int(input())
# まず素因数分解する．素因数の指数に対して-1,-2,-3と指定していき，素因数の指数が0より小さくなった時点で中止する
# それぞれの素因数についてその数を数え上げて足し算をすれば，それが最大の操作回数である
# まず素因数を求める
A = {}
while N%2 == 0:
    if not 2 in A:
        A[2]=1
    else:
        A[2]+=1
    N /= 2

f=3
while f*f <= N:
    if N % f == 0:
        if not f in A:
            A[f] = 1
        else:
            A[f] += 1
        N /= f
    else:
        f += 2

if N != 1:
    if N in A:
        A[N] += 1
    else:
        A[N] = 1

ans = 0
for k,v in A.items():
    ind = 1
    while not v<ind:
        v -= ind
        ans += 1
        ind += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

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

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

    return arr

fact = factorization(N)
cnt = 0

for value in fact.values():
    tmp = 3
    next_num = 3
    tmp_cnt = 1
    while tmp <= value:
        tmp += next_num
        next_num += 1
        tmp_cnt += 1
    

    cnt += tmp_cnt
    
print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

n = int(input())
d = prime_factrize(n)
ans = 0
for x in d.values():
    y = 0
    for k in range(1, x + 1):
        y += k
        if y + k >= x:
            break
    ans += k
print(ans)

Submission status: Accepted

Solution code:
import math
from collections import defaultdict
N = int(input())
d = defaultdict(int)
tmp = N
for i in range(2, int(math.sqrt(N))+1):
    while tmp % i == 0:
        d[i] += 1
        tmp /= i

if tmp > 1:
    d[tmp] += 1
ans = 0
for key, value in d.items():
    i = value
    j = 1
    while value >= j:
       ans += 1
       value -= j
       j += 1
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, n

a, n = prime_factorize(N)
c = Counter(a)
ans = 0
for v in c.values():
    for i in range(1, N):
        if v < i: break
        v -= i
        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
soinsu = factorization(int(input()))
if soinsu[0][0]==1:
  print(0)
  exit()
answer=0
for i in range(len(soinsu)):
  x = soinsu[i][1]
  j = 0
  while x >= 0 :
    j+=1
    x -= j
  else:answer += j-1
print(answer)

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())
arr=factorization(n)
ans=0
if n==1:
    print(0)
else:
    for i in arr:
        tmp=i[1]
        cnt=1
        while tmp>=0:
            tmp-=cnt
            cnt+=1
            #print(tmp,cnt)
        ans+=cnt-2
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())

def solve(n):
    ans = []
    tmp = n
    for i in range(2, int(np.sqrt(n))+1):
        if tmp%i == 0:
            cnt = 0
            while tmp%i==0:
                cnt += 1
                tmp //= i
            ans.append(cnt)
    if tmp != 1:
        ans.append(1)
    return ans

a = solve(N)

def z_num(k):
    tmp = 1
    d = 2
    while True:
        if tmp <= k and tmp+d > k:
            return d-1
        tmp += d
        d += 1
    
b = list(map(z_num, a))
b = np.array(b)

ans = int(b.sum())

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

soinsu_list = prime_factorize(N)
sosu_list = collections.Counter(soinsu_list)
count = 0

for k, v in sosu_list.items():
  i = 1
  _v = v
  while _v - i >= 0:
    count+=1
    _v-=i
    i+=1
print(count)

Submission status: Accepted

Solution code:
from math import floor,ceil,sqrt
import fractions
from collections import deque
import itertools
from collections import deque
import heapq
N=int(input())
l=[]
pf={}
m=N
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1
#print(pf)
keys=list(pf.keys())
values=list(pf.values())
for i in range(len(keys)):
    l.append([keys[i],values[i]])
#print(l)	#これでlistになった
num=[i*(i+1)//2 for i in range(40)]
#print(num)
ans=0
for i in range(len(l)):
    for j in range(39):
        if num[j]<=l[i][1]<num[j+1]:
            ans=ans+j
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
factor = dict()
if N%2 == 0:
    factor[2] = 0
    while N%2 == 0:
        factor[2] += 1
        N/=2
f = 3
while f**2 <= N:
    if N%f == 0:
        factor[f] = 0
        while N%f == 0:
            factor[f] += 1
            N/= f
    else:
        f += 2
p = len(factor.values())
ans = 0
for k in range(p):
    A = list(factor.values())[k]
    for l in range(1,100):
        A -= l
        if A < 0:
            break
        ans += 1
if N != 1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import collections


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


def main():
    n = int(input())
    factor_counts = collections.Counter(prime_factorize(n))

    result = 0

    for _, c in factor_counts.items():
        current_c = c
        n = 1
        while current_c >= n:
            current_c = current_c - n
            result += 1
            n += 1

    print(result)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def task(n):
    if n == 1:
        print(0)
        return

    primes = {}
    i = 2
    while i < 1000001 and i <= n:
        if n % i == 0:
            n = n // i
            if not i in primes:
                primes[i] = 0
            primes[i] += 1
        else:
            i += 1

    # print(primes)
    ans = 0

    if n > 1:
        ans = 1

    for prime in primes:
        e = 1
        count = primes[prime]
        while count >= e:
            count -= e
            e += 1
            ans += 1

    print(ans)


n = int(input())
task(n)

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 sum_n(n):
    return int(n*(1+n)/2)


N = int(input())

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

fac = factorization(N)


count = 0

for i in range(len(fac)):
    j = 0
    while (True):
        j += 1
        if (sum_n(j) == fac[i][1]):
            break
        elif (sum_n(j) > fac[i][1]):
            j = j - 1
            break

    count += j

print(count)

Submission status: Accepted

Solution code:
from collections import deque


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())
if n == 1:
    print(0)
    exit()
d = factorization(n)
d = deque(d)
count = 0
while d:
    m = 1
    a = d.popleft()
    while a >= m:
        a = a - m
        m += 1
        count += 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))

l = len(list(c.keys()))
it = list(c.values())

ans = 0

#print(it)

for i in range(l):
    p = 1
    while (it[i] - p >= 0):
        it[i] -= p
        ans += 1
        p += 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())
e = factorization(n)
cnt = 0
if n != 1:
  for i in range(len(e)):
    curr_num = e[i][1]
    curr_val = 1
    while curr_val * (curr_val + 1) / 2 < curr_num:
      curr_val += 1
    if curr_val * (curr_val + 1) / 2 > curr_num:
      curr_val -= 1
    cnt += curr_val

print(cnt)

Submission status: Accepted

Solution code:
import math

n = int(input())

tmpn = n

dic = dict([])

for i in range(2, int(math.sqrt(n))+1):
    if tmpn%i == 0 and tmpn/i > 0:
        divided = True
        while divided:
            tmpn = tmpn/i
            if i in dic.keys():
                dic[i] += 1
            else:
                dic[i] = 1
            if tmpn != 1 and tmpn not in dic.keys():
                dic[int(tmpn)] = 1
            if tmpn%i == 0 and tmpn/i > 0:
                divided = True
            else:
                divided = False

keyls = list(dic.keys())

# print (keyls)

for key1 in keyls:
    for key2 in keyls:
        if key1 < key2:
            if key2%key1 == 0 and key2/key1 > 0:
                if key2 in dic.keys():
                    dic.pop(key2)

if len(dic.keys()) == 0 and n != 1:
    ans = 1
else:
    ans = 0
    for key in dic.keys():
        num = dic[key]
        i = 1
        while num > 0:
            num -= i
            if num >= 0:
                ans += 1
            i += 1

print(ans)
# print(dic)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math

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

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

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

    return arr

if __name__ == '__main__':
    # スペース区切りの整数の入力
    #N, K = map(int, input().split())
    # 文字列の入力
    N = int(input())
    #開業されたN個要素を受け付ける
    #input_list = [list(map(int, input().split())) for i in range(N)]
    factor = factorization(N)
    #print(factor)

    ans = 0
    if N == 1:
        ans = 0
    else:
        for f in factor:
            g = f[1]
            i = 1
            while(g>=i):
                ans = ans+1
                g=g-i
                i=i+1
    print(ans)

Submission status: Accepted

Solution code:
'''     ##     ##  #######  # #  ######
        ##     ##  ##   ##  ###    ##
        ##     ##  ##    #  # #    ##
        #########  #######  # #    ##    '''

import sys
import math
# sys.setrecursionlimit(10**6)

def get_ints(): return map(int, sys.stdin.readline().strip().split())
def get_array(): return list(map(int, sys.stdin.readline().strip().split()))

def printspx(*args): return print(*args, end="")
def printsp(*args): return print(*args, end=" ")
def printchk(*args): return print(*args, end=" \ ")

MODPRIME = int(1e9+7); BABYMOD = 998244353;

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

if __name__ == "__main__":
    # sys.stdin = open("input.txt","r")  # <<<  ^o^  Comment this line  ^_^  >>>
    d = {}
    n = int(input())
    i = 2
    while i * i <= n:
        if n % i == 0:
            d[i] = d.get(i, 0)
            d[i] += 1
            n //= i
        else:
            i += 1
    if n!=0 and n!=1:
        d[n] = d.get(n, 0)
        d[n] += 1
    ans = 0
    # print(d)
    for k, v in d.items():
        ans += getval(v)
    print(ans)


# #############################################################################
'''
THE LOGIC AND APPROACH IS BY ME @luctivud ( UDIT GUPTA )
SOME PARTS OF THE CODE HAS BEEN TAKEN FROM WEBSITES LIKE::
(I Own the code if no link is provided here or I may have missed mentioning it)
>>> DO NOT PLAGIARISE.
TESTCASES:
'''

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main():  #startline-------------------------------------------
    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))
    lck = list(c.keys())
    lcv = list(c.values())
    lenlcv = len(lcv)
    ans = 0
    p = 1
    for i in range(lenlcv):
        while lcv[i]-p >= 0:
            lcv[i] -= p
            ans += 1
            p += 1
        p = 1
    print(ans)
if __name__ == "__main__":
    main() #endline===============================================

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

a=factorization(n)
ans=0


#print(a)

for i in a:
  temp=1
  for j in range(1,41):
    if temp<=i:
      ans+=1
      temp+=j+1
      #print(temp)
    if temp>i:
      break

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

x = factorization(n) 

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

res = 0

for i in x:
    temp = 0
    for j in range(1,100):
        temp += j
        if i[1] < temp:
            res += (j-1)
            break

print(res)

Submission status: Accepted

Solution code:
N = int(input())

res = []
x = N
y = 2
while y*y <= x:
    while x % y == 0:
        res.append(y)
        x //= y
    y += 1
if x > 1:
    res.append(x)

ans = 0
# 10**12 < 2 ** 40
while res:
    nn = res.pop()
    ans += 1
    for i in range(2,41,1):
        cnt = res.count(nn)
        if i <= cnt:
            ans +=1
            for _ in range(i):
                res.remove(nn)
        else:
            res = [i for i in res if i != nn]

print(ans)

Submission status: Accepted

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

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 prime_judge(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)
    a = set(a)
    if len(a) == 1:
        return True
    else:
        return False

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)
    a = set(a)
    if len(a) == 1 and prime_judge(list(a)[0]):
        return True
    else:
        return False

divisors = make_divisors(N)
ans = 0
for d in divisors:
    if prime_factorize(d) and N % d == 0 and N // d > 0:
            N //= d
            ans += 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(cnt)

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

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

    return arr


ans = 0

if N == 1:
    ans = 0
else:
    l = factorization(N) 
    for i in range(len(l)):
        tmp = 1
        for j in range(40):
            if l[i] >= tmp:
                l[i] -= tmp
                ans += 1
                tmp += 1
            else:
                break
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict

sys.setrecursionlimit(10 ** 7)
# import math
# from itertools import product, accumulate, combinations, product
# import bisect# lower_bound etc
#import numpy as np
# from copy import deepcopy
#from collections import deque
#import numba
import math

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

    primes = []
    p = [0] * 1000000

    for i in range(2, 1000000):
        done = False
        m = int(i ** (1/2))
        for k in primes:
            if k > m:break
            if i % k == 0:
                done = True
                break
        if not done:
            primes.append(i)
            p[i] = 1


    count = 0

    for i in primes:
        if p[2]:
            s = i
            while True:
                if not N % s:

                    N = N // s
                    count += 1
                    s *= i

                else:break
            s = s // i
            while s > 1:
                if not N % s:
                    N = N // s
                else:
                    s = s // i


    if count == 0 and N != 1:
        print(1)
    elif N != 1:
        print(count + 1)
    else:
        print(count)



if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
arr = []
initial = int(input())
temp = initial
for i in range(2, int(-(-temp**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)

def judge(n):
  l = 1
  while n > 0:
    n -= l
    l += 1
  if n == 0:
    return l-1
  else:
    return l-2

count = 0
for i in arr:
  count += judge(i)

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

Submission status: Accepted

Solution code:
__DEUBG__ = 0

import decimal
import math
import sys
from collections import *
from itertools import *

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

if __DEUBG__:
	print(prime_factors(N))

z = set()
p = None

while N > 1:
	if __DEUBG__:
		print('while')
		print(N)
	for n in prime_factors(N):
		if p:
			if (p % n) == 0:
				p *= n
			else:
				p = n
			if p in z:
				pass
			else:
				N //= p
				z.add(p)
				p = None
				break
		else:
			p = n
			if p in z:
				pass
			else:
				N //= p
				z.add(p)
				p = None
				break
	else:
		break

print(len(z))