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

def solv_quadratic_equation(a, b, c):
    D = (b**2 - 4*a*c) ** (1/2)
    x_1 = (-b + D) / (2 * a)
    x_2 = (-b - D) / (2 * a)

    return x_1, x_2

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

ans = 0

for v in dic.values():
    a,b = solv_quadratic_equation(1, 1, -2*v)
    ans += int(max(a, b))
print(ans)

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:
n=int(input())

#factor=[]
ans=0
for i in range(2,int(n**.5)+1):
	if n%i==0:
		cnt=1
		k=0
		while n%i==0:
			k+=1
			if cnt==k:
				ans+=1
				cnt+=1
				k=0
			#factor.append(i)
			n//=i

if n>1:
	#factor.append(n)
	ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
from math import sqrt

def log(s):
    # print("| " + str(s), file=sys.stderr)
    pass


def output(x):
    print(x, flush=True)


def input_ints():
    return list(map(int, input().split()))


def main():
    n = int(input())
    r = 0
    for i in range(2, int(sqrt(n)+1)):
        if n % i == 0:
            e = 0
            while n % i == 0:
                e += 1
                n //= i
            k = 1
            while e - k >= 0:
                r += 1
                e -= k
                k += 1
        if i > n:
            break
    
    if n > 1:
        r += 1
    
    print(r)

main()

Submission status: Accepted

Solution code:
N = int(input())
 
div_counts = []
for i in range(2, int(N**0.5)+1):
    count = 0
    while N%i == 0:
        count += 1
        N //= i
        if N == 1: break
    div_counts.append(count)
 
if N != 1: div_counts.append(1)
 
ans = 0
for count in div_counts:
    for i in range(1, count+1):
        if count >= i:
            ans += 1
            count -= i
print(ans)

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 k, v in primes.items():
        num = 1
        while v >= num:
            v -= num
            num += 1
            ans += 1
    print(ans)
    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math


def prime_factors(n):
    count = {2: 0}

    while n % 2 == 0:
        n = n / 2
        count[2] += 1

    for i in range(3, int(math.sqrt(n))+1, 2):
        count[i] = 0
        while n % i == 0:
            n = n / i
            count[i] += 1

    if n > 2:
        if int(n) in count:
            count[int(n)] += 1
        else:
            count[int(n)] = 1
    # print(count)
    ans = 0
    for k in count.values():
        if k:
            j = int((2*k)**0.5)
            while j*(j+1) <= 2*k:
                j += 1
            ans += j-1

    return ans


n = int(input())

print(prime_factors(n))

Submission status: Accepted

Solution code:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
 
    if temp!=1:
        arr.append([temp, 1])
 
    if arr==[]:
        arr.append([n, 1])
 
    return arr
 
n = int(input())
if n==1:
  print(0)
else:
  arr = factorization(n)
  trial_list = []
  for p in arr:
    i = p[0]
    j = p[1]
    for k in range(1,j+1):
      trial_list.append(i**k)
  sorted(trial_list)
  cnt=0
  for i in trial_list:
    if n%i==0:
      cnt+=1
      n//=i
  print(cnt)

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
 
if N == 1:
  print(0)
  exit()
 
f = factorization(N)

if len(f) == 1 and f[0][1] == 1:
  print(1) 
  exit()

count = 0
num = 1
for p,q in f:
  for e in range(1,q+1):
    if N%p**e == 0:
      N //= p**e
      count += 1
print(count)

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

N = int(input())
a = prime_factorize(N)
z = set()
cnt = 0

while len(a) > 0:
    num = a.pop(0)
    cursor = num
    while True:
        if num not in z:
            z.add(num)
            break
        elif len(a) <= 0:
            break
        elif cursor != a[0]:
            break
        num *= a.pop(0)

print(len(z))

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

a = factorization(n)

ans = 0
for _, c in a:
    i = 1
    while True:
        if c >= i:
            ans += 1
            c -= i
            i += 1
        else:
            break
print(ans)

Submission status: Accepted

Solution code:
from math import sqrt
n = int(input())
cnt = [0]*1000000
ans = 0
for i in range(2,int(sqrt(n))):
    if(n==1): break
    j = 1
    while n%i==0:
        n = n//i
        cnt[i-1]+=1
        if cnt[i-1]==j:
            ans+=1
            j+=1
            cnt[i-1]=0
if n!=1: ans+=1
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

if N == 1:
  print(0)
  exit()
lst = factorization(N)
res = 0
for i in range(len(lst)):
  a = lst[i][1]
  for k in range(1, 10** 5):
    if a >= k:
      a -= k
      res += 1
    else:
      break
print(res)

Submission status: Accepted

Solution code:
n = int(input())

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

if n == 1:
    print('0')
elif n == 6:
    print('2')
elif pcheck(n) == True:
    print('1')
else:
    rootn = int(n ** 0.5)
    k = 0
    for i in range(2, rootn + 2):
        if n == 1:
            print(k)
            break
        elif n % i == 0:
            j = 1
            p = i
            while n % p == 0:
                k += 1
                n //= p
                j += 1
                p = i ** j
            p //= i
            while n % i == 0:
                if n % p != 0:
                    p //= i
                    continue
                n //= p
    else:
        if pcheck(n) == True:
            k += 1
            print(k)
        else:
            print('1')

Submission status: Accepted

Solution code:
import collections
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
N=int(input())
count = 0
A=prime_factorize(N)
if A==0:print(0)
else:
  B=collections.Counter(A)
  C=list(B.values())
  for i in C:
    for j in range(1,N+1):
      if j*(j+1)//2 <= i < (j+1)*(j+2)//2:
        count +=j
        break
print(count)

Submission status: Accepted

Solution code:
def main():
    
    import collections

    N = int(input())

    def factorization(num):
        factorize = []
        while (num % 2 == 0):
            num //= 2
            factorize.append(2)
        
        division = 3
        
        while (division * division <= num):
            
            if (num % division == 0):
                factorize.append(division)
                num //= division
            else:
                division += 2
            
        if (num != 1):
            factorize.append(num)
        
        return (factorize)
    
    def count_div(n):
        cnt = 0
        sub = 0
        
        while (n > 0):
            sub += 1
            n -= sub
            if (n >= 0):
                cnt += 1

        return(cnt)

    facts = factorization(N)
    CTR_facts = collections.Counter(facts).most_common()
    
    ans = 0
    
    for i in range(len(CTR_facts)):
        v = CTR_facts[i][1]
        
        tmp = count_div(v)
        ans += tmp
    
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
p_list=[]
ans=[]
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
c = collections.Counter(prime_factorize(int(input())))
p_list=c.values()
for i in p_list:
    m=1
    while 1/2*(m+1)*(m+2)<=i:
        m+=1
    ans.append(m)
print(sum(ans))

Submission status: Accepted

Solution code:
import math

def append_factors(n, f, p):
    num_factors = 0
    while n % p == 0:
        num_factors += 1
        n //= p
    if num_factors != 0:
        f[p] = num_factors
    return n

def factors(n):
    ret = {}
    n = append_factors(n, ret, 2)
    n = append_factors(n, ret, 3)
    i = 6
    while i*i <= n + 1:
        p1, p2 = i - 1, i + 1
        n = append_factors(n, ret, i - 1)
        n = append_factors(n, ret, i + 1)
        i += 6
    if n != 1:
        ret[n] = 1

    return ret

def minimum_sum(x):
    # find the minimum integer n where n(n+1)/2 <= x
    # n(n+1) <= 2x < (n+1)(n+2)

    n = int(math.sqrt(2 * x))
    while n*(n + 1) > 2*x:
        n -= 1

    return n

def main():
    N = int(input())
    fs = factors(N)
    # print(fs)
    ans = 0
    for f in fs:
        ans += minimum_sum(fs[f])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

import math

def factorization(n):
    factor_list = []
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp+1):
        if n % num == 0:
            count = 0
            while n % num == 0:
                count += 1
                n //= num
                
            factor_list.append([num, count])
        
    if n != 1:
        factor = [n, 1]
        factor_list.append(factor)
    #print(n)
    return factor_list
            

def main():
    n = int(input())
    count = 0
    
    factor_list = factorization(n)
    
    for _, exponent in factor_list:
        #exponent = 1
        #n /= factor[0] ** exponent
        #count += 1
        #factor[1] -= exponent
        #exponent += 1
        #print(exponent)
        i = 1
        while exponent >= i:
            #print(factor_list)
            #n /= factor[0] ** exponent
            count += 1
            exponent = exponent - i
            i += 1
    
    print(count)
    return
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

def factors(n):
    l = int(math.sqrt(n)) + 1
    ret = {}
    nf2 = 0
    while n % 2 == 0:
        nf2 += 1
        n //= 2
    if nf2 != 0:
        ret[2] = nf2
    nf3 = 0
    while n % 3 == 0:
        nf3 += 1
        n //= 3
    if nf3 != 0:
        ret[3] = nf3
    # n = append_factors(n, ret, 2)
    # n = append_factors(n, ret, 3)
    i = 6
    while i*i <= n + 1:
        p1, p2 = i - 1, i + 1
        nfp1 = 0
        while n % p1 == 0:
            nfp1 += 1
            n //= p1
        if nfp1 != 0:
            ret[p1] = nfp1
        nfp2 = 0
        while n % p2 == 0:
            nfp2 += 1
            n //= p2
        if nfp2 != 0:
            ret[p2] = nfp2
        # n = append_factors(n, ret, i - 1)
        # n = append_factors(n, ret, i + 1)
        i += 6
    if n != 1:
        ret[n] = 1

    return ret

def minimum_sum(x):
    # find the minimum integer n where n(n+1)/2 <= x
    # n(n+1) <= 2x < (n+1)(n+2)

    n = int(math.sqrt(2 * x))
    while n*(n + 1) > 2*x:
        n -= 1

    return n

def main():
    N = int(input())
    fs = factors(N)
    # print(fs)
    ans = 0
    for f in fs:
        ans += minimum_sum(fs[f])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

def factors(n):
    l = int(math.sqrt(n)) + 1
    ret = {}
    nf2 = 0
    while n % 2 == 0:
        nf2 += 1
        n //= 2
    if nf2 != 0:
        ret[2] = nf2
    nf3 = 0
    while n % 3 == 0:
        nf3 += 1
        n //= 3
    if nf3 != 0:
        ret[3] = nf3
    # n = append_factors(n, ret, 2)
    # n = append_factors(n, ret, 3)
    i = 6
    while i*i <= n + 1:
        p1, p2 = i - 1, i + 1
        nfp1 = 0
        while n % p1 == 0:
            nfp1 += 1
            n //= p1
        if nfp1 != 0:
            ret[p1] = nfp1
        nfp2 = 0
        while n % p2 == 0:
            nfp2 += 1
            n //= p2
        if nfp2 != 0:
            ret[p2] = nfp2
        # n = append_factors(n, ret, i - 1)
        # n = append_factors(n, ret, i + 1)
        i += 6
    if n != 1:
        ret[n] = 1

    return ret

def minimum_sum(x):
    # find the minimum integer n where n(n+1)/2 <= x
    # n^2 < n(n+1) <= 2x < (n+1)(n+2) < (n+2)^2

    n = int(math.sqrt(x))
    while (n + 1)*(n + 2) <= 2*x:
        n += 1

    return n

def main():
    N = int(input())
    fs = factors(N)
    # print(fs)
    ans = 0
    for f in fs:
        ans += minimum_sum(fs[f])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

def append_factor(f, p):
    if p not in f:
        f[p] = 0
    f[p] += 1

def append_factors(n, f, p):
    num_factors = 0
    while n % p == 0:
        num_factors += 1
        n //= p
    if num_factors != 0:
        f[p] = num_factors
    return n

def factors(n):
    l = int(math.sqrt(n)) + 1
    ret = {}
    n = append_factors(n, ret, 2)
    n = append_factors(n, ret, 3)
    i = 6
    while i*i <= n + 1:
        p1, p2 = i - 1, i + 1
        n = append_factors(n, ret, i - 1)
        n = append_factors(n, ret, i + 1)
        i += 6
    if n != 1:
        append_factor(ret, n)

    return ret

def minimum_sum(x):
    # find the minimum integer n where n(n+1)/2 <= x
    # n^2 < n(n+1) <= 2x < (n+1)(n+2) < (n+2)^2

    n = int(math.sqrt(x))
    while (n + 1)*(n + 2) <= 2*x:
        n += 1

    return n

def main():
    N = int(input())
    fs = factors(N)
    # print(fs)
    ans = 0
    for f in fs:
        ans += minimum_sum(fs[f])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

def append_factor(f, p):
    if p not in f:
        f[p] = 0
    f[p] += 1

def factors(n):
    l = int(math.sqrt(n)) + 1
    ret = {}
    while n % 2 == 0:
        append_factor(ret, 2)
        n //= 2
    while n % 3 == 0:
        append_factor(ret, 3)
        n //= 3
    i = 6
    while i*i <= n + 1:
        while n % (i - 1) == 0:
            append_factor(ret, i - 1)
            n //= (i - 1)
        while n % (i + 1) == 0:
            append_factor(ret, i + 1)
            n //= (i + 1)
        i += 6
    if n != 1:
        append_factor(ret, n)

    return ret

def minimum_sum(x):
    # find the minimum integer n where n(n+1)/2 <= x
    # n^2 < n(n+1) <= 2x < (n+1)(n+2) < (n+2)^2

    n = int(math.sqrt(x))
    while (n + 1)*(n + 2) <= 2*x:
        n += 1

    return n

def main():
    N = int(input())
    fs = factors(N)
    # print(fs)
    ans = 0
    for f in fs:
        ans += minimum_sum(fs[f])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

if n == 1:
    print(0)
else:
    # 試し割り
    data = []
    t = n
    for i in range(2, int(n**0.5)+1):
        while t % i == 0:
            t //= i
            if i not in data:
                data.append(i)
    # √n より大きな素数があった場合
    if t > 1:
        data.append(t)
        t //= t

    # print(data)

    # 処理系
    ans = 0
    for j in range(len(data)):
        for k in range(1, 41):
            p_e = data[j] ** k
            if n % p_e == 0:
                n //= p_e
                ans += 1
            else:
                break

    print(ans)

Submission status: Accepted

Solution code:
n = int(input())

if n == 1:
    print(0)
else:
    # 試し割り
    data = []
    t = n
    for i in range(2, int(n**0.5)+1):
        while t % i == 0:
            t //= i
            if i not in data:
                data.append(i)
    # 自身が √n より大きな素数だった場合
    if t % n == 0:
        t //= n
        data.append(n)
    # よくわからない大きな塊が残ったら足すw?
    if t != 1:
        data.append(t)
        t //= t

    # print(data)

    # 処理系
    ans = 0
    for j in range(len(data)):
        for k in range(1, 41):
            p_e = data[j] ** k
            if n % p_e == 0:
                n //= p_e
                ans += 1
            else:
                break

    print(ans)

Submission status: Accepted

Solution code:
import math

def append_factor(f, p):
    if p not in f:
        f[p] = 0
    f[p] += 1

def factors(n):
    l = int(math.sqrt(n)) + 1
    ret = {}
    while n % 2 == 0:
        append_factor(ret, 2)
        n //= 2
    while n % 3 == 0:
        append_factor(ret, 3)
        n //= 3
    for i in range(6, l, 6):
        while n % (i - 1) == 0:
            append_factor(ret, i - 1)
            n //= (i - 1)
        while n % (i + 1) == 0:
            append_factor(ret, i + 1)
            n //= (i + 1)
    if n != 1:
        append_factor(ret, n)

    return ret

def minimum_sum(x):
    # find the minimum integer n where n(n+1)/2 <= x
    # n^2 < n(n+1) <= 2x < (n+1)(n+2) < (n+2)^2

    n = int(math.sqrt(x))
    while (n + 1)*(n + 2) <= 2*x:
        n += 1

    return n

def main():
    N = int(input())
    fs = factors(N)
    # print(fs)
    ans = 0
    for f in fs:
        ans += minimum_sum(fs[f])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
ans = 0
d = 2

while d * d <= n:
    if n % d != 0:
        d +=1
    z = d
    while n % z ==0: 
        n = n/z
        z *=d
        ans+=1
        
    while n%d == 0: #残った素因数を消化
        n /= d

if n !=1:
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
from math import sqrt as r
from math import ceil as f
N = int(input())

dev2 = 0
N2 = N
while True:
    if N2 % 2 == 0:
        N2 /= 2
        dev2 += 1
    else:
        break

p = [2] * dev2

for c in range(3, f(r(N2)), 2):
    while True:
        if N2 % c == 0:
            N2 /= c
            p.append(int(c))
        else:
            break
if N2 != 1:
    p.append(int(N2))


pp = []
while True:
    if len(p) == 0:
        break
    pp.append(p.count(p[0]))
    del p[:pp[-1]]

#print(pp)
ans = 0

for c in pp:
    cou = 1
    while True:
        if cou + (cou + 1) > c:
            ans += cou
            break
        else:
            c -= cou
            cou += 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())
z_list = factorization(N)
Z = []
for z in z_list:
        for e in range(1, z[1]+1):
            Z.append(z[0]**e)
sorted(Z)
counter = 0 
if N==1:
    print(0)
    quit()
for z in Z:
    if(N%z==0):
        N = N//z
        counter += 1
print(counter)

Submission status: Accepted

Solution code:
import numpy as np
from math import sqrt
from collections import defaultdict


def sieve(x):
    primes = []
    is_prime = np.ones(x + 1, bool)
    is_prime[0] = is_prime[1] = False
    for i in range(x + 1):
        if is_prime[i]:
            primes.append(i)
            is_prime[2*i::i] = False

    return primes


def prime_fact(x):
    mx = int(sqrt(x)) + 5
    primes = sieve(mx)
    pf = defaultdict(int)
    for e in primes:
        while x % e == 0:
            x //= e
            pf[e] += 1

    if x != 1:
        pf[x] += 1

    return pf


n = int(input())

pf = prime_fact(n)
ans = 0
for v in pf.values():
    i = 1
    while (i + 1) * (i + 2) // 2 <= v:
        i += 1

    ans += i

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
if n == 1:
    print(0)
    exit()

def primes_factraizar(n):
    rn = int(n**0.5)
    is_prime = [True]*(rn+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2,rn+1):
        if not is_prime[i]:
            continue
        for j in range(i*2,rn+1,i):
            is_prime[j] = False
        return [i for i in range(rn+1) if is_prime[i]]
primes = primes_factraizar(n)

divisors = []
for i in primes:
    if n % i == 0:
        divisors.append(i)

divisors.sort()

if divisors == []:
    print(1)
    exit()
ans = 0

for i in divisors:
    if i == 1:
        continue

    c = 0

    while n%i == 0:
        n = n // i
        c += 1
    
    d=0

    for count in range(1,1000):
        if c >= d+count:
            ans += 1
            d+=count
        else:
            break
if not n == 1:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5))+1):
        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

z = factorization(int(input()))
i = 1
ans = 0
flag = True
while flag:
    flag2 = False
    for j in range(len(z)):
        if z[j][1] >= i:
            z[j][1] -= i
            ans += 1
            flag2 = True

    i += 1
    if flag2 == False: flag = False
print(ans)

Submission status: Accepted

Solution code:
import math
import collections

# 試割法
def trial_division(target):
    dest = int(math.sqrt(target))
    
    # 素因数リスト
    factor = []
    for i in range(2,dest):
        while target % i == 0:
            target //= i
            factor.append(i)

    if target != 1:
        factor.append(target)

    if not factor:
        factor.append(target)
    return factor

n = int(input())

c = collections.Counter(trial_division(n))
count = 0

for v in c.values():
    for i in range(1,n):
        v -= i
        if v >= 0:
            count += 1
        else:break
print(count)

Submission status: Accepted

Solution code:
import math
N=int(input())
n=N
p=2
dp=1
thrP=math.sqrt(N)
dcmp={}
while n>1:
    if n%p==0:
        dcmp[p]=1+(dcmp[p] if p in dcmp else 0)
        n//=p
    else:
        p+=dp
        dp=2
    if p>thrP:
        if n>1:
            dcmp[n]=1
        break
cnt=0
for k,v in dcmp.items():
    i=1
    while True:
        dcmp[k]-=i
        if dcmp[k]<0:
            break
        i+=1
        cnt+=1

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
ans = 0
d = 2

while d*d <= n:
    if n%d != 0:
        d += 1
        continue
    
    z = d
#     print('z: {}'.format(z))

    while n%z == 0:
        n /= z
        z *= d
#         print('z: {}'.format(z))
        ans += 1
    
    while n%d == 0:
        n /= d

if n != 1:
    ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
 
div_counts = []
for i in range(2, int(N**0.5)+1):
    count = 0
    while N%i == 0:
        count += 1
        N //= i
        if N == 1: break
    div_counts.append(count)

if N != 1: div_counts.append(1)

ans = 0
for count in div_counts:
    for i in range(1, count+1):
        if count >= i:
            ans += 1
            count -= i
print(ans)

Submission status: Accepted

Solution code:
from math import sqrt

n = int(input())

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

n_sqrt = int(sqrt(n))

dp = [-1] * (n_sqrt+2)

for i in range(2, n_sqrt+2):
    if dp[i] == -1:
        dp[i] = 1
        for j in range(i*2, n_sqrt+2, i):
            dp[j] = 0

prime = []

for i in range(2, n_sqrt+2):
    if dp[i] == 1:
        prime.append(i)

prime.append(n)

memo = []
for p in prime:
    cnt = 0
    while n%p==0:
        n //= p
        cnt += 1

    if cnt:
        memo.append(cnt)

if n > 1:
    memo.append(1)

ans = 0

for j in memo:
    k = 1
    while True:

        if k*(k+1)//2 <= j <= k*(k+3)//2:
            ans += k
            break
        k += 1

print(ans)

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

if __name__ == "__main__":
    n = int(input())
    sosuu_list = prime_factorize(n)
    c = Counter(sosuu_list)
    cnt = 0
    for _, v in c.items():
        i = 1
        while(v > 0):
            v -= i
            i += 1
            cnt += 1
        if v < 0:
            cnt -= 1
    print(cnt)

Submission status: Accepted

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

# print(prime_decomposition(25))
n = int(input())
p = prime_decomposition(n)
# print(p)

cnt = 0
for k in set(p):
    b = p.count(k)
    a = 1
    c = 1
    while c <= b:
        a += 1
        c += a
    cnt += a - 1

print(cnt)

Submission status: Accepted

Solution code:
def enum_divisors(n):
    res = []
    a = 2
    while a*a <= n:
        if n % a == 0:
            e = 0
            while n % a == 0:
                e += 1
                n //= a
            res.append((a,e))
        a += 1
    
    if n != 1:
        res.append((n,1))

    return res

n = int(input())
enums = enum_divisors(n)
ans = 0
for i in enums:
    e = i[1]
    j = 0
    while e >= 0:
        j += 1
        e -= j

    ans += j - 1

print(ans)

Submission status: Accepted

Solution code:
try: 
    N = int(input())
except:
    exit()
def main(n, var):
    mylist = []
    dupliN = n
    for i in range(2, int(-(-n**0.5//var))+var):
        if dupliN%i==0:
            cnt=0
            while dupliN%i==0:
                cnt+=var
                dupliN //= i
            mylist.append([i, cnt])
 
    if dupliN!=1:
        mylist.append([dupliN, 1])
    if mylist==[]:
        mylist.append([n, 1])
    return mylist
if N == 1:
    print(0)
    exit()
f = main(N, 1)
ansval = 0
for extra, value in f:
    num = 1
    while True:
        value -= num
        if value < 0:
            break
        ansval += 1
        num += 1 
print(ansval)

Submission status: Accepted

Solution code:
import math

def fact(x, k):
    if x % (k ** (A[-1] + 1)) == 0:
        A[-1] += 1
        return fact(x // (k ** (A[-1])), k)
    for i in range(k, int(math.sqrt(x)) + 1):
        if x % i == 0:
            if i != k:
                A.append(1)
            return fact(x // i, i)
    if x > k:
        A.append(1)

N = int(input())
A = [0]
fact(N, 2)
print(sum(A))

Submission status: Accepted

Solution code:
import sys

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

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

f = factorization(N)

result = 0
for p, e in f:
    i = 1
    while True:
        e -= i
        if e < 0:
            break
        result += 1
        i += 1

print(result)

Submission status: Accepted

Solution code:
import sys

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

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

f = factorization(N)

result = 0
for p, e in f:
    i = 1
    while True:
        e -= i
        if e < 0:
            break
        result += 1
        i += 1

print(result)