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 factorization(n):
    m=n
    counter_map={}
    i=2
    tmp=1
    while n!=1:
        #因数に持つか判定
        if n%i==0:
            n=n//i
            #素数判定
            for j in range(2,int(i**(1/2))+1):
                if i%j==0:
                    break
            else:
                tmp*=i
                if i not in counter_map:
                    counter_map[i]=1
                    tmp=1
                else:
                    if tmp not in counter_map:
                        counter_map[tmp]=1
                        tmp=1
        else:
            i+=1
            tmp=1
        if i>int(m**(1/2)) and n!=1:
            counter_map[n]=1
            break
        #print(i,n,counter_map)
    return counter_map


a=int(input())
b=factorization(a)
#print(b)

print(len(b))

Submission status: Accepted

Solution code:
def factorization(n):
    m=n
    counter_map={}
    i=2
    tmp=1
    while n!=1:
        #因数に持つか判定
        if n%i==0:
            n=n//i
            #素数判定
            for j in range(2,int(i**(1/2))+1):
                if i%j==0:
                    break
            else:
                tmp*=i
                if i not in counter_map:
                    counter_map[i]=1
                    tmp=1
                else:
                    if tmp not in counter_map:
                        counter_map[tmp]=1
                        tmp=1
        else:
            i+=1
            tmp=1
        if i>int(m**(1/2)) and n!=1:
            counter_map[n]=1
            break
        #print(i,n,counter_map)
    return counter_map


a=int(input())
b=factorization(a)
#print(b)
print(len(b))

Submission status: Accepted

Solution code:
def factorization(n):
    m=n
    counter_map={}
    i=2
    tmp=1
    while n!=1:
        #因数に持つか判定
        if n%i==0:
            n=n//i
            #素数判定
            for j in range(2,int(i**(1/2))+1):
                if i%j==0:
                    break
            else:
                tmp*=i
                if i not in counter_map:
                    counter_map[i]=1
                    tmp=1
                else:
                    if tmp not in counter_map:
                        counter_map[tmp]=1
                        tmp=1
        else:
            i+=1
            tmp=1
        if i>int(m**(1/2)) and n!=1:
            counter_map[n]=1
            break
        #print(i,n,counter_map)
    return counter_map


a=int(input())
b=factorization(a)
#print(b)
sum=0

# for i in b.keys():
#     counter=0
#     for j in range(1,41):
#         if b[i]>=1+(j+2)*(j-1)//2:
#             counter=j
#         else:
#             break
#     sum+=counter

# print(sum)

print(len(b))

Submission status: Accepted

Solution code:
n = int(input())

def factorization(n):
    arr = []
    if n == 1:
        return 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_list = factorization(n)
ans = 0

for i in range(len(f_list)):
    tmp = f_list[i][1]
    j = 1
    while tmp >= 0:
        tmp -= j
        j += 1
    ans += j-2

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

def factorization(n):
    arr = []
    if n == 1:
        return 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_list = factorization(n)
ans = 0

for i in range(len(f_list)):
    _tmp = f_list[i][1]
    j = 1
    while _tmp >= 0:
        _tmp -= j
        j += 1
    ans += j-2

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import defaultdict


def main():
    n = int(input())
    prime_counter = defaultdict(int)  # key ^ value
    # 10 because 2^39 < 10^12 < 2^40 and accum[9] = 45
    accum = tuple(accumulate(range(10)))

    def facs(n):
        yield 2
        max_prime = int(pow(n, 0.5)) + 1
        for x in range(3, max_prime, 2):
            yield x

    for fac in facs(n):
        while n % fac == 0:
            n //= fac
            prime_counter[fac] += 1
    if n != 1:
        prime_counter[n] += 1

    ans = 0
    for c in prime_counter.values():
        for accum_count, accum_value in enumerate(accum):
            if c < accum_value:
                ans += accum_count - 1
                break
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

n = 0
for p, e in arr:
  temp = e
  j = 0
  while temp > 0:
    j += 1
    temp = temp - j
    if temp < 0:
      break
    n += 1

print(n)

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import defaultdict


def main():
    n = int(input())
    prime_counter = defaultdict(int)  # key ^ value
    accum = tuple(accumulate(range(1, 10)))  # because 10^12 < 2^39

    def facs(n):
        yield 2
        for x in range(3, int(pow(n, 0.5)) + 1, 2):
            yield x

    for fac in facs(n):
        while n % fac == 0:
            n //= fac
            prime_counter[fac] += 1
    if n != 1:
        prime_counter[n] += 1

    ans = 0
    for c in prime_counter.values():
        for accum_count, accum_value in enumerate(accum):
            if c < accum_value:
                break
        ans += accum_count
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import defaultdict


def main():
    n = int(input())
    prime_counter = defaultdict(int)  # key ^ value
    accum = tuple(accumulate(range(1, 38)))  # because 10^12 < 2^39

    def facs(n):
        yield 2
        for x in range(3, int(pow(n, 0.5)) + 1, 2):
            yield x

    for fac in facs(n):
        while n % fac == 0:
            n //= fac
            prime_counter[fac] += 1
    if n != 1:
        prime_counter[n] += 1

    ans = 0
    for c in prime_counter.values():
        for accum_count, accum_value in enumerate(accum):
            if c < accum_value:
                break
        ans += accum_count
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import defaultdict


def main():
    n = int(input())
    prime_counter = defaultdict(int)  # key ^ value
    accum = tuple(accumulate(range(1, 40)))  # because 10^12 < 2^39

    def facs(n):
        yield 2
        for x in range(3, int(pow(n, 0.5)) + 1, 2):
            yield x

    for fac in facs(n):
        while n % fac == 0:
            n //= fac
            prime_counter[fac] += 1
    if n != 1:
        prime_counter[n] += 1

    ans = 0
    for c in prime_counter.values():
        for accum_count, accum_value in enumerate(accum):
            if c < accum_value:
                break
        ans += accum_count
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import defaultdict


def main():
    n = int(input())
    prime_counter = defaultdict(int)  # key ^ value
    accum = tuple(accumulate(range(1, 42)))  # because 10^12 < 2^39

    def facs(n):
        yield 2
        for x in range(3, int(pow(n, 0.5)) + 1, 2):
            yield x

    for fac in facs(n):
        while n % fac == 0:
            n //= fac
            prime_counter[fac] += 1
            # ここで if fac * fac > n: braek を入れると，
            # 計算量の少ないケースでは早く，多いケースでは遅くなる。
    if n != 1:
        prime_counter[n] += 1

    ans = 0
    for c in prime_counter.values():
        for accum_count, accum_value in enumerate(accum):
            if c < accum_value:
                break
        ans += accum_count
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import defaultdict


def main():
    n = int(input())
    prime_counter = defaultdict(int)  # key ^ value
    acc = tuple(accumulate(range(1, 42)))  # because 10^12 < 2^39

    def facs(n):
        yield 2
        for x in range(3, int(pow(n, 0.5)) + 1, 2):
            yield x

    for fac in facs(n):
        while n % fac == 0:
            n //= fac
            prime_counter[fac] += 1
            # ここで if fac * fac > n: braek を入れると，
            # 計算量の少ないケースでは早く，多いケースでは遅くなる。
    if n != 1:
        prime_counter[n] += 1

    ans = 0
    for c in prime_counter.values():
        for i, x in enumerate(acc):
            if c < x:
                tmp = i
                break
        ans += tmp
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import defaultdict


def main():
    n = int(input())
    prime_counter = defaultdict(int)  # key ^ value
    acc = tuple(accumulate(range(1, 42)))  # because 10^12 < 2^39

    def facs(n):
        yield 2
        for x in range(3, int(n ** 0.5) + 1, 2):
            yield x

    for fac in facs(n):
        while n % fac == 0:
            n //= fac
            prime_counter[fac] += 1
            # ここで if fac * fac > n: braek を入れると，
            # 計算量の少ないケースでは早く，多いケースでは遅くなる。
    if n != 1:
        prime_counter[n] += 1

    ans = 0
    for c in prime_counter.values():
        for i, x in enumerate(acc):
            if c < x:
                tmp = i
                break
        ans += tmp
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import defaultdict


def main():
    n = int(input())
    prime_counter = defaultdict(int)  # key ^ value
    acc = tuple(accumulate(range(1, 42)))  # because 10^12 < 2^39

    def facs(n):
        yield 2
        max_x = int(n ** 0.5)
        for x in range(3, max_x+1, 2):
            yield x

    for fac in facs(n):
        while n % fac == 0:
            n //= fac
            prime_counter[fac] += 1
            # ここで if fac * fac > n: braek を入れると，
            # 計算量の少ないケースでは早く，多いケースでは遅くなる。
    if n != 1:
        prime_counter[n] += 1

    ans = 0
    for c in prime_counter.values():
        for i, x in enumerate(acc):
            if c < x:
                tmp = i
                break
        ans += tmp
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import defaultdict


def main():
    n = int(input())
    prime_counter = defaultdict(int)  # key ^ value
    acc = tuple(accumulate(range(1, 42)))  # because 10^12 < 2^39

    def facs(n):
        yield 2
        max_x = int((n ** 0.5 - 3) / 2 + 1)
        for x in range(max_x):
            yield x * 2 + 3

    for fac in facs(n):
        while n % fac == 0:
            n //= fac
            prime_counter[fac] += 1
            # ここで if fac * fac > n: braek を入れると，
            # 計算量の少ないケースでは早く，多いケースでは遅くなる。
    if n != 1:
        prime_counter[n] += 1

    ans = 0
    for c in prime_counter.values():
        for i, x in enumerate(acc):
            if c < x:
                tmp = i
                break
        ans += tmp
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import defaultdict


def main():
    n = int(input())
    prime_counter = defaultdict(int)  # key ^ value
    acc = tuple(accumulate(range(1, 42)))  # because 10^12 < 2^39

    def facs():
        yield 2
        for x in range(10 ** 5 * 5):
            yield x * 2 + 3

    for fac in facs():
        count = 0
        while n % fac == 0:
            n //= fac
            count += 1
            # ここで if braek を入れると遅い？
        prime_counter[count] += 1
    if n != 1:
        prime_counter[1] += 1

    ans = 0
    for prime_count, count_count in prime_counter.items():
        for i, x in enumerate(acc):
            if prime_count < x:
                tmp = i
                break
        ans += tmp * count_count
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter


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


res = prime_factorize(int(input()))

counter = Counter(res)
keys = counter.keys()

result = 0
for key in keys:
    items = counter.get(key)

    start = 1

    while items - start >= 0:
        items = items - start
        result += 1
        start += 1

print(result)

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import defaultdict


def main():
    n = int(input())
    prime_counter = defaultdict(int)  # key ^ value
    acc = tuple(accumulate(range(1, 42)))  # because 10^12 < 2^39

    def facs():
        yield 2
        for x in range(10 ** 5 * 5):
            yield x * 2 + 3

    for fac in facs():
        while n % fac == 0:
            n //= fac
            prime_counter[fac] += 1
            # ここで if braek を入れると遅い？
    if n != 1:
        prime_counter[n] += 1

    ans = 0
    for c in prime_counter.values():
        for i, x in enumerate(acc):
            if c < x:
                tmp = i
                break
        ans += tmp
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import defaultdict


def main():
    n = int(input())
    prime_counter = defaultdict(int)
    acc = tuple(accumulate(range(1, 42)))  # 10^12 < 2^39

    def facs():
        yield 2
        for x in range(10 ** 6):
            yield x * 2 + 3

    for fac in facs():
        while n % fac == 0:
            n //= fac
            prime_counter[fac] += 1
        if fac * fac > n:
            break
    if n != 1:
        prime_counter[n] += 1

    ans = 0
    for c in prime_counter.values():
        for i, x in enumerate(acc):
            if c < x:
                tmp = i
                break
        ans += tmp
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import defaultdict


def main():
    n = int(input())
    prime_counter = defaultdict(int)
    acc = tuple(accumulate(range(1, 42)))  # 10^12 < 2^39

    def facs():
        yield 2
        for x in range(10 ** 6):
            yield x * 2 + 3

    for fac in facs():
        while fac * fac <= n:
            if n % fac == 0:
                n //= fac
                prime_counter[fac] += 1
            else:
                break
    if n != 1:
        prime_counter[n] += 1

    ans = 0
    for c in prime_counter.values():
        for i, x in enumerate(acc):
            if c < x:
                tmp = i
                break
        ans += tmp
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

#########################  ネットから拾ってきた
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
######################### 

pf = prime_factorize(n)

import collections
c = collections.Counter(pf)

for i in sorted(set(pf)):
    res = c[i]
    for j in range(1,50):
        res -= j
        
        if res >= 0:
            ans += 1
            
        else:
            break
            
print(ans)

Submission status: Accepted

Solution code:
import math

n = int(input())
list = {}
flag = True
while flag:
    flag = False
    for i in range(2,int(math.sqrt(n)+2)):
        if n%i==0:
            if i in list:
                list[i] = list[i]+1
            else:
                list[i] = 1
            n /= i
            flag = True
            break
if n>1:
    if n in list:
        list[n] = list[n]+1
    else:
        list[n] = 1
ans = 0
for i in list.keys():
    m = list[i]
    for j in range(1,m+1):
        if not j>m:
            ans += 1
            m -= j
        else:
            break
print(ans)

Submission status: Accepted

Solution code:
def factorize(n):
  fct=[]
  b,e=2,0
  while b*b<=n:
    while n%b==0:
      n=n//b
      e+=1
    if e>0:
      fct.append(e)
    b,e=b+1,0
  if n>1:
    fct.append(1)
  return fct

n=int(input())
ans=0
for i in factorize(n):
  count=1
  while i>=count:
    ans+=1
    i-=count
    count+=1
print(ans)

Submission status: Accepted

Solution code:
import math

#nの素因数分解(O(n**0.5)
def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass


N = int(input())
ans = 0
howmany = []
nums = sorted(prime_factor(N))
if len(nums)>0:
    count = 1
else:
    count = 0
for one, two in zip(nums,nums[1:]):
    if one != two:
        howmany.append(count)
        count = 1
    else:
        count += 1
else:
    howmany.append(count)


for i in howmany:
    for j in range(1,20):
        if j * (j + 1) // 2 > i:

            ans += j - 1
            break

print(ans)

Submission status: Accepted

Solution code:
def factorize(n):
    fct = []
    b,e = 2,0
    while b*b <= n:
        while n % b==0:
            n = n//b
            e += 1
        if e > 0:
            fct.append((b,e))
        b,e = b+1,0
    if n > 1:
        fct.append((n,1))
    return fct

n = int(input())
ans = 0
for i,j in factorize(n):
    ans += -(-int(((1 + 8*j)**(1/2) - 1 )/ 2))
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
#import random
#sys.setrecursionlimit(100000000)
input = sys.stdin.readline
 
############ ---- USER DEFINED INPUT FUNCTIONS ---- ############
def inp():
    return(int(input()))
def inara():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))
################################################################
############ ---- THE ACTUAL CODE STARTS BELOW ---- ############

n=inp()

i=2
fact=[]

while i*i<=n:
	cnt=0
	while n%i==0:
		n//=i
		cnt+=1
	if cnt:
		fact.append(cnt)
	
	i+=1

if n>1:
	fact.append(1)

ans=0

def koyta(n):
	i=1
	curr=0
	while i<=n:
		n-=i
		curr+=1
		i+=1
	
	return curr 

for num in fact:
	ans+=koyta(num)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
from collections import defaultdict
n = I()
def primes(n):
    cnt = defaultdict(int)
    for i in range(2,int(n**0.5)+1): # range(3)だと、0,1,2が出てくる。
        while n % i == 0:
            cnt[i] += 1 # 同じ素数で何回割れるか辞書型で登録しておく
            n //= i # iで割り切った商で更新しておく
    if n > 1: # nの平方根より大きい値があった場合、追加
        cnt[n] += 1
    return cnt
prs = primes(n) #　素数の辞書
ans = 0
for key in prs.keys(): #辞書から素数を抽出して、その素数の指数値をvとして格納する。
    v = prs[key]
    for i in range(100):
        # if (i * (i+1)) // 2 <= v:　これだと何度も足し算してしまう。
        if (i * (i + 1)) // 2 > v: # 指数eを超えた一つ前が目的の計数である。
            ans += (i-1)
            break
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
 
def prime_factorization(n):
    table = []
    for x in range(2, int(n ** 0.5) + 1):
        while n % x == 0:
            table.append(x)
            n //= x
    if n > 1:
        table.append(n)
    return table
 
T = prime_factorization(N)
C = Counter(T)
 
cnt = 0
for v in C.values():
    next = 1
    while v >= next:
        v -= next
        cnt += 1
        next += 1
 
print(cnt)

Submission status: Accepted

Solution code:
def factorize(n):
    fct = []
    b = 2
    e = 0
    while b * b <= n:
        while n % b == 0:
            n //= b
            e += 1
        if e > 0:
            fct.append((b, e))
        b += 1
        e = 0
    if n > 1:
        fct.append((n, 1))
    return fct


n = int(input())

fct = factorize(n)

ans = 0
for i in fct:
    nokori = i[1]
    count = 1
    while nokori >= count:
        nokori -= count
        count += 1
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
ans=0
for i in range(2,1000010):
	power=0
	j=1
	if(n%i==0):
		while(n%i==0):
			power+=1
			n=(n//i)
		while(power>=j):
			power-=j
			j+=1
			ans+=1
if(n>1):
	ans+=1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
ans=0
#it is the power of every prime number
#and as z is always a prime numer we should not bother about
# combiations of prime numer dividing N
for i in range(2,1000010):
	power=0
	j=1
	if(n%i==0):
		while(n%i==0):
			power+=1
			n=(n//i)
		while(power>=j):
			power-=j
			j+=1
			ans+=1
if(n>1):
	ans+=1
print(ans)

Submission status: Accepted

Solution code:
import math

N = int(input())


def prime_factorization(n):
    from collections import Counter
    counter = Counter()

    if n < 2:
        return counter

    for i in range(2, int(n ** 0.5) + 1):
        if i * i > n:
            break

        while n % i == 0:
            counter[i] += 1
            n //= i

    if n > 1:
        counter[n] += 1

    return counter


p_fact = prime_factorization(N)

cnt = 0
for _, e in p_fact.items():
    val = math.sqrt(2 * e + 0.25) - 0.5
    val = int(val)
    cnt += val

print(cnt)

Submission status: Accepted

Solution code:
import numpy as np
import time

def get_sieve(n):
  # エラトステネスの篩
  f = np.ones(n+1, dtype=bool)
  f[0] = f[1] = False
  rn = np.sqrt(n)
  for i in range(2, int(rn)+1):
    if f[i]:
      # 素数
      j = 2
      while 1:
        ij = i * j
        if ij > n:
          break
        f[ij] = False
        j += 1
  return f


N = int(input())

rn = np.sqrt(N)
S = get_sieve(int(rn)+1)

count = 0
primes = []
newN = N
for p, s in enumerate(S):
  if s:
    e = 1
    while 1:
      z = p**e
      if z > newN:
        break
      if newN % z == 0:
        # print(f"{newN}は{z}で割り切れます. N/z={newN//z}")
        newN = newN // z
        count += 1
      e += 1
if newN > rn:
  count += 1
print(count)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(input())

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

ans = 0
for p in facts:
    count = p[1]
    cur = 1
    while count - cur >= 0:
        count -= cur
        ans += 1
        cur += 1

print(ans)

Submission status: Accepted

Solution code:
n=int(input())

def sieve(x):
  p=[2]
  b=[1]*x
  for i in range(2,x,2):  b[i]=0
  for i in range(3,x,2):
    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 sieve(int(x**0.5)+1):
    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

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:
import math
n = int(input())
div = 2
res = 0
m = int(math.sqrt(n))
while div < m:
    cnt = 0
    if ((n // div) * div != n):
        div += 1
        continue
    while (n // div) * div == n:
        cnt += 1
        n = n // div
    #print(div, cnt)
    tmp = 1
    while tmp <= cnt:
        res += 1
        cnt -= tmp
        tmp += 1
    if (n == 1):
        div = m
    div += 1
print(res+1*(n != 1))

Submission status: Accepted

Solution code:
import collections
n=int(input())
if n==1:
  print(0)
  exit()
b=int(n**0.5)
i=2
l=[]
while i<=b:
  if n%i==0:
    l.append(i)
    n=n//i
  else:
    i+=1
if n>b:
  l.append(n)
c=collections.Counter(l)
v=list(c.values())

ans=0
for vv in v:
  wa=1
  s=1
  while True:
    if vv<wa:
      break
    s+=1
    wa+=s
  ans+=(s-1)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
 
def prime_factorise(n):
    a = []
    tmp = n
    for i in range(2, int(n**0.5//1 + 1)):
        if tmp % i == 0:
            index = 0  # 指数
            while tmp % i == 0:
                index += 1
                tmp //= i
            a.append([i, index])
 
    if tmp != 1:
        a.append([tmp, 1])

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

    return a
 
x = prime_factorise(n)
count = 0
 
 
for i in range(len(x)):
    if x[0][0] == 1:
        break
 
    k = x[i][1]  # 指数の値
    for j in range(k):
        if n % (x[i][0] ** (j+1)) == 0:
            n //= x[i][0] ** (j+1)
            count += 1
            k -= (j+1) #指数の値をへらす
 
        elif n % (x[i][0]**(j+1)) != 0:
            break
        
        if k <= 0:
            break
 
print(count)

Submission status: Accepted

Solution code:
"""
- Nを素因数分解する
- N = p[i]^1*p[i]^2...*p[k]^1*p[k]^2...
"""
from collections import Counter
N = int(input())
factors = []
i = 2

while N > 1:
  if N < i * i:
    factors.append(N)
    break
  while N % i == 0:
    factors.append(i)
    N //= i
  i += 1
# N == 1
ans = 0
# print(factors)
# Counter() ->{key:count}
for count in Counter(factors).values():
  i = 1
  while count >= i:
    count -= i
    i += 1
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
def p_f(n):
    res = []
    a = 2
    while a**2 <= n:
        if n % a == 0:
            ex = 0
            while n % a == 0:
                n //= a
                ex += 1
            
            res.append([a, ex]) #割り終わったら素因数と指数を格納
        
        a += 1
    if n > 1: res.append([n, 1]) #最後が素数ならそれも格納
    
    return res

n = int(input())
p_f_l = p_f(n) #素因数分解した結果リスト
ans = 0
for i in p_f_l:
    p = i[0] #素数
    ex = i[1] #指数上限
    for j in range(1,ex+1):
        if n % p**j == 0:
            n //= p**j
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

def prime_factorise(n):
    a = []
    tmp = n
    for i in range(2, int(n**0.5//1 + 1)):
        if tmp % i == 0:
            index = 0  # 指数
            while tmp % i == 0:
                index += 1
                tmp //= i
            a.append([i, index])

    if tmp != 1:
        a.append([tmp, 1])

    return a

x = prime_factorise(n)
count = 0


for i in range(len(x)):
    if x[0][0] == 1:
        break

    k = x[i][1]  # 指数の値
    for j in range(k):
        if n % (x[i][0] ** (j+1)) == 0:
            n //= x[i][0] ** (j+1)
            count += 1
            k -= (j+1) #指数の値をへらす

        elif n % (x[i][0]**(j+1)) != 0:
            break
        # ここの分岐とおるか？
        if k <= 0:
            break

print(count)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from bisect import bisect_left

def sieve(n):
    srn = int(n ** 0.5)
    f = [False] * (srn + 1)
    res = []
    for i in range(2, srn+1):
        if f[i]:
            continue
        res.append(i)
        for j in range(2*i, srn+1, i):
            f[j] = True
    return res

def trial_division(n):
    res = dict()
    pn = sieve(n)
    for i in pn:
        while n % i == 0:
            res[i] = res.get(i, 0) + 1
            n //= i
    if n > 1:
        res[n] = 1
    return res

N = int(input())
pf = trial_division(N)
res = [i for i in range(10)]
for i in range(1, 10):
    res[i] = res[i-1] + i
ans = 0
for i in pf.values():
    idx = bisect_left(res, i)
    if i < res[idx]:
        idx -= 1
    ans += idx
print(ans)

Submission status: Accepted

Solution code:
# ABC169 D Div Game

n = int(input())

def factorization(n):
    arr = []
    if n == 1:
        return 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_list = factorization(n)
cnt = 0
for i in range(len(f_list)):
    _tmp = f_list[i][1]
    j = 1
    while _tmp >= 0:
        _tmp -= j
        j += 1
        cnt += 1
    cnt -= 1

print(cnt)

Submission status: Accepted

Solution code:
import sys

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

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

ans = 0
for f in fs:
  for e in range(1, f[1] + 1):
    z = f[0] ** e
    if N % z == 0:
      N //= z
      ans += 1

print(ans)