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:
N=int(input())
if N==1:
    print(0)
else:
    sup=int(N**0.5)
    ans=0
    kari=N
    div=[]
    for i in range(2,sup+1):
        if kari<i:
            break
        if kari%i==0:
            count=0
            while kari%i==0:
                count+=1
                kari//=i
            div.append(count)
    if kari!=1:
        div.append(1)

    for x in div:
        num=1
        while x-num>=0:
            ans+=1
            x-=num
            num+=1
    print(ans)

Submission status: Accepted

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

used = []

def primes(n):
  primefac = dict()
  d = 2
  while d * d <= n:
    iter_ = 0
    while n % d == 0:
      iter_ += 1
      n //= d
    primefac[d] = iter_
    d += 1
  if n > 1:
    primefac[n] = 1
  return primefac 

p = primes(N)

count = 0
for (k, v) in p.items():
  count += math.floor(-0.5 + math.sqrt(0.25 + 2 * v))

print(count)

Submission status: Accepted

Solution code:
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

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

factorization(24) 

import sys
N=int(input())
if(N==1):
  print(0)
  sys.exit()
div = make_divisors(N)
div.remove(1)
new_div=[]
for k in div:
  jud=factorization(k) 
  if(len(jud)==1):
    new_div.append(k)
ans=0

for i in new_div:
  if(N%i==0):
    N=N/i
    ans+=1
  if(N==1):
    print(ans)
    sys.exit()
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

def factorize(n):
     a = []
     # 2で割り切れるまでnを割り続ける
     while n % 2 == 0:
         a.append(2)
         n //= 2
     f = 3
     # 3からはじめて各奇数で割り切れるまでnを割り続ける
     # nの最大約数は√nなので、f*fで計算
     while f * f <= n:
         if n % f == 0:
             a.append(f)
             n //= f
         else:
             f += 2
     if n != 1:
         a.append(n)
     return a
    
fs = factorize(N)

from collections import Counter
fc = Counter(fs)

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

print(ans)

Submission status: Accepted

Solution code:
def fac(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(cnt)

    if temp!=1:
        arr.append(1)

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

n=int(input())
li=fac(n)

ans=0
y=0
if n==1:
    ans=0
else:
    for x in range(1,1000):
        y=y+x
        ans=ans+len([i for i in li if i >= y])
        if len([i for i in li if i >= y])==0:
            break
print(ans)

Submission status: Accepted

Solution code:
def prime_factors(num):
    if num < 2:
        return []
    ret = []
    for i in prime_list(int(num**0.5)):
        if i*i > num:
            break
        while num % i == 0:
            ret.append(i)
            num //= i
    if num > 1:
        ret.append(num)
    return ret

def prime_list(num):
    ret = []
    search = list(range(2, num+1))
    while True:
        if search[0] > num**0.5:
            ret.extend(search)
            break
        else:
            head = search[0]
            ret.append(head)
            search.pop(0)
            search = [n for n in search if n%head != 0]
    return ret

if __name__ == "__main__":
    n = int(input())
    li = prime_factors(n)
    s = set(li)
    res = 0
    for i in s:
        c = li.count(i)
        cc = 0
        step = 1
        while True:
            cc += step
            if cc > c:
                if step > 1: step -=1
                break
            step += 1
        res += step

    print(res)

Submission status: Accepted

Solution code:
n=int(input())
M=10**6+1
l=[]
p=[1]*M
for i in range(2,M):
  if p[i]:
    l+=[i]
    for j in range(2*i,M,i):
      p[j]=0
d={}
for k in l:
  c=0
  while n%k==0: n//=k; c+=1
  if c>0: d[k]=c
s=[1]
for i in range(2,9):
  s.append(s[-1]+i)
a=0
for i in d.values():
  for j in s:
    if j>i: break
    a+=1
print(a+(n>1))

Submission status: Accepted

Solution code:
from collections import defaultdict

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 Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

N = int(input())
if(N == 1):
    print(0)
else:
    fact = factorization(N)
    l = [i for i in range(1,1000)]
    count = 0
    d = {}
    for n in fact:
        num = n[1]
        for f in l:
            num -= f
            if(num < 0):
                break
            count += 1
    print(count)

Submission status: Accepted

Solution code:
import math
from collections import Counter
def total(n):
    return int((-1 + math.sqrt(1 + 8 * n)) / 2); 
def isPrime(n) : 
  
    # Corner cases 
    if (n <= 1) : 
        return False
    if (n <= 3) : 
        return True
  
    # This is checked so that we can skip  
    # middle five numbers in below loop 
    if (n % 2 == 0 or n % 3 == 0) : 
        return False
  
    i = 5
    while(i * i <= n) : 
        if (n % i == 0 or n % (i + 2) == 0) : 
            return False
        i = i + 6
  
    return True
  
def primeFactors(n): 
    tot = 0
    a = []
    while n % 2 == 0: 
        a.append(2)
        n = n / 2
          

    for i in range(3,int(math.sqrt(n))+1,2): 

        while n % i== 0: 
            a.append(i)
            n = n / i 

    if n > 2: 
        a.append(n)
    for i, j in Counter(a).items():
        tot+=total(j)
    return tot


def sol():
    n = int(input())
    if n == 1:
        print(0)
        return
    if isPrime(n):
        print(1)
        return

    print(primeFactors(n))
    
sol()

Submission status: Accepted

Solution code:
from collections import defaultdict
n=int(input())
d=defaultdict(int)

def factorization(m):
    temp = m
    f=True
    for i in range(2, int(-(-n**0.5//1))+1):
        t=str(temp)
        if temp%i==0:
            f=False
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            d[i]=cnt
    if temp!=1:
        d[temp]=1

    return f
if n==1:
    print(0)
elif factorization(n):
    print(1)
else :
    count=0
    for key in d.keys():
        l=d[key]
        i=1
        while l>=i:
            l-=i
            i+=1
            count+=1
    print(count)

Submission status: Accepted

Solution code:
N = int(input())
pf = {}
for i in range(2, int(N**0.5) + 1):
    while N % i == 0:
        pf[i] = pf.get(i, 0) + 1
        N //= i
if N > 1:
    pf[N] = pf.get(N, 0) + 1

ans = 0
for i in pf.values():
    if i < 3:
        ans += 1
    elif i < 6:
        ans += 2
    elif i < 10:
        ans += 3
    elif i < 15:
        ans += 4
    elif i < 21:
        ans += 5
    elif i < 28:
        ans += 6
    elif i < 36:
        ans += 7
    elif i < 45:
        ans += 8
    elif i < 55:
        ans += 9
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

temp = n
p = 2
res = 0
while p * p <= n:
    if temp % p == 0:
        cnt = 1
        while temp % (p ** (cnt + 1)) == 0:
            cnt += 1
        res += int((-1 + (1 + 8 * cnt) ** 0.5) // 2)
        temp //= p ** cnt
    p += 1

print(res + (temp != 1))

Submission status: Accepted

Solution code:
n=int(input())
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])
ans=0
for t in arr:
    s=t[1]
    for k in range(1,10**12):
        ans+=1
        s-=k
        if s<=k:
            break
print(ans if n!=1 else 0)

Submission status: Accepted

Solution code:
n = int(input())

def factorization(n):
    d = {}
    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
            d[i] = cnt

    if temp!=1:
        d[temp] = 1

    if d.keys()==[]:
        d[n] = 1

    return d

def get_a(n):
    N = n
    if n == 1:
        return [1]
    elif n==2:
        return [2]
    else:
        a = [1]

    while 1:
        n_temp = n - a[-1]
        #print(n_temp, a)
        if n_temp<0:
            a.pop()
            a[-1] = N - sum(a[:-1])
            break
        elif n_temp == 0:
            break
        else:
            n = n_temp
        a.append(a[-1]+1)
    #print(n_temp, a)
    return a

ans = 0
fact_dict = factorization(n)
#print(fact_dict)

for key, val in fact_dict.items():
    #print(key, val, get_a(val))
    ans += len(get_a(val))

if ans>0:
    print(ans)
else:
    print(0)

Submission status: Accepted

Solution code:
from sys import stdin
import collections
N = int(stdin.readline().rstrip())

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
prime = prime_decomposition(N)

c = collections.Counter(prime)
p = c.values()
cnt = 0
for i in p:
    t=1
    while True:
        i = i-t
        if i<=t:
            cnt += t
            break
        t+=1
print(cnt)

Submission status: Accepted

Solution code:
import sys
n = int(input())

if n == 1:
    print(0)
    sys.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

factor_list = factorization(n)
# print(factor_list)


target_list = []
for i in factor_list:
    num = i[0]
    for j in range(i[1]):
        target_list.append(num ** (j+1))

target_list.sort()

if len(target_list) == 1:
    print(1)
    sys.exit()
current_n = n 
cnt = 0
for i in target_list:
    if  current_n % i == 0:
        current_n = current_n / i
        cnt = cnt + 1
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())


def prime_factorize_n(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


a_list = prime_factorize_n(n)
# print(a_list)

tmp = 1
used_list = []
for i in range(len(a_list)):
    if a_list[i] not in used_list:
        used_list.append(a_list[i])

    else:
        if tmp == 1:
            tmp = a_list[i]

        else:
            # print(i, tmp)
            if tmp % a_list[i] == 0:
                tmp *= a_list[i]
                if tmp not in used_list:
                    used_list.append(tmp)
                    tmp = 1
            else:
                tmp = a_list[i]

# print(used_list)
print(len(used_list))

Submission status: Accepted

Solution code:
def seachPrimeNum(N):
    max = int(N ** (1/2))
    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

a = seachPrimeNum(10 ** 6)
n=(int)(input())
ans = 0
sumi = True
if n < 2:
  print(ans)
  sumi = False
else:
  ans = 0
  count = 0
  while(count < 78498):
    temp = 0
    while(n % a[count] == 0):
      n = n // a[count]
      temp += 1
    if temp >= 45:
      ans += 9
    elif temp >= 36:
      ans += 8
    elif temp >= 28:
      ans += 7
    elif temp >= 21:
      ans += 6
    elif temp >= 15:
      ans += 5
    elif temp >= 10:
      ans += 4
    elif temp >= 6:
      ans += 3
    elif temp >= 3:
      ans += 2
    elif temp >= 1:
      ans += 1
    
    count += 1
    temp = 0
    if n < 2:
      print(ans)
      sumi = False
      break
  if count == 78498 and sumi:
      print(1 + ans)
#print(a[-100])

Submission status: Accepted

Solution code:
from math import sqrt

def is_prime(n):
  if n == 1:
    return False
  for i in range(2, int(sqrt(n))+1):
    if n % i == 0:
      return False
  return True

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(sqrt(n))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
        if len(arr) > 1:
          break

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

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

    return arr

base=int(input())
tmp=base
num=[]
if is_prime(base):
  num.append(base)
else:
  for i in range(2, base+1):
    if i > tmp:
      break
    if tmp % i == 0 and len(factorization(i)) == 1:
      num.append(i)
      tmp/=i
      if is_prime(tmp):
        num.append(tmp)
        break
print(len(list(set(num))))

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

plist=factorization(N)
if [1,1] in plist:
    plist.remove([1,1])
elist=[v[1] for v in plist]
ans=0
for e in elist:
    k=0
    n=0
    while n<=e:
        ans+=1
        k+=1
        n+=k
print(ans-len(elist))

Submission status: Accepted

Solution code:
N = int(input())

ans = 0

# if N % 2 == 0:
#     i = 1
#     while N % 2**i == 0:
#         N //= 2**i
#         ans += 1
#         i += 1

# if N % 3 == 0:
#     i = 1
#     while N % 3**i == 0:
#         N //= 3**i
#         ans += 1
#         i += 1

# if N % 5 == 0:
#     i = 1
#     while N % 5**i == 0:
#         N //= 5**i
#         ans += 1
#         i += 1

# if N % 7 == 0:
#     i = 1
#     while N % 7**i == 0:
#         N //= 7**i
#         ans += 1
#         i += 1

# if N % 11 == 0:
#     i = 1
#     while N % 11**i == 0:
#         N //= 11**i
#         ans += 1
#         i += 1

# if N % 13 == 0:
#     i = 1
#     while N % 13**i == 0:
#         N //= 13**i
#         ans += 1
#         i += 1

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

prime_list = prime_factorize(N)

if prime_list:
    for prime_num in prime_list:
        if N % prime_num == 0:
            for j in range(1, 100):
                if N < prime_num**j:
                    break
                if N % prime_num**j == 0:
                    # print(prime_num, j)
                    N //= prime_num**j
                    ans += 1
# print(N)
# print(prime_list)
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(cnt)

    if temp!=1:
        arr.append(1)

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

    return arr
A = factorization(N)
if N == 1:
    print(0)
else:
    for i in range(len(A)):
        if A[i] == 1:
            A[i] = 1
        else:
            s = (-1+int(math.sqrt(1+8*A[i])))/2
            A[i] = int(s)
    print(int(sum(A)))

Submission status: Accepted

Solution code:
import collections
import math


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 count_num(n):
    i = 2
    ret = 1
    while True:
        n = n - i
        if n <= 0:
            return ret
        i = i+1
        ret = ret + 1


def main():
    N = int(input())
    list_factorize = prime_factorize(N)
    c = collections.Counter(list_factorize)
    list_key = list(c.keys())
    list_count = list(c.values())
    ans = 0
    for i in range(0, len(list_key)):
        num = list_count[i]
        ans += count_num(num)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
x = int(input())
import math
from collections import defaultdict

res = 0
value = defaultdict(int)
def isprime(n):
    if n <= 1:
        return 0
    m = int(math.sqrt(n)) + 1
    for i in range(2, m):
        if n % i == 0:
            return 0
    return 1
if isprime(x):
    print(1)
else:
    def bprime(n):
        cnt = 2
        m = int(math.sqrt(n)) + 1
        while n != 1 and cnt < m:
            while n % cnt == 0:
                n //= cnt
                value[cnt] += 1
            cnt += 1
        if cnt == m and n != 1:
            value[n] += 1
    def cal(n):
        if n <= 2:
            return 1
        j = 1
        cnt = 0
        while n >= j:
            n -= j
            j += 1
            cnt += 1
        return cnt
    bprime(x)
    for key in value.keys():
        res += cal(value[key])
    print(res)

Submission status: Accepted

Solution code:
import numpy as np
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
  
def z(p):
    n = (-1+np.sqrt(1+8*p))/2
    return int(n)
arr = factorization(N)
if N == 1:
    print(0)
else:
    print(np.sum([z(a[-1]) for a in arr]))

Submission status: Accepted

Solution code:
N = int(input())

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)

b = []
x = 0

for i in range(len(a)):
    if i == 0:
        b.append(1)
    elif a[i-1] == a[i]:
        b[x] += 1
    else:
        x += 1
        b.append(1)

count = 0

for i in range(len(b)):
    j = 1
    while b[i] > 0:
        if (b[i] - j) >=0:
            count += 1
        b[i] = b[i] - j
        j += 1

print(count)

Submission status: Accepted

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

l=factorization(m)
ans=0
for i in range(len(l)):
    a=1
    while(l[i][1]>=a):
        ans+=1
        l[i][1]-=a
        a+=1
if m==1:
    print("0")
else:
    print(ans)

Submission status: Accepted

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

def iskaijo(n):
    i=1
    while True:
        if(n==1):
            break
        if(n%i==0):
            n=n/i
            i=i+1
        else:
            i=-1
            break
    return i

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


ng=False
ans=0
List =factorization(N)
#c=collections.Counter(List)
for i in range(len(List)):
    test = List[i][1]
    i=1
    while True:
        test=test-i
        i=i+1
        ans=ans+1
        if(test == 0):
            break
        elif(test < 0 ):
             ans=ans-1
             break
#print(List)
if N!=1:
    print(ans)
else:
    print(0)

Submission status: Accepted

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

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

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

    return arr
L = factorization(N)
ans = []
for case in L:
    p = case[0]
    k = case[1]
    for i in range(1,k+1):
        ans.append(p**i)
ans.sort()
used = []
for el in ans:
    if el not in used and N % el == 0:
        N /= el
        used.append(el)
print(len(used))
sys.exit(0)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import combinations
import numpy as np

# 引用元
# https://note.nkmk.me/python-prime-factorization/
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 get_list(counter, index):
    ans = []
    for key, val in sorted(counter.items()):
        if val >= index:
            ans.append(key)
    return ans

def choice_min_data(counter, min_num):
    temp = sum(counter.values())
    temp_min_num = 10**12
    co_index = None
    for index in range(1, temp+1):
        # flag = False
        exp_list = get_list(counter, index)
        # print(exp_list)
        if not exp_list:
            break
        for ex in exp_list:
            ex_2 = ex ** index
            if temp_min_num > ex_2 > min_num:
                co_index = [ex, index]
                temp_min_num = ex_2
                # flag = True
                break

        # 最小を新たに更新せず = 終了
        # if co_index is not None and flag == False:
        #     break

    if co_index is None:
        return None, -1
    else:
        # print(co_index, temp_min_num)
        counter[co_index[0]] -= co_index[1]
        return counter, temp_min_num

def main():
    # ルール
    # 素数p, 整数e: z == p ** e
    # N / z = int(x)
    # zは被らない
    # N を N/zに置き換える
    N = int(input())

    if N <= 1:
        print(0)
        return

    counter = Counter(prime_factorize(N))
    # print(counter)
    ans = 0
    min_num = 0
    while counter is not None:
        counter, min_num = choice_min_data(counter, min_num)
        if min_num == -1:
            break
        ans += 1
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=p=1
while p<6**8:
 c=t=0;p+=1
 while n%p<1:n//=p;x=c==t;t+=x;c+=1-t*x;a+=x
print(a-(n<2))

Submission status: Accepted

Solution code:
from collections import defaultdict

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

def calc(i):
  c = 1;
  acc = 0;
  count = 0
  while acc < i:
    acc += c
    c += 1
    if acc<=i:
      count+=1
  return count;

def main():
  n = int(input())
  if(n==1):
    print(0)
    return;
  facts = prime_factorize(n)
  count = 0
  for fact in facts:
    count += calc(facts[fact])
  print(count)

main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""
import math

#def main(N):
def main():
    N = int(input())
    # Nが1のときは答えは0
    if N == 1:
        return 0
    else:
        N_remein = N
        # Nを素因数分解する。
        p_list = []
        p_factor_list = []
        #p = 2
        #while N_remein >= 2:
        for p in range(2, math.ceil(math.sqrt(N))+1):
            if N_remein%p == 0:
                counter = 0
                #p_pow_counter = 1
                while True:
                    #p_pow_counter *= p
                    if N_remein%p == 0:
                        N_remein = N_remein//p
                        counter+=1
                    else:
                        p_list.append(p)
                        p_factor_list.append(counter)
                        break
        if N_remein != 1:
            p_list.append(N_remein)
            p_factor_list.append(1)
        #print(p_list)
        #print(p_factor_list)
        # Nが素数の場合は、答えは1。
        if not p_factor_list:
            return 1
        else:
            answer = 0
            # 各素因数の指数に対して、、
            # 1,2,3,...と正整数を順番に引いていき、
            # 引けた回数を合計する。
            for factor in p_factor_list:
                counter = 1
                while (counter*(counter+1))//2 <= factor:
                    counter += 1
                answer += (counter-1) 
            #return answer, p_list, p_factor_list
            return answer

if __name__ == "__main__":
    print(main())
    #for i in range(1, 100):
    #    print(i, main(i))

Submission status: Accepted

Solution code:
import sys
import math


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

prims = prime_factorize(n)

prim_set = set(prims)

deleted_prims = {}

ans = 0
for prim in prim_set:
    while True:
        if prim not in deleted_prims:
            deleted_prims[prim] = 1
        times = deleted_prims[prim]
        # print(times)
        if times == 0:
            break
        if times <= prims.count(prim):
            # 操作できる
            ans += 1
            for i in range(times):
                prims.remove(prim)
            deleted_prims[prim] += 1
            # print("OK", prims)

        else:
            break

print(ans)

Submission status: Accepted

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

import math

def kaisa(x):
  first = math.floor(math.sqrt(x*2))
  if x*2 >= first*(first+1):
    return first
  else:
    return first-1

n = int(input())
soinsu = factorize(n) 

res = 0
for i in soinsu:
  res = res + kaisa(i[1])
print(res)

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
a = prime_factorize(n)
b = list(set(a))
total = 0
for j in range(len(b)):
    c  = len([i for i, x in enumerate(a) if x == list(set(a))[j]])
    y = 1
    while c>0:
        c -= y
        y += 1
        if c>=0:
            total +=1
print(total)

Submission status: Accepted

Solution code:
# coding: utf-8
from math import sqrt


def solve(*args: str) -> str:
    n = int(args[0])

    ret = 0
    i = 2
    sqrt_n = -int(-sqrt(n))
    P = [True]*(sqrt_n+1)
    P[0] = False
    P[1] = False

    for i in range(2, len(P)):
        if P[i]:
            for j in range(i+i, len(P), i):
                P[j] = False

    Q = []
    for p, is_prime in enumerate(P):
        if is_prime and n % p == 0:
            t = p
            while t <= n:
                Q.append(t)
                t *= p
    if not Q and 1 < n:
        Q.append(n)

    Q.sort()
    for q in Q:
        if n % q == 0:
            n //= q
            ret += 1

    for p, is_prime in enumerate(P):
        while is_prime and n % p == 0:
            n //= p
    if 1 < n:
        ret += 1

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

Solution code:
import heapq
n = int(input())
copy = 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


f = factorization(n)
l = []
for i in f:
    for j in range(1, i[1]+1):
        l.append(i[0]**j)

heapq.heapify(l)

cnt = 0
while l:
    tmp = heapq.heappop(l)
    if n % tmp == 0:
        n = n // tmp
        cnt += 1
print(cnt if copy != 1 else 0)