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

Solution code:
N = int(input())

import heapq 
from collections import defaultdict
import numpy as np
import math

def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1

def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum




if is_prime(N):
    ans = 1
elif N == 1:
    ans = 0
else:
    heap = seachPrimeNum(int(math.sqrt(N)))
    # print(heap)
    heapq.heapify(heap)
    ans = 0
    dict_prime = defaultdict(int)

    while(1):
        # print(N)
        # cnt += 1
        # if cnt > 10:break
        # print(N)
        sub = heapq.heappop(heap)
        # print(sub)
        # print(cand)
        # print(heap)
        # print(cand)
        # print(heapq)
        if N < sub:
            # print(N,sub)
            # print("a")
            break
        if N % sub == 0:
            N = N // sub
            ans += 1
            if sub not in dict_prime:
                dict_prime[sub] = sub
                dict_prime[sub*sub] = sub
            else:
                dict_prime[sub*dict_prime[sub]] = dict_prime[sub]
                # print("a")
            heapq.heappush(heap, sub*dict_prime[sub])


print(ans)

Submission status: Runtime Error

Solution code:
history = set([])


import sympy

def func(n):
    if n == 1:
        return 
    l = sympy.divisors(n)
    for i in sorted(l[1:]):
        if i in history:
            continue
        if len(sympy.factorint(i)) > 1:
            continue
        print(i, n)
        history.add(i)
        _ = n // i
        func(_)
        break
    return

N = int(input())
if N == 0:
    print(0)
elif N == 1:
    print(1)
else:
    func(N)
    print(len(history))

Submission status: Runtime Error

Solution code:
import math
N=int(input())
def hantei(u):
  if u==1:
    return 1
  for i in range(1,u+1):
    if (1/2)*i**2+(1/2)*i>u:
      return int(i-1)
    else:
      continue
   
a=[0]*int(N)
for i in range(2,N+1):
  while N%i==0:
    N=N//i
    a[i-1]=a[i-1]+1
c=0
for t in range(len(a)):
  if a[t]!=0:
    c+=hantei(a[t])
print(c)

Submission status: Runtime Error

Solution code:
def soinsu(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())
a=soinsu(n)
c=[]
if n>=2:
    for i in range(max(a)):
        c.append(0)
for i in a:
    c[i-1]+=1
z=0
f=max(c)
g=[1]
d=1
e=1
while e<=f:
    d+=1
    e=d*(d+1)/2
    g.append(e)
l=len(g)
for i in c:
    for j in range(l):
        if i<g[j]:
            z+=j
            break
        
print(z)

Submission status: Runtime Error

Solution code:
if N > rootN:
    res*=2

Submission status: Runtime Error

Solution code:
import sys
import sympy

n = int(sys.stdin.readline())

def isPrime(n):
    if n < 2:
        return False
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return False
    return True

def divisors(n):
    l = []
    for i in range(2, n):
        if n % i == 0:
            l.append(n)
    return l

def calc(n):
    used = set()
    a = 0
    c = True
    c1 = []
    ds = sympy.divisors(n)
    m = max(ds)
    for d in ds:
        if not isPrime(d):
            continue
        v = d
        i = 1
        while v <= m:
            c1.append(v)
            i += 1
            v = d ** i
    c1.sort()
    while c:
        c = False
        for d in c1:
            if d in used:
                continue
            if n % d != 0:
                continue
            #print(n, d)
            n //= d
            a += 1
            c = True
            used.add(d)
            break
    return a

print(calc(n))

Submission status: Runtime Error

Solution code:
N = int(input())
def ret(x,y,i):
    if x==1:
        return print(y)
    else:
        if x%i==0:
            return ret(x/i,y+1,i+1)
        else:
            return ret(x,y,i+1)
ret(N,0,2)

Submission status: Runtime Error

Solution code:
N = int(input())

import sympy

W =[]
L = list(sympy.divisors(N))

while len(L)>1:
    for i in L[1:]:
        if i in W :
            continue
        else:
            N=int(N/i)
            W.append(i)
            L = list(sympy.divisors(N))
            break
        break
    else:
        break

print(len(W))

Submission status: Runtime Error

Solution code:
import sys                          
import sympy                        
                                    
n = int(sys.stdin.readline())       
                                    
def isPrime(n):                     
    if n < 2:                       
        return False                
    for i in range(2,int(n**0.5)+1):
        if n%i==0:                  
            return False            
    return True                     
                                    
def divisors(n):                    
    l = []                          
    for i in range(2, n):           
        if n % i == 0:              
            l.append(n)             
    return l                        
                                    
def calc(n):                        
    used = set()                    
    a = 0                           
    c = True                        
    c1 = []                         
    ds = sympy.divisors(n)          
    m = max(ds)                     
    for d in ds:                    
        if not isPrime(d):          
            continue                
        v = d                       
        i = 1                       
        while v <= m:               
            c1.append(v)            
            i += 1                  
            v = d ** i              
    c1.sort()                       
    while c:                        
        c = False                   
        for d in c1:                
            if d in used:           
                continue            
            if n % d != 0:          
                continue            
            n //= d                 
            a += 1                  
            c = True                
            used.add(d)             
            break                   
    return a                        
                                    
print(calc(n))

Submission status: Runtime Error

Solution code:
N = int(input())
def is_prime(n):
    if(n<=1):
        ans=False
    elif(n==2):
        ans=True
    else:
        for i in range(2,n):
            if(n%i==0):
                ans=False
                break
            if(i**2>n):
                ans=True
                break
    return ans
z=2
recode={}
count=0
if isprime(N):
    print(1)
else:
    while N!=1:
        if isprime(N):
            count=count+1
            break
        if N%z==0:
            if z not in recode.keys():
                recode[z]=1
                N=int(N/z)
                z=2
                count+=1
                if isprime(N):
                    count=count+1
                    break
            else:
                z+=1
        else:
            z+=1
    print(len(recode.keys()))

Submission status: Runtime Error

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())
x = factorization(n)
x.sort(key=lambda x: x[-1])
a = [0]
b = 3
for i in range(3,9):
    a.append(b)
    b += i
ans = 0
c = 1
for i in range(len(x)):
    for j in range(len(a)):
        if x[i][1] >= a[c]:
            c += 1
        else:
            break
    ans += c
if n == 1:
    print(0)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
N = int(input())
fact = factorization(N)
if fact[0][0] == 1:
    print(0)
    sys.exit()
ans = 0
for f, num in fact:
    for i in range(1, num+1):
        if num < i:
            break
        num -= i
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import sympy
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 main():
    N=int(input())
    ans=0
    if N==1:
        print(ans)
        return 
    t=prime_decomposition(N)
    if len(t)==1:
        print(1)
        return 
    dic={}
    for a in t:
        if not a in dic.keys():
            dic[a]=1
            continue
        else:
            dic[a]+=1
    ans=0
    for i in dic.keys():
        num=dic[i]
        tmp=1
        c=1
        while True:
            if num >=c:
                num-=c
                c+=1
                ans+=1
            else:
                break
    print(ans)



        


main()

Submission status: Runtime Error

Solution code:
from tqdm import tqdm
import math

N = int(input())
max_n = math.sqrt(N)
count = 0
for i in tqdm(range(2, int(max_n+1))):
    if N % i == 0:
        count += 1
        N /= i
print(1 if count == 0 else count)

Submission status: Runtime Error

Solution code:
import sympy

N = int(input())
divi = sympy.divisors(N)
imp_factor = [
    sympy.factorint(i) for i in divi
]
imp_factor = [i for i in imp_factor if len(i) == 1]

known = dict()
ret = 0
while True:
    if len(imp_factor) == 0:
        break
    cnt = 0
    while True:
        if len(imp_factor) == 0:
            break
        factor_d = imp_factor.pop(0)
        factor = list(factor_d.keys())[0]
        factor_v = factor_d[factor]
        if factor**factor_v not in known:
            known[factor**factor_v] = 1
            ret += 1
            break
    for i in range(len(imp_factor)):
        if list(imp_factor[i].keys())[0] == factor:
            imp_factor[i][factor] -= 1

print(ret)
pass