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

N = int(input())
ans = 0
for _, cnt in factorization(N):
    i = 1
    while i<=cnt:
        ans += 1
        cnt -= i
        i += 1

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
def prime(n):
  dic={}
  f=2
  m=n
  while f*f<=m:
    r=0
    while n%f==0:
      n//=f
      r+=1
    if r>0:
      dic[f]=r
    f+=1
  if n!=1:
    dic[n]=1
  return dic

def counter(dic):
  ans=0
  for val in dic.values():
    i=1
    while i*(i+3)/2<val:
      i+=1
    ans+=i
  return ans

print(counter(prime(n)))

Submission status: Accepted

Solution code:
n = int(input())

d = 2
ans = 0

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

    z = d
    
    while n % z == 0:
        n //= z
        z *= d
        ans += 1

    while n % d == 0:
        n //= d

if n != 1:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
c = 0
b = [0]*1000
p = 0
while N % 2 == 0:
  b[p] += 1
  N //= 2
if b[p]!=0:
  p += 1
i = 3
while i * i <= N:
  if N % i == 0:
    b[p] += 1
    N //= i
  else:
    i += 2
    if b[p]!=0:
      p += 1
if N==i:
  b[p] += 1
  N //= i
if N!=1:
  p += 1
  b[p] += 1
for v in b:
  for i in range(1,v+1):
    if i<=v:
      c += 1
      v -= i
    else:
      break
print(c)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


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


# 実装を行う関数
def resolve(test_def_name=""):
    n = int(input())

    target_s = factorization(n)

    # 素因数1だけ処理対象外。
    if sum([i[1] for i in target_s]) == 1:
        if target_s[0][0] == 1:
            print(0)
        else:
            print(1)
        return

    # 少ない物から使っていく。
    cnt = 0
    for i in range(1, 1000):

        if not any([True if j[1] >= i else False for j in target_s]):
            break

        for target in target_s:
            if target[1] < i:
                continue
            target[1] -= i
            cnt += 1

    print(cnt)


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """24"""
        output = """3"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """1"""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """64"""
        output = """3"""
        self.assertIO(test_input, output)

    def test_input_4(self):
        test_input = """1000000007"""
        output = """1"""
        self.assertIO(test_input, output)

    def test_input_5(self):
        test_input = """997764507000"""
        output = """7"""
        self.assertIO(test_input, output)

    def test_1original_1(self):
        test_input = """108"""
        output = """3"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
import os

N = int(input())

def prime_fact(value):
    """
    素因数分解を行う関数
    Args:
        value: 素因数分解を行う値
    Returns:
        素因数分解を行った数値リスト
    """
    import math
    prime_list = {}
    prime = 2
    loop_num = 0
    while 1:
        if int(math.sqrt(value))+100<loop_num:
            prime_list[int(value)] = 1
            break
        if value%prime==0:
            value/=prime
            if prime in prime_list.keys():
                prime_list[prime]+=1
            else:
                prime_list[prime]=1
        else:
            prime+=1
        if value == 1:
            break
        loop_num+=1
    return prime_list

def sieve(max_num):
    """
    ある値までの素数を発見する関数
    Args:
        max_num: 素数の最大値
    Returns:
        ある値までの素数のリスト
    """
    droped = []
    uniqued = []
    prime_list = list(range(2, max_num+1))
    for i, current_num in enumerate(prime_list):
        if current_num in droped:
            continue
        else:
            uniqued.append(current_num)
        if i+1>=len(prime_list):
            break
        for num in prime_list[i+1:]:
            if num in droped:
                continue
            if num%current_num==0:
                droped.append(num)
    return uniqued

tmp = prime_fact(N)
result = 0
for prime, num in tmp.items():
    diff = 1
    while num>0:
        num-=diff
        if num<0:
            break
        diff+=1
        result+=1
print(result)

Submission status: Accepted

Solution code:
import math

N = int(input())

def bunkai(n):
    factor={}
    tmp = int(math.sqrt(n)) + 1
    
    for num in range(2, tmp):
        while n%num == 0:
            n /= num
            try:
                factor[num] += 1
            except:
                factor[num] = 1
    if int(n) != 1:
        factor[int(n)] = 1
    
    return factor

bunchan = bunkai(N)
ans = 0

for k in bunchan.keys():
    cnt = 1
    while bunchan[k] - cnt >= 0 :
        bunchan[k] -= cnt
        cnt += 1
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import math
n = int(input())
MAX = int(math.sqrt(n)) + 1

a = [0]*MAX

for i in range(2, MAX):
  while n % i == 0:
    n /= i
    a[i] += 1

if n != 1:
  ans = 1
else:
  ans = 0
  
for i in a:
  for j in range(MAX):
    p = int(j * (j+1) / 2)
    if i < p:
      ans += j - 1
      break
print(ans)

Submission status: Accepted

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

def factors(x: int) -> list:
    s, xx = [], x
    for i in range(2, int(x ** 0.5 + 1)):
        if xx % i == 0:
            c = 0
            while xx % i == 0: c += 1; xx //= i
            s.append((i, c))
    if xx != 1: s.append((xx, 1))
    if s == []: s.append((x, 1))
    return s

n, res = int(input()), 0
f = factors(n)
pre = [1, 3, 6, 10, 15, 21, 28, 36, 43]
flag = False
if len(f) == 1 and f[0][0] == 1: print(0); flag = True
if not flag:
    for fact in f:
        for i in range(len(pre)):
            if pre[i] > fact[1]: res += i; break
    print(res)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
def main():
    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()
    nfac = factorization(n)
    r = 0
    for nfe in nfac:
        c = 1
        while True:
            if c <= nfe[1]:
                nfe[1] -= c
                r += 1
                c += 1
            else:
                break
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())

d=2
ans=0

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

    z=d

    while n%z ==0:
        n //=z
        z *= d
        ans += 1
    
    while n % d == 0:
        n /= d

if n != 1:
    ans +=1

print(ans)

Submission status: Accepted

Solution code:
def factorization(n):
    arr = []
    temp = n
    if n<2:
        return []
    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)

    if arr==[]:
        arr.append(n)
    return arr

N = int(input())
arry = factorization(N)
ans = 0
for a in sorted(arry):
    if N%a==0:
        N //= a
        ans += 1
    if N<=1:
        break
print(ans)

Submission status: Accepted

Solution code:
#169D
#Div Game

n=int(input())

def factorize(n):
    fct=[]
    b,e=2,0
    while b**2<=n:
        while n%b==0:
            n/=b
            e+=1
        if e>0:
            fct.append([b,e])
        b+=1
        e=0
    if n>1:
        fct.append([n,1])
    return fct
l=factorize(n)
ans=0
for i in l:
    c=1
    while i[1]>=c:
        ans+=1
        i[1]-=c
        c+=1
print(ans)

Submission status: Accepted

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


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


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

Submission status: Accepted

Solution code:
n=int(input())
factors=[]
i=2
def checker(power):
    l=1
    r=20
    ans=1
    while l<=r:
        mid=l+(r-l)//2
        if mid*(mid+1)/2<=power:
            ans=mid
            l=mid+1
        else:
            r=mid-1
    return ans
while i**2<=n:
    if n%i==0:
        cnt=0
        while n%i==0:
            n/=i
            cnt+=1
        factors.append([i,cnt])
    i+=1
if n>1:
    factors.append([n,1])

res=0
rem=0
for i in range(len(factors)):
    a=checker(factors[i][1])
    res+=a
    factors[i][1]-=a
    rem+=factors[i][1]
'''if rem>1:
    res+=rem*(rem-1)/2'''
#print(factors)
print(int(res))

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
dum = prime_factorize(int(input()))
dum_len = len(dum)

num = 0
ans = 0
cnt = 0
check = 0
for i in range(dum_len):
    if num == dum[i]:
        cnt += 1
        if cnt >= check:
            check += 1
            ans += 1
            cnt = 0
    else:
        num = dum[i]
        ans += 1
        cnt = 0
        check = 2
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
r=int(n**0.5+1)
ans=0
for i in range(2,r):
  e=0
  while n%i==0:
    n//=i
    e+=1
  k=1
  while e>=k:
    e-=k
    ans+=1
    k+=1
if n!=1:
  ans+=1
print(ans)

Submission status: Accepted

Solution code:
import collections

n = int(input())

numbers = []

while n%2 == 0:
    numbers.append(2)
    n //= 2

i = 3
while i*i <= n:
    if n%i == 0:
        numbers.append(i)
        n //= i
    else:
        i += 2

if n != 1:
    numbers.append(n)

factors = collections.Counter(numbers)

ans = 0

for num in factors.values():
    k = 1
    while num >= k:
        num -= k
        ans += 1
        k += 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())
if N == 1:
    print(0)
else:
    arr = factorization(N) 
    cnt = 0
    for key in arr:
        tmp = 1
        val = key[1]
        while val > 0:
            if val - tmp > tmp:
                val -= tmp
                tmp += 1
                cnt += 1
            else:
                val = 0
                cnt += 1
            
    print(cnt)

Submission status: Accepted

Solution code:
from collections import Counter

def get_prime_factors(x):
    out = []
    if x < 1:
        return out
    while not x%2:
        out.append(2)
        x //= 2
    i = 3
    while i*i <= x:
        if not x%i:
            out.append(i)
            x //= i
        else:
            i += 2
    if x != 1:
        out.append(x)
    return out
    
def main():
    n = int(input())
    primes = Counter(get_prime_factors(n))
    ans = 0
    for prime, num in primes.items():
        i = 1
        while num >= i:
            ans += 1
            num -= i
            i += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter
def get_prime_factors(x):
    out = []
    if x < 1:
        return out
    while not x%2:
        out.append(2)
        x //= 2
    i = 3
    while i*i <= x:
        if not x%i:
            out.append(i)
            x //= i
        else:
            i += 2
    if x != 1:
        out.append(x)
    return out
def main():
    n = int(input())
    primes = Counter(get_prime_factors(n))
    ans = 0
    for prime, num in primes.items():
        i = 1
        while num >= i:
            ans += 1
            num -= i
            i += 1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter

def get_prime_factors(x):
    out = []
    if x < 1:
        return out
    while not x%2:
        out.append(2)
        x //= 2
    i = 3
    while i*i <= x:
        if not x%i:
            out.append(i)
            x //= i
        else:
            i += 2
    if x != 1:
        out.append(x)
    return out

def main():
    n = int(input())
    primes = Counter(get_prime_factors(n))
    ans = 0
    for prime, num in primes.items():
        i = 1
        while num >= i:
            ans += 1
            num -= i
            i += 1
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import sqrt
from collections import defaultdict

N = int(input())

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

def func2(k):
  n = 1
  count = 1
  while count * (count+1) // 2 <= k:
    count += 1
  return count-1

res = 0

for value in ps.values():
  if value > 0:
    res += func2(value)

print(res)

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())
F = factorization(n)
counter = 0
for a in range(len(F)):
    B = int((-1+(1+8*F[a][1])**0.5)/2)
    counter += B

if F[0][0] == 1:
    print(0)
else:
    print(counter)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from typing import Iterator

def traial_division(n: int) -> Iterator[int]:
    while not n % 2:
        yield 2
        n //= 2
    v = 3
    while v * v <= n:
        if not n % v:
            yield v
            n //= v
        else:
            v += 2
    if n != 1:
        yield n

n = int(sys.stdin.read())
c = Counter(traial_division(n))
# print(c)
ans = 0
for i, k in c.items():
    j = 1
    while k >= j:
        k -= j
        ans += 1
        j += 1
print(ans)

Submission status: Accepted

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

N = int(input().strip())
#-----

def get_divisor(n :int) -> dict:
    divisor_dic={}
    tmp_num = n

    for i in range(2, int(n**(1/2)+1) ):
        while tmp_num % i == 0:
            divisor_dic.setdefault(i,0)
            divisor_dic[i] += 1
            
            tmp_num //= i
    
    if (tmp_num != 1):
        divisor_dic[tmp_num] = 1
    
    return divisor_dic
#-----

div = get_divisor(N)
cnt =0

for num,pow in div.items():
    for p in range(1, pow+1):
        #if N % (num ** p) == 0:
        #    N /= (num ** p)
        #    cnt += 1
        
        if div[num] >= p:
            div[num] -= p
            cnt += 1


print(cnt)

Submission status: Accepted

Solution code:
import os
import sys
from collections import defaultdict, Counter
from itertools import product, permutations,combinations, accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush
from math import ceil, floor, sqrt, gcd
from copy import deepcopy

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 retuen_num(n):
    ans = 0
    count = 0
    for i in range(2,100,1):
        count += i
        if n <= count:
            ans = i - 1
            break
        
    return ans

def main():
    n = int(input())
    sosu = prime_factorize(n)
    c = Counter(sosu)
    count = 0

    for i in c.values():
        count += retuen_num(i)

    print(count)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())

    def prime_factorize(n):
        res = []
        for i in range(2, n+1):
            if i*i > n:
                break
            if n % i != 0:
                continue
            ex = 0
            while n % i == 0:
                ex += 1
                n //= i
            res.append((i, ex))
        if n != 1:
            res.append((n, 1))
        return res

    divs = prime_factorize(N)
    ans = 0
    for p, e in divs:
        d = p
        for _ in range(e):
            if N % d != 0:
                break
            N //= d
            d *= p
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections

N = int(input())


def prime_factorization(n):
    """Algorithm: trial division"""
    divs = []
    div = 2
    while n % div == 0:
        divs.append(div)
        n //= div
    div = 3
    while div ** 2 <= n:
        if n % div == 0:
            divs.append(div)
            n //= div
        else:
            div += 2
    if n != 1:
        divs.append(n)
    return divs


div_count_map = collections.Counter(prime_factorization(N))
ans = 0
for div, cnt in div_count_map.items():
    e = 1
    while e <= cnt:
        ans += 1
        cnt -= e
        e += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    from math import sqrt
    N = int(input())

    def prime_factorization(n):
        facts = []
        for i in range(2, int(sqrt(n)) + 5):
            while n % i == 0:
                n //= i
                facts.append(i)
        if n != 1:
            facts.append(n)
        return facts

    ans = 0
    facts = sorted(set(prime_factorization(N)))
    for f in facts:
        i = 1
        while N % (f**i) == 0:
            N //= f**i
            i += 1
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
c = 0
for p in range(2, int(n**0.5)+1):
  e = 0
  while n%p == 0:
    n //= p
    e += 1
  i = 1
  while e >= i:
    e -= i
    c += 1
    i += 1
if n != 1:
  c += 1
print(c)

Submission status: Accepted

Solution code:
Number=int(input())

times=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])
    
    if n==1:
        return []
    else:
        return arr


Factors=factorization(Number)
#print(Factors)

for i in Factors:
    Power=i[1]
    BiggerThan=0
    MinusPower=1
    
    while Power>BiggerThan:
        times+=1
        Power-=MinusPower
        MinusPower+=1
        BiggerThan+=1

print(times)

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)

z=0    
if n!=1:
    for i in range(len(arr)):
        k=0
        for j in range(1,100000):
            k+=j
            z+=1
            if k+j+1>arr[i][1]:
                break

print(z)

Submission status: Accepted

Solution code:
import numpy as np

n=int(input())
if n==1:
  print(0)
else:
  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
 
  y=factorization(n)
  def judge(y):
    i=1
    while np.arange(i+2).sum()<=y:
      i+=1
    return i
  ans=0
  for i in range(len(y)):
    ans+=judge(y[i][1])
  print(ans)

Submission status: Accepted

Solution code:
import math
from collections import defaultdict

def get_max_frequency(x):
  n = 1
  while True:
    if n*(n+1)/2 <= x and x < (n+1)*(n+2)/2:
      break
    n += 1
  return n

N = int(input())
divided = N
d = defaultdict(int)
ans = 0

for i in range(2, int(math.sqrt(N)//1)+1):
  while True:
    if divided%i == 0:
      divided //= i
      d[i] += 1
    else:
      break
d[divided] += 1
if 1 in d:
  del d[1]

for v in d.values():
  ans += get_max_frequency(v)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def prime_factorization(n):
    res = []
    for i in range(2, int(pow(n, 0.5))+1):
        if n % i: continue
        ex = 0
        while n % i == 0:
            n = n // i
            ex += 1
        res.append((i, ex))
    if n != 1:
        res.append((n, 1))
    return res

def solve():
    N = II()
    fact = prime_factorization(N)
    # print(fact)
    ans = 0
    for num, ex in fact:
        th = 1
        while ex >= th:
            ans += 1
            ex -= th
            th += 1
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n=int(input())
ans=0
dn=n
g={}
d=2
while d*d<=dn:
    if dn%d==0:
        if not g.get(d):g[d]=0
        while dn%d==0:dn//=d;g[d]+=1
    d+=1
if dn>1:g[dn]=1
for v in g:
    i=g[v]
    cnt=1
    while cnt<=i:i-=cnt;cnt+=1;ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2, 7, 61] if n < 1 << 32 else [2, 3, 5, 7, 11, 13,
                                        17] if n < 1 << 48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1:
            continue
        while y != n - 1:
            y = y * y % n
            if y == 1 or t == n - 1:
                return 0
            t <<= 1
    return 1


def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        def f(x): return (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g):
                return g
            elif isPrimeMR(n // g):
                return n // g
            return findFactorRho(g)


def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k:
            ret[i] = k
        i += i % 2 + (3 if i % 3 == 1 else 1)
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1:
        ret[n] = 1
    if rhoFlg:
        ret = {x: ret[x] for x in sorted(ret)}
    return ret


def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p] + 1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return sorted(ret)


N = ni()

fact_dic = primeFactor(N)

ans = 0
for k, v in fact_dic.items():
    i = 1
    while(v - i >= 0):
        ans += 1
        v -= i
        i += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n=int(input())
def soin(n):
  soin_ans=[]
  while n%2==0:
    n//=2
    soin_ans.append(2)
  f=3
  while f<=n**0.5:
    if n%f==0:
      n//=f
      soin_ans.append(f)
    else:
      f+=2
  if n!=1:
    soin_ans.append(n)
  return soin_ans
s_list=soin(n)
s_set=set(s_list)
sc=Counter(s_list)
count=0
for i in s_set:
  for j in range(1,sc[i]+1):
    if n%i**j==0:
      n//=i**j
      count+=1
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 arr==[]:
        arr.append([n, 1])

    return arr


arr = factorization(int(input()))
res = 0

if arr[0][0] != 1:
    
    for i in arr:
        cnt = 1
        while(i[1]>=cnt):
            i[1] -= cnt
            cnt += 1
            res +=1
            
print(res)

Submission status: Accepted

Solution code:
import collections
N = int(input())


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


ans = 0
for v in prime_factorize(N).values():
    for i in range(1, 100):
        if (i + 1) * (i + 2) // 2 > v:
            break
    ans += i
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())

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

lis = prime_factorize(N)

ans = 0

for v, cnt in lis:
    i = 1
    while cnt >= i:
        cnt -= i
        i += 1   
    ans += i - 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import defaultdict

N = int(input())

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

dic = defaultdict(int)
lis = prime_factorize(N)
for num in lis:
    dic[num] += 1

ans = 0

for v in dic.values():
    i = 1
    while v >= i:
        v -= i
        i += 1   
    ans += i - 1
print(ans)