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:
def main():
    n = int(input())
    ans = 0

    fac = 2
    e = 1
    while True:
        div = pow(fac, e)
        if n % div == 0:
            n //= div
            ans += 1
            e += 1
        else:
            while n % fac == 0:
                n //= fac
            if fac == 2:
                fac += 1
            else:
                fac += 2
            if fac * fac > n:
                break
            e = 1
    if n != 1:
        ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    ans = 0

    fac = 2
    e = 1
    while True:
        div = pow(fac, e)
        if n % div == 0:
            n //= div
            ans += 1
            e += 1
        else:
            while n % fac == 0:
                n //= fac
            fac += 1
            if fac * fac > n:
                break
            e = 1
    if n != 1:
        ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    ans = 0

    fac = 2
    e = 1
    while n % (div := pow(fac, e)) == 0:
        n //= div
        ans += 1
        e += 1

    while n % fac == 0:
        n //= fac

    fac = 3
    e = 1
    while pow(fac, 2) <= n:
        while n % (div := pow(fac, e)) == 0:
            n //= div
            ans += 1
            e += 1

        while n % fac == 0:
            n //= fac
        e = 1
        fac += 2

    if n != 1:
        ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    ans = 0

    fac = 2
    e = 1
    while pow(fac, 2) <= n:
        while n % (div := pow(fac, e)) == 0:
            n //= div
            ans += 1
            e += 1

        while n % fac == 0:
            n //= fac

        e = 1
        fac += 1

    if n != 1:
        ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

k=make_divisors(n)#nの約数のリスト
c=0#操作回数
#2つ目の条件よりnの約数を全て探索する・
#最大回数割るためには小さい約数から順に行うのがベスト
for i in range(len(k)):
    if i==0:pass #約数1をpass
    else:
        l1=factorization(k[i])#i-1番目に小さい約数を素因数分解してn乗数かどうかの確認
        seigo=is_prime(l1[0][0])#そのn乗数が素べきかどうかチェック
        #条件1~3を満たす場合のみ操作を行う
        if len(l1)==1 and seigo==True and n%k[i]==0:#最後に割り切れるかどうかのチェック
            n//=k[i]
            c+=1
        
print(c)

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
    
fact = factorization(N)

import math

ans = 0

if N!= 1:
    
    for f in fact:
        X = f[1]
        n = math.ceil(math.sqrt(2*X)-1)
        if n * (n+1) > 2* X:
            n = n-1
            
        ans += n
        
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

from collections import Counter

n = int(input())
if n == 1:
    print(0)
else:
    a = prime_factorize(n)
    c = Counter(a)
    ans = 0
    for v in c.values():
        temp = 1
        while True:
            v -= temp
            if v >= 0:
                ans +=1
                temp += 1
            else:
                break
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
d={}

for i in range(2, int(n**0.5)+1):
    while n % i == 0:
        if n<2:
            break
        d[i] = d.get(i, 0)+1
        n //=i
    if n<2:
        break
if n>1:
    d[n] = 1
def get(n):
    cur, total = 0, 0
    while cur+total<n:
        cur +=1
        total +=cur
    return cur
ans = 0
for v in d.values():
    ans += get(v)
print(ans)

Submission status: Accepted

Solution code:
import sys

n = int(input())

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

count = 0
i = 2

while True:
    if i * i > n:
        break

    e = 0
    while n % i == 0:
        n = n // i
        e += 1
    curr = 1
    while e >= curr:
        e -= curr
        curr += 1
        count += 1
    i += 1

if n > 1:
    print(count + 1)
else:
    print(count)

Submission status: Accepted

Solution code:
n=int(input())
d={2:0}
while n%2<1:  n//=2;  d[2]+=1
for i in range(3,int(n**0.5)+1,2):
  while n%i<1:  n//=i;  d[i]=d.get(i,0)+1
  if n<2: break
if n>1: d[n]=1
a=0
for i in d.values():
  t=c=0
  while t+c<i: c+=1; t+=c
  a+=c
print(a)

Submission status: Accepted

Solution code:
n=int(input())

int_sqrt=lambda x:int(x**0.5)+1
def prime_factor(x):
  d={}
  for i in p:
    while x%i<1:
      x//=i
      d[i]=d.get(i,0)+1
    if x<2: break
  if x>1: d[x]=1
  return d

p=range(2,int_sqrt(n))
d=prime_factor(n)
a=0
for i in d.values():
  t=c=0
  while t+c<i: c+=1; t+=c
  a+=c
print(a)

Submission status: Accepted

Solution code:
n=int(input())

int_sqrt=lambda x:int(x**0.5)+1
def sieve(x):
  p=[]
  b=[1]*x
  for i in range(2,x):
    if b[i]:
      p+=[i]
      for j in range(2*i,x,i): b[j]=0
  return p
def prime_factor(x):
  d={}
  for i in p:
    while x%i<1:
      x//=i
      d[i]=d.get(i,0)+1
    if x<2: break
  if x>1: d[x]=1
  return d

p=sieve(int_sqrt(n))
d=prime_factor(n)
a=0
for i in d.values():
  t=c=0
  while t+c<i: c+=1; t+=c
  a+=c
print(a)

Submission status: Accepted

Solution code:
# Python program to print prime factors 

import math 

def primeFactors(n):
    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)
    
    return A
        


N = int(input())
primes = set(primeFactors(N))
answer = 0
for p in primes:
    d = p
    while N%d == 0:
        answer += 1
        N //= d
        d *= p
 
print(answer)

Submission status: Accepted

Solution code:
def get_prime_factorizations(n):
    """
    [summary]

    Parameters
    ----------
    n : int
        the number factorized by prime numbers.

    Returns
    -------
    dict[int: int]
        prime and exponent pair
        ex.) if n == 40, the function return  {2:3, 5:1} 
    """    
    root_n = int( n**(1/2) )
    primes = {2:0}
    primes.update({i:0 for i in range(3, root_n+1, 2)})
    for i in primes.keys():
        if n == 1:
            primes = {i: v for i, v in primes.items() if v > 0}
            return primes
        # count exponent
        exponent = 0
        while n % i == 0:
            n //= i
            exponent += 1
        # store the prime and exponent
        primes[i] = exponent

    primes = {i: v for i, v in primes.items() if v > 0}

    if n!=1:
        primes[n] = 1

    if len(primes) == 0:
        return {n: 1}
    return primes

n = int(input())
if n == 1:
    print(0)
else:
    primes =  get_prime_factorizations(n)
    result = 0
    for exponent  in primes.values():
        count = 0
        while exponent - count > 0:
            count += 1
            exponent -= count
        result += count
    print(result)

Submission status: Accepted

Solution code:
def d_div_game():
    def prime_factorization(n):
        """n を素因数分解したときの素数とその指数の辞書"""
        from collections import defaultdict
        if n == 1:
            return {2: 0}  # 1 は素数の 0 乗の積とみなす
        i, table = 2, defaultdict(int)
        while i**2 <= n:
            while n % i == 0:
                table[i] += 1
                n //= i
            i += 1
        if n > 1:
            table[n] = 1
        return table

    def sub(n):
        """1 + ... + e = e*(e+1)//2 <= n となる最大の e を返す"""
        for e in range(1, n + 2):
            if e * (e + 1) > 2 * n:  # e = n + 1 は必ずこの不等式を満たす
                return e - 1

    return sum(sub(v) for v in prime_factorization(int(input())).values())

print(d_div_game())

Submission status: Accepted

Solution code:
from collections import defaultdict
import decimal
import sys
input = sys.stdin.readline


def prime_factor_count(n):
    def count(n, i):
        cnt = 0
        while n % i == 0:
            cnt += 1
            n //= i
        return n, cnt

    d = {}
    if n == 1:
        return d

    n, cnt = count(n, 2)
    d[2] = cnt

    lst = [2]
    for num in range(3, int(n ** 0.5) + 1, 2):
        if n == 1:
            break
        for p_num in lst:
            if num % p_num == 0:
                break
            elif p_num * p_num > num:
                lst.append(num)
                n, cnt = count(n, num)
                d[num] = cnt
                break
    else:
        if n != 1:
            d[n] = 1
    return d



def main():
    n = int(input())
    d = prime_factor_count(n)

    cnt = 0
    tmp_n = 0
    for k, v in d.items():
        exp_cnt = 1
        while 1:
            if exp_cnt > v:
                break
            else:
                if tmp_n % (tmp_exp := k ** exp_cnt) == 0:
                    tmp_n //= tmp_exp
                    cnt += 1
                    v -= exp_cnt
                    exp_cnt += 1
    else:
        if n == tmp_n:
            cnt += 1
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if i!=1:
                divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def resolve():
    N = int(input())
    divs = make_divisors(N)
    divs.sort()
    count = 0
    pdivs = []
    while divs:
        pdivs.append(divs[0])
        divs = [i for i in divs if i % divs[0] != 0]

    count = 0
    for i in pdivs:
        x = i
        while N % x ==0:
            count +=1
            N //= x
            x *= i
    print(count)
resolve()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

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

N = ir()
primes = set(prime_factorize(N))
answer = 0
for p in primes:
    d = p
    while N%d == 0:
        answer += 1
        N //= d
        d *= p

print(answer)

Submission status: Accepted

Solution code:
import collections

def trial_division(n):
    if n < 2:
        return []
    
    prime_factors = []

    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            prime_factors.append(i)
            n //= i
    
    if n > 1:
        prime_factors.append(n)
    
    return prime_factors

counter = 0
if __name__ == "__main__":
    N = int(input())
    
    c = collections.Counter(trial_division(N))
    for primary_number, count in c.items():
        for i in range(1, count+1):            
            z = primary_number ** i
            if N % z == 0:
                counter += 1
                N //= z
    
    print(counter)

Submission status: Accepted

Solution code:
def factorize(n):
    res = []
    i = 2
    while i * i <= n:
        cnt = 0
        while n % i == 0:
            cnt += 1
            n //= i
        if cnt > 0:
            res.append([i, cnt])
        i += 1
    if n != 1:
        res.append([n, 1])
    return res

n = int(input())
nlist = factorize(n)
ans = 0
for j in range(0, len(nlist)):
    sum_ = 1
    i = 2
    while nlist[j][1] >= sum_:
        sum_ += i
        i += 1
    ans += i-2
print(ans)

Submission status: Accepted

Solution code:
import collections as cl
n = int(input())


# N: 素因数分解する数

res = []
x = n
y = 2
while y*y <= x:
    while x % y == 0:
        res.append(y)
        x //= y
    y += 1
if x > 1:
    res.append(x)
res = cl.Counter(res)
#print(res)

ans = 0

for i in res.values():
    temp = 1
    while True:
        i -= temp
        if i >= 0:
            ans +=1
            temp += 1
        else:
            break

print(ans)

Submission status: Accepted

Solution code:
from math import sqrt

n = int(input())
p = n
count = 0

for i in range(2, int(sqrt(n)) + 1):
    e = 1
    while n % i ** e == 0:
        n //= i ** e
        count += 1
        e += 1
    if n % i == 0:
        while n % i == 0:
            n //= i

if n != 1:
    count += 1
if count == 0 and p != 1:
    count = 1

print(count)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue
from decimal import Decimal

# import fractions

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def prime_fact(N):
    n = 2
    prime = []
    while n * n <= N:
        i = 0
        while N % n == 0:
            N //= n
            i += 1
        if i > 0:
            prime.append((n, i))
        n += 1
    if N != 1:
        prime.append((N, 1))
    return prime


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    prime = prime_fact(N)

    ret = 0
    for p, e in prime:
        i = 1
        while e >= i:
            e -= i
            i += 1
            ret += 1
    print(ret)


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

import math
def myFactorization(n):
    '''nを素因数分解する

    戻り値: factList = [[prime1, exp1], [prime2, exp2],...] 
           n=(prime1)**exp1 * (prime2)**exp2 * ...
    '''

    factList=[]
    temp=n
    cnt=0
    while(temp%2==0):
        temp=temp//2
        cnt+=1
    if(cnt>0):
        factList.append([2,cnt])

    m=int(math.sqrt(n))+1
    for i in range(3,m+1,2):
        cnt=0
        while(temp%i==0):
            temp=temp//i
            cnt+=1
        if(cnt>0):
            factList.append([i,cnt])
        if(temp==1):
            break
    if(temp>1):
        factList.append([temp,1])
    return factList            


def readinput():
    n=int(input())
    return n

def possibleCnt(n):
    cnt=0
    resu=n
    for i in range(1,n+1):
        if resu >= i:
            cnt+=1
            resu-=i
            #print(cnt,resu)
    return cnt       

def main(n):
    #ansList=factorization(n)
    ansList=myFactorization(n)
    #print(ansList)
    count=0
    for l in ansList:
        if(l[0]!=1):
            count+=possibleCnt(l[1])
    return count    


if __name__=='__main__':
    n=readinput()
    ans=main(n)
    print(ans)

Submission status: Accepted

Solution code:
def searchPrime(n):
    i = 2
    p_list = []
    while i * i <= n:
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt != 0:
            p_list.append([i, cnt])
        i += 1
    if n != 1:
        p_list.append([n, 1])
    return p_list

n = int(input())
p_list = searchPrime(n)

ans = 0
for p in p_list:
    i = 1
    while p[1] > 0:
        p[1] = p[1] - i
        if p[1] >= 0:
            ans += 1
        i += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())

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

e = defaultdict(int)
for i in range(2, int(N ** 0.5) + 1):
    while N % i == 0:
        e[i] += 1
        N //= i
if N != 1:
    e[N] += 1


if len(e) == 0:
    print(1)
    exit()

ans = 0
for k, v in e.items():
    tmp = 0
    i = 0
    while tmp + i + 1 <= v:
        i += 1
        tmp += i
    ans += i

print(ans)

Submission status: Accepted

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

def pF(n):
	fList = []
	while (n%2 == 0):
		fList.append(2)
		n = n//2

	x = int(math.sqrt(n))
	for i in range(3,x+1,2):
		while (n%i == 0):
			fList.append(i)
			n = n//i

	if n>2:
		fList.append(n)

	return set(fList)

pSet = pF(n)

ans = 0

for p in pSet:
	i = 1
	while (n%(p**i)==0):
		n = n//(p**i)
		ans += 1
		i += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
n = N
fs = {}
f = 2
while n > 1:
  if f*f > n:
    if n not in fs:
      fs[n] = 0
    fs[n] += 1
    n = 1
  elif n%f == 0:
    if f not in fs:
      fs[f] = 0
    fs[f] += 1
    n = n//f
  else:
    f += 1
#print(fs)
rs = []
for f in fs:
  n = fs[f]
  for r in range(1, 256):
    if (r+1)*(r+2)//2 > n:
      rs.append(r)
      break
r = sum(rs)
print(r)

Submission status: Accepted

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

    if tmp != 1:
        res.append((tmp, 1))

    # 素数
    if len(res) == 0:
        res.append((n, 1))

    return res

n = int(input())
if n == 1:
    print(0)
    exit()
cnt = 0
l = factorization(n)
for i, p in l:
    for pp in range(1, p+1):
        if n % (i**pp) == 0:
            n //= i**pp
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import numpy as np
import sys
A=a=int(input())
count=2
samenumcount=0
y=[]
 
if A==1:
    print(0)
    sys.exit()
 
while A!=1 and count<np.sqrt(a):
    if A%count==0:
        samenumcount+=1
        y.append(count**samenumcount)
        A=A/count
    else:
        count+=1
        samenumcount=0
if A!=1:
    y.append(A)
y.sort()
count2=0
for i in y:
    if a==1:
      break
    if a%i==0:
        a=a/i
        count2+=1
 
if count2==0:
    count2+=1

print(count2)

Submission status: Accepted

Solution code:
def factorization(n):
    factors = []
    i = 2
    cnt = 0
    while i ** 2 <= n:
        while n % i == 0:
            n //= i
            cnt += 1
        if cnt > 0:
            factors.append((i, cnt))
        i += 1
        cnt = 0
    if n > 1:
        factors.append((n, 1))
    return factors


n = int(input())
print(sum([int((-1 + (1 + 8 * v[1]) ** 0.5) / 2) for v in factorization(n)]))

Submission status: Accepted

Solution code:
n=int(input())
d={}
for k in range(2,10**6):
  while n%k<1: n//=k; d[k]=d.get(k,0)+1
if n>1: d[n]=1
a=0
for i in d.values():
  t=c=0
  while t+c<i: c+=1; t+=c
  a+=c
print(a)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
        
    N=I()
    n=int(N**0.5)+1
    ans=0
    
    def make_divisors(n):
        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
    
    div=make_divisors(N)
    if len(div)==2:
        ans+=1
    else:
        ans=0
        for d in div:
            div2=make_divisors(d)
            if N==0:
                break
            if len(div2)==2:
                p=div2[-1]
                p2=p
                while N%p2==0:
                    N=N//p2
                    p2*=p
                    ans+=1

        
            
    
    
            
    print(ans)

main()

Submission status: Accepted

Solution code:
N = int(input())

ans = 0
temp = N
fact = []

if N == 1:
    print(0)
    exit()
for i in range(2, int(N ** 0.5 + 2)):
    if temp % i == 0:
        n = 0
        while temp % i == 0:
            temp //= i
            n += 1
        fact.append(n)
if temp != 1:
    fact.append(1)

ans = 0
for f in fact:
    n = f
    i = 1
    while True:
        n -= i
        i += 1
        if n < 0:
            break
        ans += 1

print(max(ans, 1))

Submission status: Accepted

Solution code:
import collections
def prime_factor(n):
    res = collections.Counter()
    i = 2
    while i*i <= n:
        while n % i == 0:
            res[i] += 1
            n //= i
        i += 1
    if n != 1:
        res[n] = 1
    return res

def solve(n):

    tmp = prime_factor(n)

    ans = 0
    x = 0
    for v in tmp.values():
        i = 1
        while i <= v: 
            if v - i >= 0:
                v -= i
                ans += 1
            else:
                x += 1
            i += 1
    ans += x // 2
    return ans


if __name__ == "__main__":
    n = int(input())
    print(solve(n))

Submission status: Accepted

Solution code:
n = int(input())

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""

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
ch = 0
tmp = 0
if n == 1:
    print(0)
    exit()

for fn in factorization(n):
    while True:
        ch += 1
        if fn[1] >= ch:
            fn[1] -= ch
            tmp += 1
        else:
            break
    ans += tmp
    tmp = 0
    ch = 0
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])

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

    return arr
  
n = int(input())

fact = factorization(n)
cnt = 0
for f in fact:
  if f[0] == 1:
    continue
  i = 1
  while True:
    f[1] -= i
    i += 1
    if f[1] < 0:
      break
    cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
# Nまでの素数を全て出す
# 素数をすべて出す
# 小さい順から
import math
N = int(input())
s = {}

for i in range(2, math.ceil(math.sqrt(N))):
    mod = N % i
    while mod == 0:
        s[i] = s.get(i, 0) + 1
        N = N // i

        if N == 0:
            break

        mod = N % i
if not N == 1:
    s[N] = s.get(N, 0) + 1

count = 0

for prime in s:
    pow = s[prime]

    if pow == 1:
        count += 1
        continue

    for i in range(1, pow+1):
        pow -= i
        if pow < 0:
            count += i - 1
            break

        if pow == 0:
            count += i
            break

print(count)

Submission status: Accepted

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10**6)

n=int(input())

m=int(np.sqrt(n))+1

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

ans=0
for i in range(2,m):
    cnt=0
    for j in range(44):
        if n%i==0:
            n=n/i
#            print("i=",i,"n=",n)
            cnt+=1
        else:
            break
    if 1<=cnt<3:
        ans+=1
    if 3<=cnt<6:
        ans+=2
    if 6<=cnt<10:
        ans+=3
    if 10<=cnt<15:
        ans+=4
    if 15<=cnt<21:
        ans+=5
    if 21<=cnt<28:
        ans+=6
    if 28<=cnt<36:
        ans+=7
    if 36<=cnt<45:
        ans+=8

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

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

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

fact = factorization(n)
cnt = 0
for f in fact:
  if f[0] == 1:
    continue
  i = 1
  while True:
    f[1] -= i
    i += 1
    if f[1] < 0:
      break
    cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    NN=N=ii()
    ans = 0
    for i in range(2, int(N**0.525)+1):
        c = i
        while N%c == 0:
            N //= c
            c *= i
            ans += 1
        while N%i==0:
            N//=i
    if N>1:
        ans += 1
    print(ans)





main()

Submission status: Accepted

Solution code:
n=int(input())
def calc(n):
  dic={}
  f=2
  while f*f<=n:
    if n%f==0:
      if f in dic:
        dic[f]+=1
      else:
        dic[f]=1
      n//=f
    else:
      f+=1
  if n!=1:
    if n in dic:
      dic[n]+=1
    else:
      dic[n]=1
  return dic

def ans_count(dic):
  ans=0
  for val in dic.values():
    k=1
    while k*(3+k)//2<val:
      k+=1
    ans+=k
  return ans

print(ans_count(calc(n)))

Submission status: Accepted

Solution code:

import random, math

def parse():
  return int(input())

def is_prime3(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

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():
  N = parse()
  if N == 1:
    print(0)
    exit(0)
  elif is_prime3(N):
    print(1)
    exit(0)

  factors = factorization(N)
  
  factors_dict = {}
  for factor in factors:
    factors_dict[factor[0]] = factor[1]
  # print(factors_dict)

  ans = 0
  last_flag = False
  for p, e in factors_dict.items():
    # 素数ごとに繰り返す
    i = 1
    while e >= i:
      e -= i
      i += 1
      ans += 1
    
    # if e > 0:
    #   last_flag = True
  
  if last_flag:
    ans += 1
  print(ans)

if __name__ == "__main__":
  main()