Problem:


Score : 400 points

Problem Statement

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

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

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

z divides N;

z is different from all integers chosen in previous operations.

Then, replace N with N/z.

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

Constraints

All values in input are integers.

1 \leq N \leq 10^{12}

Input

Input is given from Standard Input in the following format:

N

Output

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

Sample Input 1

24

Sample Output 1

3

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

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

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

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

Sample Input 2

1

Sample Output 2

0

We cannot apply the operation at all.

Sample Input 3

64

Sample Output 3

3

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

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

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

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

Sample Input 4

1000000007

Sample Output 4

1

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

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

Sample Input 5

997764507000

Sample Output 5

7



Sample input:
24


Sample output:
3

Submission status: Accepted

Solution code:
import collections

def p(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())
s = p(n)
c = collections.Counter(s)
t = list(c.values())
m = 0

for x in t:
    
    a = 1

    for j in range (100):
        if (x - a >= 0):
            x = x - a
            m = m + 1
            a = a + 1
        else:
            break

print(m)

Submission status: Accepted

Solution code:
import math,sys
ans=0
def factorization(n):
    num=0
    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])
            num=num+1
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr,num
def kirisute(n):
    p=(-1+math.sqrt(1+8*n))/2
    q=math.floor(p)
    return q
N=int(input())
if N==1:
  print(0)
  sys.exit()
soinsuu,jigen=factorization(N)
for i in range(len(soinsuu)):
  ans=ans+kirisute(soinsuu[i][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())
total = 0
if n == 1:
    pass
else:
    for i in factorization(n):
        t = 1
        while 1:
            if i[1]-t < 0:
                break
            else:
                total += 1
                i[1] -= t
                t += 1
print(total)

Submission status: Accepted

Solution code:
from collections import Counter

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

def cnt(x):
    ans = 0
    i = 1
    while True:
        ans += i
        if ans > x:
            return i-1
        i += 1
        
n = int(input())
ans = 0

a = Counter(prime_factorize(n))
for i in a.values():
    ans += cnt(i)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()

	tmp = factorize(N)
	ans = 0

	for i,val in enumerate(tmp):
		sosuu,kai = val

		tmtmtm = 1
		con = 2
		while True:
			if kai < tmtmtm:
				break
			ans += 1
			tmtmtm += con
			con += 1

	print(ans)

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

if __name__ == "__main__":
	main()

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())
l = factorization(n)
ans = 0



if n == 1:
    ans = 0
elif l[0][0] == n:
    ans = 1

else:
    l2 = []
    s = set()

    for i in l:

        for j in range(1,9999999999):
            if i[1]*2 < j*(j+1):
                ans += j-1
                break

    
print(ans)

Submission status: Accepted

Solution code:
import math
n=int(input())
def factorization(num):
    factor = []
    flag = True
    is_Prime= True
    if num == 1:
        is_Prime = False
    while num > 1 and flag:
        flag = False
        for i in range(int(math.sqrt(num))+2):
            k = i + 2
            if num % k == 0:
                factor.append(k)
                num = int(num / k)
                is_Prime = False
                flag = True
                break
    if is_Prime or num > 1:
        factor.append(num)
    return factor
a = factorization(n)
from collections import Counter
co = Counter(a)
result = 0
for k, num in co.items():
    c = 0
    for i in range(1, num+1):
        c += i
        result += 1
        if c > num:
            result -= 1
            break
print(result)

Submission status: Accepted

Solution code:
import math
N=int(input())
i=2
A=N
app=0
for i in range(2, int(N**(1/2)+1)+1):
    suma=0
    sume=0
    while A%i==0:
        A=A/i
        suma+=1
    if suma>0:
        n=(-1+(1+8*suma)**(1/2))/2
        n=math.floor(n)
        n=int(n)
        app=app+n
    suma=0
    i+=1
if A>1:
    app+=1
if app>0:
    print(app)
if app==0:
    if N>1:
        print(1)
    if N==1:
        print(0)

Submission status: Accepted

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

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

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

    return arr

N = int(input())
f = factorization(N)
count = 0
for a, b in f:
    c = 0
    for i in range(1, b+1):
        c += i
        if c > b:
            break
        else:
            count += 1
if N == 1:
    print(0)
else:
    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


if __name__=="__main__":
    N = int(input())
    count = 0
    counter = collections.Counter(prime_factorize(N))
    output = 0
    for prime in counter:
        num_prime = 1
        count = 1
        while True:
            if counter[prime] >= num_prime:
                output += 1
                count += 1
                num_prime += count
            else:
                break
    print(output)

Submission status: Accepted

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

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

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

    return arr
N = int(input())
if N == 1:
    print(0)
    exit()
count = 0
lis = factorization(N)
for l in lis:
    num = l[1]
    for i in range(1,l[1]+1):
        if i > num:
            break
        num -= i
        i += 1
        count += 1
print(count)

Submission status: Accepted

Solution code:
import math
n=int(input())
if n==1:
  print(0)
else:
  x=[]
  for i in range(2,int(math.sqrt(n)+1)):
    if n%i==0:
      x.append(i)
      if n//i!=i:
        x.append(n//i)
  x.append(n)
  x.sort()
  sosu=[]
  for i in x:
    for j in range(2,int(math.sqrt(i))+1):
      if i%j==0:
        break
    else:
      sosu.append(i)
  ans=0
  for i in x:
    if n//i>=1:
      for j in sosu:
        for k in range(1,int(math.log(i,j))+1):
          if j**k==i:
            if n%i==0:
              ans+=1
              n/=i
              break
    else:
      break
  print(ans)

Submission status: Accepted

Solution code:
def create_divisors(n):
  """
  自然数nの全ての約数を列挙したリストを作成する。

  Parameters
  ----------
  n : int
    自然数

  Returns
  -------
    divisors：list

  """
  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 factorization(n):
    """
    引数の値を素因数分解したリストを返す

    Parameters
    ----------
    n : int
        素因数分解したい自然数

    Returns
    -------
    retlist : list
        2以上の整数n => [[素因数, 指数], ...]の2次元リスト
    """
    retlist = []
    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
            retlist.append([i, cnt])

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

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

    return retlist
def isPrime(x):
  """
  xが素数か否か判定する。

  Parameters
  ----------
  x: int
      自然数

  Returns
  -------
      True:素数
      False:素数ではない
  """
  if x<2:
    return False
  for i in range(2,int(x**0.5)+1):
    if x%i==0:
      return False
  return True

n=int(input())
d=factorization(n)

p=[]
for i in range(len(d)):
  if isPrime(d[i][0]):
    p.append(d[i]) 

# print(p)
from collections import Counter
used=Counter()
ans=0
for i in range(len(p)):
  t=p[i][1]
  j=1
  t_sum=0
  while t>0 and t>=j:
    if used[p[i][0]**j]==0:
      ans+=1
    used[p[i][0]**j]+=1
    t-=j
    j+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
import collections
readline = sys.stdin.readline
 
n = int(readline().strip())
 
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)

if len(a) == 0:
  print(0)
  exit()

c = collections.Counter(a)
p = c.keys()

ans = 0
for i in p:
  v = c[i]
  m = 0
  ans += 1
  for j in range(1,v):
    m += j
    if m + j >= v:
      break
    else:
      ans += 1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import numpy
import collections
#標準出力からの読み込み
n = int(input())

#判定ロジック
#nを素因数分解
output = 0

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

prime = prime_factorize(n)
c = collections.Counter(prime)

try:
    for key, values in c.items():
        i = 1
        while values - i >= 0:
            output = output + 1
            values = values - i
            i = i + 1
except:
    pass

print(output)

Submission status: Accepted

Solution code:
import sys
import math
import random

def isPrime(q):
    if q==2:
        return True
    if q<2:
        return False
    if pow(2,q-1,q)==1:
        return True
    else:
        return False

def f(x,c,n):
    return (x**2+c)%n

def rho(n):
    x=random.randint(0,n-1)
    y=random.randint(0,n-1)
    c=random.randint(1,n-3)
    d=math.gcd(abs(x-y),n)
    while d==1:
        print(d)
        x=f(x,c,n)
        y=f(y,c,n)
        y=f(y,c,n)
        d=math.gcd(abs(x-y),n)
        if d==n:
            break

    return d


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

    P={}

    # d=rho(N)
    # P[d]=1
    #
    # while N>d:
    #     N=N//d
    #     d=rho(N)
    #     if (d in P.keys()):
    #         P[d]+=1
    #     else:
    #         P[d]=1

    if isPrime(N):
        print("1")
        sys.exit()

    for i in range(2,N):
        if N%i==0:
            P[i]=1
            N=N//i
            while N%i==0:
                N=N//i
                P[i]+=1
            if isPrime(N):
                P[N]=1
                break
        if N==1:
            break

    counter=1
    res=0
    KEY=list(P.keys())
    while len(KEY)>0:
        for i in KEY:
            if P[i]-counter>=0:
                res+=1
                P[i]=P[i]-counter
            else:
                KEY.remove(i)
                P.pop(i,None)
        counter+=1

    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from math import factorial

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


ls = factorization(n)
ans = 0

for i, j in ls:
    cnt = 0
    for i in range(1, 10*10):
        cnt += i
        if cnt > j:
            break
        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
ans = 0
n = int(input())
f = [None for _ in range(40)]
f[1] = 1
for i in range(2, 40):
    if (f[i-1]+1)*(f[i-1]+2) == 2*i:
        f[i] = f[i-1]+1
    else:
        f[i] = f[i-1]   

if n==1:
    print(0)
else:
    arr = factorization(n)
    for a,b in arr:
        ans += f[b]
    print(ans)

Submission status: Accepted

Solution code:
import random,math

def MillerRabinPrimalityTest(n):
	if n == 2:
		return True;
	if n == 1 or n & 1 == 0:
		return False
	d = (n - 1) >> 1
	while d & 1 == 0:
		d >>= 1
	for k in range(int(math.log(n, 4))):
		a = random.randint(1, n - 1)
		t = d
		y = pow(a, t, n)
		while t != n - 1 and y != 1 and y != n - 1:
			y = (y * y) % n
			t <<= 1
		if y != n - 1 and t & 1 == 0:
			return False
	return True
def nextp(prevp):
	if(prevp<=3):
		return 2
	prevp-=1
	while(True):
		if(MillerRabinPrimalityTest(prevp)):
			break
		prevp-=1
	return prevp
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:
	ans = 0;
	facts = factorization(N)
	for fact in facts:
		used = 0
		left = fact[1]
		while True:
			used+=1
			ans+=1
			left-=used
			if left<=used:
				break
	print(ans);

Submission status: Accepted

Solution code:
import numpy as np
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

fact = collections.Counter(prime_factorize(n))
# print("f", fact)
can = 0

for a in fact.values():
    a_i = a
    # print("a", a)
    i = 0
    while(a_i >= 0):
        i += 1
        a_i -= i
        # print("i", i)
    can += (i-1)

print(can)

Submission status: Accepted

Solution code:
n = int(input())
b = n
def pf(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 = list(set(pf(n)))
cnt = 0
for i in l:
    n = b
    t = 1
    j = i
    while i <= n:
        if n % i == 0:
            cnt += 1
            n = n // i
        i *= j
print(cnt)

Submission status: Accepted

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

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

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

    return arr

N = int(input())
A  = factorization(N) 

count = 0
for i in A:
  judge = 1
  temp = i[1]
  while temp >= judge:
    count += 1
    temp -=judge
    judge += 1

if N == 1:
  count = 0

print(count)

Submission status: Accepted

Solution code:
import math
from collections import defaultdict
def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
          n /= i
          table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table
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 main():
    dd = defaultdict(int)
    n = int(input())
    pri = factorization(n)
    res = 0
    i  = len(pri)-1
    ans = 0

    for i in pri:
        k = i[1]
        i=1
        tmp=2
        cnt = 0
        while i<=k:
            i+=tmp
            tmp+=1
            cnt+=1
        ans+=cnt
    if len(pri)==1 and pri[0][1]==1:
        ans=1
    if n==1:
        ans = 0
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

line=prime_factorize(num)
value=0
time=1
ans=0


while len(line)>0:
  value1=line[0]
  if value1!=value:
    num=num/value1
    value=value1
    del line[0]
    time=1
    ans+=1
    
    
  else:
    time+=1
    if line.count(value)<time:
      del line[0:line.count(value)]
      continue
      
    value1=value**time
    num=num/value1
    del line[0:time]
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
def counter(array):
    from collections import Counter
    return list(Counter(array).most_common())
c = counter(prime_factorize(int(input())))
table = [(i + 1)*i//2 for i in range(100)]


from bisect import bisect_right
ans = 0
for x in c:
    ans += bisect_right(table,x[1]) - 1
print(ans)

Submission status: Accepted

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

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

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

    return arr


n = int(input())
if n==1:
    print(0)
    sys.exit()
ans = 0
array = factorization(n)
#print(array)

array2 = [row[1] for row in array]

for i in array2:
    ans += math.ceil(math.sqrt(2*i+9/4)-1/2)-1
    #print(math.ceil(math.sqrt(2*i+9/4)-1/2)-1)

print(ans)