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: Time Limit Exceeded

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
#N=10**18
if N==1:
    print(0)
    exit()

i=2
#N=10**12
def sosuu(x):
    sosuulst=[]
    i=2
    while i<int(x**.5+1):
        for s in sosuulst:
            if i%s==0:
                break
        else:
            sosuulst.append(i)
        i+=1
    for s in sosuulst:
        if x%s==0:
            while x%s==0:
                x//=s
            if x==1:
                return(1)
            else:
                return(0)
    return(1)


c=0
lst=[]
lst2=[]
for i in range(2,int(N**.5+1)):
    if N%i==0:
        lst.append(i)
        lst2.append(N//i)
lst2.reverse()
lst+=lst2
lst.append(N)
#print(lst)
for i in lst:

    if N%i==0:

        if sosuu(i):
        #    print(N,i)
            N//=i
            c+=1
print(c)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
count=0
i=0
z=[x for x in range(2,10000) if not [t for t in range(2,x) if not x%t]]
p=1
while(n>1):
    if(i==34 and count<=1):
        break
    if(z[i]>n):
        break
    if n%(z[i]**p)==0:
        n=n//(z[i]**p)
        p+=1
        count+=1
    else:
        p=1
        i+=1
if n>1 and count==0:
    print(1)
else:
    print(count)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
ans=0
for i in range(2,n):
    if n%i==0:
        ans+=1
        n/=i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
n=int(input())
if n==1:
    print(0)
    sys.exit()
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
tmp=f(n)
ans=0
for i in tmp:
    dd=i[1]
    tt=1
    while dd>0:
        if dd-tt>=0:
            dd-=tt
            tt+=1
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

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


def get_knu(a):
    if a == 1:
        return 1
    n = 2
    while True:
        if a == (n * (n + 1)) // 2:
            return n
        n += 1


D = int(input())
p = get_prime_fact(D)

if len(p) != len(set(p)):
    res = 0
    for n in set(p):
        count = p.count(n)
        res += get_knu(count)

    print(res)
else:
    print(len(p))

Submission status: Time Limit Exceeded

Solution code:
import sys
# from collections import defaultdict
# from collections import Counter
# from queue import Queue

sys.setrecursionlimit(10000)

def solve(n, start):
    if n == 1:
        return 0

    for i in range(start, n+1):
        if n % i == 0:
            # 素因数を枯らす
            sys.stderr.write('hit: n = {}, i = {}^1\n'.format(n, i))
            sys.stderr.write('hit: {}^1\n'.format(i))
            cnt = 1
            tmp = n // i
            while(tmp % (i ** (cnt+1)) == 0):
                sys.stderr.write('hit: {}^{}\n'.format(i, cnt+1))
                tmp = tmp // (i ** (cnt+1))
                cnt += 1

            while(tmp % i == 0):
                tmp = tmp // i

            return solve(tmp, i+1) + cnt

    return 0

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

    ans = solve(N, 2)
    print(ans)

    # N, M = [int(s) for s in input().split()]

    # As = []
    # for i in range(N):
    #     tmp = int(input())
    #     As.append(tmp)

    return 0

if __name__ == '__main__':
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
# from collections import defaultdict
# from collections import Counter
# from queue import Queue

sys.setrecursionlimit(10000)

def solve(n):
    if n == 1:
        return 0

    for i in range(2, n+1):
        if n % i == 0:
            # 素因数を枯らす
            sys.stderr.write('hit: n = {}, i = {}^1\n'.format(n, i))
            sys.stderr.write('hit: {}^1\n'.format(i))
            cnt = 1
            tmp = n // i
            while(tmp % (i ** (cnt+1)) == 0):
                sys.stderr.write('hit: {}^{}\n'.format(i, cnt+1))
                tmp = tmp // (i ** (cnt+1))
                cnt += 1

            while(tmp % i == 0):
                tmp = tmp // i

            return solve(tmp) + cnt

    return 0

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

    ans = solve(N)
    print(ans)

    # N, M = [int(s) for s in input().split()]

    # As = []
    # for i in range(N):
    #     tmp = int(input())
    #     As.append(tmp)

    return 0

if __name__ == '__main__':
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
m = n

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

for i in div:
    cnt = 0
    while n%i == 0:
        cnt += 1
        n //= i
    if cnt >= 1:
        exp.append(cnt)

if n == m and m > 1:
    exp.append(1)

opr = 0
for x in exp:
    opr += int((-1+(8*x+1)**(1/2))/2)

print(opr)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import os
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from io import BytesIO, IOBase
from typing import Dict, List, Optional, Set, Tuple


def count(prime_divisors: Dict[int, int]) -> int:
    result = 0
    for e in prime_divisors.values():
        result += int((math.sqrt(1 + 8 * e) - 1) / 2)
    return result


def solve(nb: int) -> int:
    if nb == 1:
        return 0
    prime_divisors = defaultdict(int)
    while nb % 2 == 0:
        prime_divisors[2] += 1
        nb //= 2
    cur = nb
    for i in range(3, (nb + 1) // 2 + 2, 2):
        if cur == 1:
            break
        while cur % i == 0:
            prime_divisors[i] += 1
            cur //= i
    # LOG.debug((prime_divisors))
    if not prime_divisors:
        return 1
    return count(prime_divisors)


def do_job(stdin, stdout):
    "Do the work"
    LOG.debug("Start working")
    N = int(stdin.readline().strip())
    # values = []
    # for _ in range(N):
    #     values.append(stdin.readline().split())
    result = solve(N)
    print(result, file=stdout)


def print_output(testcase: int, result, stdout) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result), file=stdout)
    # 6 digits float precision {:.6f} (6 is the default value)
    # print("Case #{}: {:f}".format(testcase + 1, result), file=stdout)


BUFSIZE = 8192


class FastIO(IOBase):
    # pylint: disable=super-init-not-called, expression-not-assigned
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    # pylint: disable=super-init-not-called
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def configure_log() -> None:
    "Configure the log output"
    log_formatter = logging.Formatter("L%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(IOWrapper(sys.stderr))
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    stdin = IOWrapper(sys.stdin)
    stdout = IOWrapper(sys.stdout)
    do_job(stdin, stdout)
    stdout.flush()
    for h in LOG.handlers:
        h.flush()
    return 0


if __name__ == "__main__":
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
m = n

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

for i in div:
    cnt = 0
    while n%i == 0:
        cnt += 1
        n //= i
    if cnt >= 1:
        exp.append(cnt)

if n == m and m > 1:
    exp.append(1)

opr = 0
for x in exp:
    for i in range(x+1):
        if i*(i+1)//2 <= x < (i+1)*(i+2)//2:
            opr += i
            break

print(opr)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
counter=[0,0]
i=2
while True:
    while True:
        counter.append(0)
        if n%i==0:
            counter[i]+=1
            n/=i
        else:
            break
    if n==1:
        break
    i+=1

ans=0
for j in range(len(counter)):
    k=1
    while True:
        if counter[j]-k>=0:
            counter[j]-=k
            ans+=1
        else:
            break
        k+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = 0
count = 0

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

for i in range(2,N+1):
    if N%i == 0:
        N = N/i
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
input_line1 = input()

N = int(input_line1)
count = 0

for i in range (2,N):
    if N % i == 0:
        count += 1
        N = N / i

print(count)

Submission status: Time Limit Exceeded

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
#n = 2*10**8
n = 20001002
prime = [] # i番目の素数
is_prime = [True] * (n+1)
p = 0 # 何番目か　0-indexed
is_prime[0] = False
is_prime[1] = False
ll = 0
#print('a')
for i in range(2,n+1):
    #ll += 1
    #print(i)
    if is_prime[i] == True:
        prime.append(i) # p番目の素数はiとなる
        p += 1
        # print(ll)
        # if p == 1000*ll:
        #     print(p)
        for j in range(2*i, n+1,i):
            is_prime[j] = False # その素数の倍数のやつ

#print(sieve(n,11000000))
#print(prime)
import math
def is_prime(n):
    for i in range(2,int(math.sqrt(n)+1)):
        if n % i == 0:
            return False
    return n != 1 # 1の場合は除外

n = int(input())
if is_prime(n):
    print(1)
    exit()
cnt = 0
for v in prime:
    nya = v
    while n % v == 0:
        cnt += 1
        n //= v
        v *= nya
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = float(input())
cnt = 0
for i in range(2, int(N)):
    if N % i == 0:
        cnt += 1
        N /= i

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n = int(input())
nmax = 10**6+10
eratos = [0 for i in range(nmax+1)]
prime = []
cnt = 2
while True:
  while cnt <= nmax and eratos[cnt]:
    cnt += 1
  if cnt > nmax:
    break
  eratos[cnt] = 1
  prime.append(cnt)
  for i in range(cnt**2,nmax+1,cnt):
    eratos[i] = 1
pr = []
while n > 1:
  for i in prime:
    while n%i == 0:
      n //= i
      pr.append(i)
c = Counter(pr)
ans = 0
for i in c.values():
  for j in range(10):
    if i < j*(j+1)//2:
      ans += j-1
      break
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

#import
import math
#import numpy as np
N = int(input())
#= input()
#= map(int, input().split())
#= list(map(int, input().split()))
#= [input(), input()]
#= [list(map(int, input().split())) for _ in range(N)]
#= [int(input()) for _ in range(N)]
#= {i:[] for i in range(N)}

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

res = factorization(N)

li = [0] * 101
for i in range(1, 101):
    li[i] = li[i - 1] + i

ans = 0
for r in res:
    if r[0] == 1:
        continue
    i = 0
    while li[i] <= r[1]:
        i += 1
    ans += i - 1

print(ans)

Submission status: Accepted

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

N = int(input())
dic = factrization_prime(N)
ans = 0
for d in dic.keys():
    x = dic[d]
    minus = 1
    while(x>0):
        x -= minus
        minus += 1
        if x >= 0:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
primes = {}
for num in range(2, int(N**0.5)+1):
  while N%num == 0:
    if num in primes:
      primes[num] += 1
    else:
      primes[num] = 1
    N //= num
ans = 0
for p in primes.values():
  n = 1
  while n*(n+1)//2 <= p:
    n += 1
  ans += n-1
if N > 1:
  ans += 1
print(ans)

Submission status: Accepted

Solution code:
import math
n=int(input())
def fac(n):
    arr=[]
    temp=n
    for i in range(2,math.ceil(math.sqrt(n)+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
l=fac(n)
if n==1:
    print(0)
else:
    ans=0
    for i in range(len(l)):
        count=l[i][1]
        p=0
        k=1
        while count>0:
            if count-k<0:
                break
            p+=1
            count-=k
            k+=1
        ans+=p
    print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
#from operator import itemgetter
#from heapq import heappush, heappop
#import numpy as np
#from scipy.sparse.csgraph import breadth_first_order, depth_first_order, shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix
#from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
import sys

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

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 = ni()
res = factorization(N)
ans = 0
sum_ = [x for x in range(1, 200)]
for i in range(len(sum_)-1):
    sum_[i+1] += sum_[i]
for k, v in res:
    ans += bisect.bisect_right(sum_, v)
if N == 1:
    print(0)
else:
    print(ans)

Submission status: Accepted

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

f=factorization(n) 
l=len(f)
x=0
for i in range(l):
    x+=int((-1+math.sqrt(1+8*f[i][1]))//2)
if n==1:
    x=0
print(x)

Submission status: Accepted

Solution code:
import sys
from collections import deque, defaultdict, Counter
from itertools import accumulate, product, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush
from math import ceil, floor, sqrt, gcd, inf
from copy import deepcopy
import numpy as np
import scipy as sp

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

INF = inf
MOD = 1000000007

n = int(input())

tmp = 0
res = 0

cnt = Counter(prime_factorize(n))
for i in cnt.values():
    res += floor((-1 + sqrt(1 + 8 * i)) / 2)

print(res)

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**2 <= 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())

if N <= 1:
  print(0)
  exit()
else:
  c = collections.Counter(prime_factorize(N))

  K = [sum(range(1,i)) for i in range(2,11)]
  # = [1, 3, 6, 10, 15, 21, 28, 36, 45]
 
  for i in c:
    for j in range(1,len(K)):
      if c[i] < K[j]:
        count += j
        break

  print(count)

Submission status: Accepted

Solution code:
n = int(input())

m = n
p = 2
res = 0
st = [0 for i in range(100)]
for i in range(100):
    if i * (i + 1) // 2 >= 100:
        break
    st[i * (i + 1) // 2] = i
for i in range(1, 100):
    st[i] = st[i - 1] if st[i] == 0 else st[i]
#print(st)
while p * p <= n:
    l = 0
    while m % p == 0:
        m //= p
        l += 1
    res += st[l]
    #print(p, res, l)
    p += 1
res += m > 1
print(res)

Submission status: Accepted

Solution code:
N = int(input())
div = 2
dic = {}
while div**2 <= N:
  if N % div == 0:
    count = 0
    while N % div == 0:
      N = N // div
      count += 1
    dic[div] = count
  div += 1
if N != 1:
  dic[N] = 1
ans = 0
for v in dic.values():
  tmp = 1
  while v >= tmp:
    v -= tmp
    tmp += 1
    ans += 1
print(ans)

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
l=prime_factorize(N)
L=set(l)
z=0
for j in L:
  i=1
  while i*(i+1)//2<=l.count(j):
    i+=1
  z+=i-1
print(z)

Submission status: Accepted

Solution code:
from collections import Counter

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


def main():

    N = int(input())
    cnt = Counter(prime_factorize(N))
    # stock = {k : 1 for k in cnt}
    ans = 0
    for prime in cnt:
        needed = 1
        while cnt[prime] >=needed:         
            ans += 1
            cnt[prime] -= needed
            needed += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

n=int(input())
if n==1:
  print(0)
  exit()
ans=0
for i in factorization(n):
  if i[1]>=3:
    cnt=1
    while i[1]-cnt>cnt:
      ans+=1
      i[1]-=cnt
      cnt+=1
    if i[1]!=0:
      ans+=1
  else:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
def sep():
    return map(int,input().strip().split(" "))
def lis():
    return list(sep())

#a module for any prime implication
import random

def primesbelow(N):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    #""" Input N>=6, Returns a list of primes, 2 <= p < N """
    correction = N % 6 > 1
    N = {0:N, 1:N-1, 2:N+4, 3:N+3, 4:N+2, 5:N+1}[N%6]
    sieve = [True] * (N // 3)
    sieve[0] = False
    for i in range(int(N ** .5) // 3 + 1):
        if sieve[i]:
            k = (3 * i + 1) | 1
            sieve[k*k // 3::2*k] = [False] * ((N//6 - (k*k)//6 - 1)//k + 1)
            sieve[(k*k + 4*k - 2*k*(i%2)) // 3::2*k] = [False] * ((N // 6 - (k*k + 4*k - 2*k*(i%2))//6 - 1) // k + 1)
    return [2, 3] + [(3 * i + 1) | 1 for i in range(1, N//3 - correction) if sieve[i]]

smallprimeset = set(primesbelow(100000))
_smallprimeset = 100000
def isprime(n, precision=7):
    # http://en.wikipedia.org/wiki/Miller-Rabin_primality_test#Algorithm_and_running_time
    if n < 1:
        raise ValueError("Out of bounds, first argument must be > 0")
    elif n <= 3:
        return n >= 2
    elif n % 2 == 0:
        return False
    elif n < _smallprimeset:
        return n in smallprimeset


    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1

    for repeat in range(precision):
        a = random.randrange(2, n - 2)
        x = pow(a, d, n)

        if x == 1 or x == n - 1: continue

        for r in range(s - 1):
            x = pow(x, 2, n)
            if x == 1: return False
            if x == n - 1: break
        else: return False

    return True

# https://comeoncodeon.wordpress.com/2010/09/18/pollard-rho-brent-integer-factorization/
def pollard_brent(n):
    if n % 2 == 0: return 2
    if n % 3 == 0: return 3

    y, c, m = random.randint(1, n-1), random.randint(1, n-1), random.randint(1, n-1)
    g, r, q = 1, 1, 1
    while g == 1:
        x = y
        for i in range(r):
            y = (pow(y, 2, n) + c) % n

        k = 0
        while k < r and g==1:
            ys = y
            for i in range(min(m, r-k)):
                y = (pow(y, 2, n) + c) % n
                q = q * abs(x-y) % n
            g = gcd(q, n)
            k += m
        r *= 2
    if g == n:
        while True:
            ys = (pow(ys, 2, n) + c) % n
            g = gcd(abs(x - ys), n)
            if g > 1:
                break

    return g

smallprimes = primesbelow(1000) # might seem low, but 1000*1000 = 1000000, so this will fully factor every composite < 1000000
def primefactors(n, sort=False):
    factors = []

    for checker in smallprimes:
        while n % checker == 0:
            factors.append(checker)
            n //= checker
        if checker > n: break

    if n < 2: return factors

    while n > 1:
        if isprime(n):
            factors.append(n)
            break
        factor = pollard_brent(n) # trial division did not fully factor, switch to pollard-brent
        factors.extend(primefactors(factor)) # recurse to factor the not necessarily prime factor returned by pollard-brent
        n //= factor

    if sort: factors.sort()

    return factors

def factorization(n):
    factors = {}
    for p1 in primefactors(n):
        try:
            factors[p1] += 1
        except KeyError:
            factors[p1] = 1
    return factors

totients = {}
def totient(n):
    if n == 0: return 1

    try: return totients[n]
    except KeyError: pass

    tot = 1
    for p, exp in factorization(n).items():
        tot *= (p - 1)  *  p ** (exp - 1)

    totients[n] = tot
    return tot

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

n=int(input())
k=factorization(n)
ar=k.values()
ans=0

def find(i):
    j=1
    while((j*(j+1))//2 <= i):
        j+=1
    return j-1


for i in ar:
    ans+=find(i)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
import math

N = int(input())
c = Counter()

for i in range(2, math.ceil(math.sqrt(N)+1)+1):
    while N%i == 0:
        c.update([i])
        N = N // i
if N!=1: c.update([N])
            
def R(n):
    ret = 0
    for i in range(1, n+1):
        if n>=i:
            ret += 1
            n -= i
        else:
            break
    return ret
 
ans = 0
for n in c:
    ans += R(c[n])
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

q = factorization(n)

ans = 0
for i in range(len(q)):
    l = q[i][1]
    if q[i][0] == 1:
        continue

    for j in range(1,l+1):
        l -= j
        if l < 0:
            break
        else:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
from math import sqrt
n=int(input())
t=0
i=2
while i*i<=n:
  if n%i==0:
    c=0
    while n%i==0:
      n//=i
      c+=1
    t+=(int(sqrt(8*c+1))-1)//2
  i+=1
if n>1:
  t+=1
print(t)

Submission status: Accepted

Solution code:
def division(n):
    if n < 2:
        return []
    prime_fac = []
    for i in range(2,int(n**0.5)+1):
        cnt = 0
        while n % i == 0:
            n //= i
            cnt += 1
        if cnt!=0:prime_fac.append((i,cnt))
    if n > 1:
        prime_fac.append((n,1))
    return prime_fac

n = int(input())
div = division(n)
ans = 0
for i,e in div:
    b = 1
    while b <= e:
        e -= b
        b += 1
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import math
import collections


def main():
    N = int(input())
    if N == 1:
        print(0)
        exit()
    limit = math.sqrt(N)
    vals = []
    i = 2
    while True:
        if i > limit:
            break
        if N % i == 0:
            vals.append(i)
            N //= i
        else:
            i += 1
    if N != 1:
        vals.append(N)
    c = collections.Counter(vals)
    ans = 0
    for v, freq in c.items():
        i = 0
        while True:
            i += 1
            freq -= i
            if freq < 0:
                break
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

def factorization(n: int) -> list:
    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 main():
    n = int(input())
    if n == 1:
        print(0)
        return
    factors = factorization(n)
    ans = 0

    for _, e in factors:
        ei = 1
        while ei <= e:
            e -= ei
            ei += 1
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

def factorization(n: int) -> list:
    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 main():
    n = int(input())
    if n == 1:
        print(0)
        return
    factors = factorization(n)
    ans = 0

    for _, e in factors:
        ei = 1
        ans += 1
        while ei < e:
            e -= ei
            ei += 1
            if ei <= e:
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()