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 math
import sys
from collections import Counter

N = int(input())
Ns = N
Nso = []
i = 0
if N == 1:
    print(0)
    sys.exit()

Nruto = math.sqrt(N)
Nruto = math.floor(Nruto)


# 素因数分解していきますpart2
for i in range(2, Nruto+1):
    while N % i == 0:
        N = N//i
        Nso.append(i)
    if N == 1:
        break
    Nruto = math.sqrt(N)
    Nruto = math.floor(Nruto)

Nso.append(N)
if 1 in Nso:
    Nso.remove(1)

# Nso^xの形にカウントしていきます
Nso.sort()
Nso = Counter(Nso)


# 設問の操作をしていきます
x = 0
count = 0
xcount = 0
while Ns > 1 and x <= len(Nso):
    for x in Nso.keys():
        for y in range(1, Nso[x]+1, +1):
            if Ns % (x**y) == 0:
                count = count+1
                Ns = Ns/(x**y)
                xcount = xcount+y
            else:
                break

print(count)

Submission status: Accepted

Solution code:
import math
import sys
from collections import Counter

import time

N = int(input())
Ns = N


def create_sosu(n, max, Nso):
    for i in range(2, max+1):
        if n % i == 0:
            while n % i == 0:
                n = n // i
                Nso.append(i)
            return create_sosu(n, int(math.sqrt(n)), Nso)

    # 最後まで来た場合 = その値が素数の場合
    # ただし1は素数ではない
    if n != 1:
        Nso.append(n)
    return Nso


def execute_answer(n, kv):
    # 設問の操作をしていきます
    x = 0
    count = 0
    xcount = 0
    while n > 1 and x <= len(kv):
        for x in kv.keys():
            for y in range(1, kv[x]+1, +1):
                if n % (x**y) == 0:
                    count = count+1
                    n = n//(x**y)
                    xcount = xcount+y
                else:
                    break
    print(count)


def main():

    # Nが1の場合にはそのまま終了
    if N == 1:
        print(0)
        return

    # Nが1以外の場合
    # 素数一覧を作成する
    Nso = create_sosu(N, int(math.sqrt(N)), [])
    execute_answer(Ns, Counter(Nso))


main()

Submission status: Accepted

Solution code:
import collections

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

    return prime_factor

n = int(input())
c = prime_factorize(n)
ans = 0
for i in c.values():
    tmp = 0
    for j in range(1, i+1):
        tmp += j
        if tmp > i:
            break
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N=int(input())
soinsu=defaultdict(int)
x=2
while x<=10**6:
  while N%x==0:
    soinsu[x]+=1
    N//=x
  x+=1
  
if N>1:
  soinsu[N]+=1
  
ans=0
for key in soinsu.keys():
  x=1
  while soinsu[key]>=x:
    ans+=1
    soinsu[key]-=x
    x+=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:
n=int(input())
a=[]
ans=0
for i in range(2,n):
    if i*i>n:
        break
    x=0
    while n%i==0:
        n//=i
        x+=1
    a.append(x)
if n!=1:
    ans+=1

for i in a:
    b=1
    while b<=i:
        i-=b
        b+=1
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

s = []
for i in range(2, int(n**0.5)+1):
  t = 0
  while n%i == 0:
    n //= i
    t += 1
  s.append(t)
  if n == 1: break

if n > 1: s.append(1)

ans = 0
for i in s:
  for j in range(1, i+1):
    if i >= j:
      ans += 1
      i -= j
    else:
      break
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


# print(factorization(0))
n = int(input())
if n == 1:
    print(0)
    exit()
n_fact = factorization(n)
ans = 0
# print(n_fact)

for i in n_fact:
    j = 1
    while i[1] >= j:
        ans += 1
        i[1] -= j
        j += 1

print(ans)

Submission status: Accepted

Solution code:
import collections
N = int(input())
root = int(N**0.5+3)
l = [0] * root
t = [0] * root
c = [0] * root
for i in range(2,root):
    while N % i ==0:
        N = N/i
        l[i] +=1
    t[i] = l[i]
        
    j = 1
    while l[i]- j >=0:
        l[i] =l[i] - j
        j = j +1
        
    c[i] = j -1

if N >1:
    a = 1
else:
    a =0
    
#print(t)
#print(l)

print(sum(c)+a)

Submission status: Accepted

Solution code:
import math

N = int(input())

def primeFactors(n):
        while n % 2 == 0:
                yield 2
                n /= 2
        
        for i in range(3, int(math.sqrt(n)) + 1, 2):
                while n % i == 0:
                        yield i
                        n /= i

        if n > 2:
                yield n


def cn(n):
        i = 1
        count = 0
        while n >= i:
                n -= i
                count += 1
                i += 1
        return count


res = 0

check = list(primeFactors(N))

while check:
        g = check[0]
        num = check.count(g)
        res += cn(num)
        del check[:num]

print(res)

Submission status: Accepted

Solution code:
#因数分解
#N=24ならばa=[2, 2, 2, 3]　のように素因数が昇順の配列で返される
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から1,2,3...とどこまで引けるか数える
#引けなくなったらその前でストップ
#引ける回数(=最大で引ける数)を返す
#N=5であれば、1,2まで引けて3は引けない(負になる)ので2を返す
def cn(n):
  i=1
  count=0
  while n >= i:
    n=n-i
    count+=1
    i+=1
  return count;

N=int(input())
#checkに素因数リストを格納
check=prime_factorize(N)

ans=0

while check:
  #最小の素因数を取得
  get=check[0]
  #getを数える、すなわちある素数が何乗か調べる
  num=check.count(get)
  #与えられた手順をある素数に対して何回行えるか
  ans+=cn(num)
  #使った素数はリストから消す
  del check[:num]
  
print(ans)

Submission status: Accepted

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


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


def main():
	n=II()

	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]=1
	#print(pf)

	li={}
	for k in pf:
		li[pf[k]]=li.get(pf[k],0)+1
	#print(li)

	p=[]
	for i in range(10):
		p+=[i]*(i+1)
	#print(p)

	ans=0
	for i in li:
		ans+=li[i]*p[i]
	print(ans)







if __name__ == "__main__":
	main()

Submission status: Accepted

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

def factorization(num):
    import math
    # 因数分解した結果をタプルのリストで返す
    # [(prime, count), ...]
    MAX_PRIME = int(math.sqrt(num)) + 1
    primes = []
    is_prime = [True] * (MAX_PRIME+1)
    for i in range(2, MAX_PRIME+1):
        if is_prime[i]:
            primes.append(i)
            for j in range(2*i, MAX_PRIME+1, i):
                is_prime[j] = False
    insu = []
    tmp = num
    max_count = 0
    for i in range(len(primes)):
        count = 0
        while tmp%primes[i] == 0:
            tmp //= primes[i]
            count += 1
        if count > 0:
            insu.append((primes[i], count))
            max_count = max(max_count, count)
        if tmp == 1:
            break
    if tmp != 1:
        insu.append((tmp, 1))
    return insu

def main():
    N = int(input())
    insu = factorization(N)
    ans = 0
    for p, c in insu:
        ans += int((-1 + pow(1 + 8 * c, 0.5)) / 2)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
# 素因数分解
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 cn(n):
  i=1
  count=0
  while n >= i:
    n=n-i
    count+=1
    i+=1
  return count;


#1入力
N=int(input())
#X,Y=(int(x) for x in input().split())
#print(N)
#複数入力
#A=input().split()
#A_int = [int(s) for s in A]
#print(A_int)
#print(N)
check=prime_factorize(N)
#print(check)
#print(check[0])
ans=0;

#ここからループ
while check:
  get=check[0]
  num=check.count(get)
  del check[:num]
  #print(check)
  #print(get,num)
  ans+=cn(num)
  
print(ans)

Submission status: Accepted

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

class Factorization:	
	def __init__(self):
		# privateなインスタンス変数を作成
		self.__factors = dict()
		self.__n = 0
	
	
	def get_factors(self, n):
		# [summary] 素因数分解した結果を、辞書([素因数, 指数]...)で返す
		self.__factors.clear()
		self.__n = n
		
		if n < 2:
			# 2より小さい数の場合、素因数分解できない
			return { n:1 }
		else:
			self.__factorization()
			
			return self.__factors
	
	
	def get_divisors(self, n):
		# [summary] 約数をリストに列挙
		self.__factors.clear()
		self.__n = n
		
		if n < 2:
			return [1]
		else:
			self.__factorization()
			divisors = [1]
			
			for k, v in self.__factors.items():
				import copy
				copy_ = copy.deepcopy(divisors)
								
				for i in range(1, v + 1):
					for c in copy_:
						divisors.append(c * (k ** i))
			
			return divisors

				
	def count_divisors(self, n):
		# [summary] 約数の個数を返す
		self.__factors.clear()
		self.__n = n
		
		if n < 2:
			return 1
		else:
			self.__factorization()
			count = 1
			
			for v in self.__factors.values():
				count *= v + 1
			
			return count
	

	def	__factorization(self):
		# [summary]素因数分解した結果を、インスタンス変数に格納
		
		# 2,3,5で、割れなくなるまで割り続ける
		# (末尾に2,3,5のつく数は素数でないことが明白なので
		# 後続の処理で素数のリストに入れないように、先に処理する)
		self.__divide_with(2)
		self.__divide_with(3)
		self.__divide_with(5)
			
		# 平方根以下の素数で総当たりで試し割りする
		# (実際は、素数らしき数)
		import math
		sqrt_ = math.floor(math.sqrt(self.__n))
			
		primes = [7, 11, 13, 17, 19, 23, 29, 31]
		i = 0
		is_break = False
			
		while self.__n > 1:
			for p in primes:
				if p + i <= sqrt_:
					self.__divide_with(p + i)
				else:
					# 試し割りする数が平方根を超えたら、ループを抜ける
					is_break = True
						
					# 1が素因数に追加されることを防止
					if self.__n > 1:
						self.__factors.setdefault(self.__n, 1)
				
			if is_break:
				break
			else:
				i += 30
	
	
	def __divide_with(self, d):
		count = 0
		
		while self.__n % d == 0:
			self.__n //= d
			count += 1
		
		if count > 0:
			self.__factors.setdefault(d, count)


# D - Div Game
n = int(input())

if n == 1:
	print(0)
else:
	lib = Factorization()
	factors = lib.get_factors(n)

	ans = 0

	for v in factors.values():
		count = 0
		sum = 0
		i = 1
	
		while True:
			count += 1
			sum += i
		
			if sum > v:
				count -= 1
				break
			elif sum == v:
				break
			else:
				i += 1 
	
		ans += count

	print(ans)

Submission status: Accepted

Solution code:
import sys
import time
st = time.perf_counter()
# ------------------------------


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

from itertools import groupby
N = int(input())
P = prime_decomposition(N)
ans = 0
for k, g in groupby(P):
    n = len(list(g))
    for i in range(1, 10000000):
        n -= i
        if n >=0:
            ans += 1
        else:
            break
print(ans)

        
        



# ------------------------------
ed = time.perf_counter()
print('time:', ed-st, file=sys.stderr)

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

def count_make_fact(n):
    count = 1
    while n - count >= 0:
        n -= count
        count += 1
    return count-1

n = int(input())

if n == 1:
    print(0)
else:
    factor_list = factorization(n)
    print(sum(map(count_make_fact,(map(lambda list: list[1],factor_list)))))

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

def count_make_fact(n):
    count = 1
    while n - count >= 0:
        n -= count
        count += 1
    return count-1

n = int(input())

if n == 1:
    print(0)
else:
    factor_list = factorization(n)
    list = sum(map(count_make_fact,(map(lambda list: list[1],factor_list))))
    print(list)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())

def factorint(N):
    """
    Nを作っている素数を辞書で返す．
    input 100
    output Counter({2: 2, 5: 2})
    """
    table = []
    tmp = 2
    while(N > 1):
        for i in range(tmp,N+1):
            if N%i == 0:
                while N%i == 0:
                    N = N//i
                    table.append(i)
                tmp = i+1
                break
    table_ = collections.Counter(table)
    return table_

def primes(n): #試し割り法で各素因数とその指数を求める
    cnt=collections.defaultdict(int)
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            while n%i==0:
                cnt[i]+=1
                n//=i
    if n!=1:
        cnt[n]+=1
    return cnt

# factors = factorint(N)
factors = primes(N)
ans = 0

for key in factors.keys():
    f_c = factors[key]
    tmp = 1
    while f_c >= tmp:
        ans += 1
        f_c -= tmp
        tmp += 1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)


from math import sqrt, floor, factorial, gcd, log
from collections import deque, Counter, defaultdict
from itertools import permutations
from math import gcd
from bisect import bisect

input = lambda: sys.stdin.readline().rstrip("\r\n")
read = lambda: list(map(int, input().strip().split(" ")))

def p_factors(n):
    # arr = []
    dic = defaultdict(int)
    for i in range(2, int(sqrt(n)+1)):
        if n%i == 0:
            c = 0
            while n%i==0:
                c += 1
                n//=i
            dic[i] = c
    if n > 1:dic[n] = 1
    return(dic)



def solve():
    dic = {((i*(i+1))//2): i for i in range(30)}
    powers = list(p_factors(int(input())).values())
    # print(dic)
    # print(powers)
    ans = 0
    for i in powers:
        if i in dic:
            ans += dic[i]
        else:
            while i not in dic: i-= 1
            ans += dic[i]
    print(ans)




        

if __name__ == "__main__":
	solve()

Submission status: Accepted

Solution code:
import math
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([i, cnt])

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

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

    return arr

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

n = int(input())
if n==1:
    print(0)
elif is_prime(n):
    print(1)
else:
    cnt = 0
    P = fac(n)
    for p,_ in P:
        c = 1
        while n%pow(p,c)==0:
            n /= pow(p,c)
            cnt += 1
            c += 1
    print(cnt)

Submission status: Accepted

Solution code:
from numba import jit
N = int(input())

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

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

li = factorization(N)
ans = 0
for i in li:
    k = i[1]
    loop = 1
    while True:
        k -= loop
        if k>=0:
            ans += 1
        else:
            break
        loop += 1
if N==1:
    print(0)
else:
    print(ans)

Submission status: Accepted

Solution code:
from numba import jit
N = int(input())

"""nを素因数分解"""
"""2以上の整数n => [(素因数, 指数), ...]の2次元リスト"""
@jit
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

li = factorization(N)
ans = 0
for i in li:
    k = i[1]
    loop = 1
    while True:
        k -= loop
        if k>=0:
            ans += 1
        else:
            break
        loop += 1
if N==1:
    print(0)
else:
    print(ans)

Submission status: Accepted

Solution code:
# oreder(√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

import collections
def smallest_prime_factors(n):

    spf = [[] for _ in range(n+1)]
    for i in range(n+1):
        spf[i] = i
    i = 2
    while i*i <= n:
        if spf[i] == i:
            for j in range(i*i, n+1, i):
                if spf[j] == j:
                    spf[j] = i
        i += 1

    return spf

def factolization(x,spf):
    ret = []
    while (x != 1):
        ix = int(x)
        ret.append(spf[ix])
        x /= spf[ix]
    return sorted(ret)


import sys
# x,y = map(int,input().split())
n = int(input())
ans = 0
facts = factorization(n)
if n == 1:
    pass
else:
    for fact in facts:
        beki = fact[1]
        b = 1
        while b <= beki:
            beki -= b
            b += 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))+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())
 
arr = factorization(n) 
# print(arr)
 
cnt = 0
if n == 1:
    pass
else:
    for ar in arr:
        i = 1
        while 1:
            ar[1]-=i
            if ar[1] < 0:
                break
            cnt += 1
            i+=1
print(cnt)

Submission status: Accepted

Solution code:
#素因数分解
def prime_factor(n):#nは引数
    factors = []
    for i in range(2,int(n**0.5)+1):
        while n%i==0:
            factors.append(i)
            n = n//i
    if n!=1:
        factors.append(n)
    return factors #list化されたものを返すsetにすれば含まれる素数を列挙できる

N = int(input())
li = prime_factor(N)
tmp = list(set(li))
ans = 0

for i in tmp:
    count = 0
    p = n = 1
    while(li.count(i)>=p):
        count += 1
        n += 1
        p += n
    ans += count

print(ans)

Submission status: Accepted

Solution code:
import math

N = int(input())

def gcd(a, b):
    while b: a, b = b, a % b
    return a

def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1

def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)

def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret

pfacts = primeFactor(N)
ans = 0
for p, e in pfacts.items():
    i = math.floor((-1 + math.sqrt(1 + 8 * e)) / 2)
    ans += i
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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


pri = prime_factorize(N)
c = Counter(pri)
val = list(c.values())

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

Submission status: Accepted

Solution code:
# Problem D - Div Game

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

# check
if N==1:
    print(0)
else:
    count = 0
    fact_list = factorization(N)
    for f in fact_list:
        tmp = f[1]
        i = 1
        while tmp-i>=0:
            count += 1
            tmp -= i
            i += 1
    print(count)

Submission status: Accepted

Solution code:
import collections
def factorization(n):
    if n<2:
        return []
    
    prime_factor=[]
    
    for i in range(2,int(n**0.5)+1):
        while n%i==0:
            prime_factor.append(i)
            n//=i
            
    if n>1:
        prime_factor.append(n)
    return prime_factor

count=0
n=int(input())
 
c=collections.Counter(factorization(n))
d=list(c.values())
 
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:
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 list(set(a))

a = prime_factorize(N)
count, j = 0, 0
for i in a:
    j = 0
    while N % pow(i, j+1) == 0:
        N /= pow(i, j+1)
        j += 1
    count += j
        
print(count)

Submission status: Accepted

Solution code:
# D - Div Game
from collections import deque

def pf(N):
    ans = deque([])
    p = 2
    while N>1:
        if N%p==0:
            k = 0
            while N%p==0:
                N //= p
                k += 1
            ans.append(k)
        p += 1+(p>2)
        if p**2>N:
            p = N
    return ans

def func(a):
    tmp = 0
    while True:
        a -= tmp+1
        if a<0:
            return tmp
        else:
            tmp += 1

N = int(input())
ans = 0
l = pf(N)
while len(l)>0:
    ans += func(l.popleft())
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
#計算量はo(n**0.5)なので間に合う
def fact(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
arr=fact(n)
ans=0
for i in arr:
  k=i[1]
  loop=1
  while True :
    k -=loop
    if k>=0:
      ans+=1
    else:
      break
    loop += 1
    
if n==1:
  print(0)
else:
  print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
i = 2
a = []
x = n
while(i * i <= n):
    if (n % i == 0):
        a.append(i)
        n //= i
        while(n % i == 0):
            n //= i
            a.append(a[-1] * i)
    i += 1
if (n != 1):
    a.append(n)
a.sort(reverse = True)
ans = 0
while(x != 1 and len(a)):
    while(x % a[-1]):
        a.pop()
        if (len(a) == 0):
            break
    if (len(a) == 0):
        break
    x //= a[-1]
    a.pop()
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
use_list = []


def make_prime(n):
    array = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt = cnt + 1
                temp = temp // i
            array[i] = cnt

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

    if array == {}:
        array[n] = 1

    return array


def div_prime(n, count):

    if n == 1:
        return count

    # 素数一覧を取得
    prime_list = make_prime(n)
    for p, e in prime_list.items():
        for i in range(1, e + 1):
            if not p ** i in use_list:
                z = p ** i
                use_list.append(z)
                return div_prime(int(n / z), count + 1)

    return count


N = int(input())
print(div_prime(N, 0))

Submission status: Accepted

Solution code:
N=int(input())
ans=0
for i in range(2,10**6+1):
  anssub=0
  t=0
  while N%i==0:
    N=N//i
    anssub+=1
  while t*(t+1)//2<=anssub:
    t+=1  
  ans+=t-1
if N!=1:
  ans+=1
print(ans)