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:
## necessary imports
# import sys
# input = sys.stdin.readline
# from math import ceil, floor;

# swap_array function
def swaparr(arr, a,b):
    temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp

## gcd function
def gcd(a,b):
    if a == 0:
        return b
    return gcd(b%a, a)

## nCr function efficient using Binomial Cofficient
def nCr(n, k): 
    if(k > n - k): 
        k = n - k 
    res = 1
    for i in range(k): 
        res = res * (n - i) 
        res = res / (i + 1) 
    return int(res) 

## upper bound function code -- such that e in a[:i] e < x;
def upper_bound(a, x, lo=0):
    hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x:
            lo = mid+1
        else:
            hi = mid
    return lo

## prime factorization
def primefs(n):
    ## if n == 1    ## calculating primes
    primes = {}
    while(n%2 == 0):
        primes[2] = primes.get(2, 0) + 1
        n = n//2
    for i in range(3, int(n**0.5)+2, 2):
        while(n%i == 0):
            primes[i] = primes.get(i, 0) + 1
            n = n//i
    if n > 2:
        primes[n] = primes.get(n, 0) + 1
    ## prime factoriazation of n is stored in dictionary
    ## primes and can be accesed. O(sqrt n)
    return primes

## MODULAR EXPONENTIATION FUNCTION
def power(x, y, p): 
    res = 1
    x = x % p  
    if (x == 0) : 
        return 0
    while (y > 0) : 
        if ((y & 1) == 1) : 
            res = (res * x) % p 
        y = y >> 1      
        x = (x * x) % p 
    return res 

## DISJOINT SET UNINON FUNCTIONS
def swap(a,b):
    temp = a
    a = b
    b = temp
    return a,b

# find function with path compression included (recursive)
# def find(x, link):
#     if link[x] == x:
#         return x
#     link[x] = find(link[x], link);
#     return link[x];

# find function with path compression (ITERATIVE)
def find(x, link):
    p = x;
    while( p != link[p]):
        p = link[p];
    
    while( x != p):
        nex = link[x];
        link[x] = p;
        x = nex;
    return p;


# the union function which makes union(x,y)
# of two nodes x and y
def union(x, y, link, size):
    x = find(x, link)
    y = find(y, link)
    if size[x] < size[y]:
        x,y = swap(x,y)
    if x != y:
        size[x] += size[y]
        link[y] = x

## returns an array of boolean if primes or not USING SIEVE OF ERATOSTHANES
def sieve(n): 
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
        if (prime[p] == True): 
            for i in range(p * p, n+1, p):
                prime[i] = False
        p += 1
    return prime

#### PRIME FACTORIZATION IN O(log n) using Sieve ####
MAXN = int(1e6 + 5)
def spf_sieve():
    spf[1] = 1;
    for i in range(2, MAXN):
        spf[i] = i;
    for i in range(4, MAXN, 2):
        spf[i] = 2;
    for i in range(3, ceil(MAXN ** 0.5), 2):
        if spf[i] == i:
            for j in range(i*i, MAXN, i):
                if spf[j] == j:
                    spf[j] = i;
    ## function for storing smallest prime factors (spf) in the array

################## un-comment below 2 lines when using factorization #################
# spf = [0 for i in range(MAXN)]
# spf_sieve() 
def factoriazation(x):
    ret = {};
    while x != 1:
        ret[spf[x]] = ret.get(spf[x], 0) + 1;
        x = x//spf[x]
    return ret
    ## this function is useful for multiple queries only, o/w use
    ## primefs function above. complexity O(log n)

## taking integer array input
def int_array():
    return list(map(int, input().strip().split()))
## taking string array input
def str_array():
    return input().strip().split();

#defining a couple constants
MOD = int(1e9)+7;
CMOD = 998244353;
INF = float('inf'); NINF = -float('inf');

################### ---------------- TEMPLATE ENDS HERE ---------------- ###################

n = int(input()); prs = primefs(n);
ans = 0;
for i in prs:
    k = prs[i];
    ts = (-1 + (1 + 8*k)**0.5)//2;
    ans += ts;
print(int(ans));

Submission status: Accepted

Solution code:
import math
def findFactors(n):
    now=n
    f=[]
    while now%2==0:
        now//=2
        f.append(2)
    p=3
    while p<=math.sqrt(n):
        while now%p==0:
            now//=p
            f.append(p)
        p+=2
        if now==1:
            break
    if now>math.sqrt(n):
        f.append(now)
    return f

C=[0]
for i in range(1,100):
    C.append(C[-1]+i)
    
n=int(input())
F=findFactors(n)

ans=0
now=0
cnt=0
for f in F:
    if now!=f:
        for c in range(1,90):
            if C[c]>cnt:
                break
        ans+=c-1
        now=f
        cnt=1
    else:
        cnt+=1
for c in range(1,100):
    if C[c]>cnt:
        break
ans+=c-1       
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
fac = {}
for i in range(2,10**6):
  if n % i == 0:
    fac[i] = 0
    while n % i == 0:
      fac[i] += 1
      n //= i
if n != 1:
  fac[n] = 1
#print(fac)
jud = [1]
for i in range(10**6):
  jud.append(jud[-1]+i+2)
#print(jud)
ans = 0
for k in fac:
  num = fac[k]
  for i in range(10**6):
    if num >= jud[i]:
      ans += 1
    else:
      break
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

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 g(n):
    ret = 0
    for i in range(1, 100):
        n -= i
        if n < 0:
            break
        ret += 1
    return ret

MOD = 10 ** 9 + 7
INF = 10 ** 18

N = int(input())

if N == 1:
    print(0)
else:
    f = factorization(N)
    f.sort(key = lambda x: -x[1])
    len_f = len(f)

    answer = 0
    for i in range(len_f):
        answer += g(f[i][1])
    print(answer)

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])
    return arr
l=factorization(n)
ans=0
for p,i in l:
  cnt=1
  while i>=cnt:
    ans+=1
    i-=cnt
    cnt+=1
print(ans)

Submission status: Accepted

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
data = [0] * (10**5)
for i in range(1,10**5):
  data[i] = data[i-1] + i

def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        count=0
        while n % i==0:
            count+=1
            n = n//i
        if count!=0:
            ass.append((i,count))
    if n != 1:
        ass.append((n,1))
    return ass
ass = prime_factor(n)
for num,count in ass:
  ans += bisect.bisect_right(data,count)-1
  # print(bisect.bisect_right(data,count),count)
print(ans)
# print(data[:10])

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

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

#篩
num = 10 ** 6 + 1 #適当に値を入れる
L = [1 for i in range(num)]; L[0] = 0; L[1] = 0
plist = []
for i in range(num):
	if L[i] == 1:
		plist.append(i); c = 2
		while i * c <= num - 1:
			L[i * c] = 0; c += 1

def prime_factorization(N):
	D = defaultdict(int)
	for i in plist:
		while N % i == 0:
			D[i] += 1; N = int(N // i)

	if N != 1:
		D[N] += 1

	return D


#処理内容
def main():
	N = int(input())
	fac = prime_factorization(N)
	ans = 0
	# print(fac)
	for i in fac:
		for j in range(1, 100):
			if fac[i] < int((j * (j + 1) // 2)):
				ans += j - 1
				break

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

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

n = int(input())
dic = prime_factorize(n)
ans = 0
for value in dic.values():
    left = 1 # 可能
    right = value # 不可能
    while left + 1 < right:
        mid = (left+right)//2
        if mid * (mid+1) / 2 <= value:
            left = mid
        else:
            right = mid
    ans += left

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
if n == 1:
    print(0)
    exit()
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f**2 <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
b = []
d = prime_factorize(n)
c = len(d)
count = 1
for i in range(1,c):
    if d[i] != d[i-1]:
        b.append(count)
        count = 1
    else:
        count+=1
b.append(count)
ans = 0
for i in b:
    j = 1
    count2 = 0
    while count2 <= i:
        count2 += j
        j += 1
    ans += (j - 2)
print(ans)

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

# print(factorization(N))

count = 0

for i in factorization(N):

    # print(i, count)
    if i[0] != 1:
        minus = 1
        while i[1] > 0:
            i[1] -= minus
            if i[1] < 0:
                break
            minus += 1
            count += 1
    # print(i, count)
print(count)

Submission status: Accepted

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

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

if N == 1:
    print(0)
else:
    ans = 0
    for i,j in factorize(N):
        for k in range(1,10**9):
            j -= k
            if j < 0:
                break
            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
p = [1, 3, 6, 10, 15, 21, 28, 36]
n = int(input())
sss  = factorization(n)
ans = 0
if(n == 1):
    print(0)
else:
    for i in sss:
        s = 7
        while(i[1] < p[s]):
            s -= 1
        ans += s+1
    print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    N = int(input())
    ans = defaultdict(int)
    while N % 2 == 0:
        ans[2] += 1
        N //= 2
    f = 3
    while f * f <= N:
        if N % f == 0:
            ans[f] += 1
            N //= f
        else:
            f += 2
    if N != 1:
        ans[N] += 1
    
    Ans = 0
    for v in ans.values():
        x = 1
        while x * (x+1) // 2 <= v:
            x += 1
        Ans += x-1
    print(Ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def factorization(n):
    factors = []

    if n < 2:
        return n

    while n % 2 == 0:
        factors.append(2)
        n //= 2

    for i in range(3, int(n ** 0.5) + 5, 2):
        while n % i == 0:
            factors.append(i)
            n //= i

    if n != 1:
        factors.append(n)

    return factors


def main():
    from collections import Counter

    n = int(input())

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

    factors = Counter(factorization(n))

    ans = 0
    i = 0
    flag = True

    while flag:
        flag = False
        i += 1
        for key in factors.keys():
            if factors[key] >= i:
                ans += 1
                factors[key] -= i
                flag = True

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

def primeFactors(n):
    res = []
    while n%2==0:
        res.append(2)
        n //= 2
    x = 3
    while n>1 and n>=x*x:
        while n%x==0:
            res.append(x)
            n //= x
        x += 2
    if n>1:
        res.append(n)
    return res

n = int(input())
pl = primeFactors(n)

res = 0
cd = Counter(pl)
for k in cd:
    c = cd[k]
    i = 1
    while c-i>=0:
        c -= i
        res += 1
        i += 1
print(res)

Submission status: Accepted

Solution code:
n=int(input())
from math import sqrt as S 
pf=[]
for i in range(2,int(S(n))+1):
    if n%i==0:
        c=0 
        while n%i==0:
            n//=i 
            c+=1 
        pf.append([i,c])
if n>1:
    pf.append([n,1])
cnt=0 
def search(x):
    lo=0
    hi=10**9 
    ans=0 
    while lo<=hi:
        mi=(lo+hi)//2 
        if mi*(mi+1)//2<=x:
            ans=mi 
            lo=mi+1 
        else:
            hi=mi-1 
    return ans 
for x in range(len(pf)):
    a=pf[x][0]
    b=pf[x][1]
    cnt+=search(b)
print(cnt)

Submission status: Accepted

Solution code:
n=int(input()) 
s=[]
for i in range(2,int(n**0.5)+1):
    if n%i==0:
        p=0
        while(n%i==0):
            p+=1
            n//=i
        s.append(p)
if n>1:
    s.append(1)
#1print(s)
ans=0
for i in s:
    r=1
    while(i>0):
        if i<r:
            break
        i-=r 
        r+=1
        ans+=1 
print(ans)

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    ans = 0
    for i in range(2, int(N ** 0.5) + 1):
        c = 0
        while N % i == 0:
            c += 1
            N //= i
        i = 0
        while c > i:
            ans += 1
            i += 1
            c -= i
    if N > 1:
        ans += 1
    print(ans)

if __name__ == '__main__':
    main()

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

fac = factorization(N)
ans = 0

for k, v in fac:
    cnt = 1
    if k != 1:
        while True:
            v -= cnt
            if v < 0:
                break
            ans += 1
            cnt += 1

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

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

N = int(input())

# [[素因数,数]]を出力
def fctr1(n):
    f = []
    c = 0
    r = int(n ** 0.5)
    for i in range(2, r + 2):
        while n % i == 0:
            c += 1
            n = n // i
        if c != 0:
            f.append([i, c])
            c = 0
    if n != 1:
        f.append([n, 1])
    return f


f = fctr1(N)

ans = 0
for n, v in f:
    c = 1
    while 0 < v:
        v -= c
        c += 1

        if v >= 0:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
sys.setrecursionlimit(10**9)
from collections import deque,defaultdict
import heapq
from itertools import combinations
import bisect


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

n=int(input())
if n==1:
    print(0)
    exit()
p=fact(n)
ans=0
for a,b in p:
    t=1
    g=b
    while g>=t:
        g-=t
        t+=1
    ans+=t-1
print(ans)

Submission status: Accepted

Solution code:
import bisect
import heapq
import math
import random
import sys
import collections
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub, or_

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())

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

def read_float():
    return float(input())

def read_float_n():
    return list(map(float, input().split()))

def read_str():
    return input().strip()

def read_str_n():
    return list(map(str, input().split()))

def error_print(*args):
    print(*args, file=sys.stderr)

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 = read_int()
    f = factorization(n)
    count = 0
    for x in f:
        if x[0] == 1:
            continue
        lc = x[1]
        for i in range(1,INF):
            if i <= lc:
                lc = lc - i
                count+=1
            else:
                break
    print(count)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
total = 0
for i in range(2, int(n**(1/2)+2)):
    acc = 0
    while n % i == 0:
        acc += 1
        n //= i
    total += (-1 + (1 + 8 * acc)**(1/2)) // 2;
if n != 1:
    total += 1
print(int(total))

Submission status: Accepted

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

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

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

    return arr


N = int(input())

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

prime = factorization(N)
count = 0
for i in range(len(prime)):
    num, e = prime[i]
    tmp = 1
    while True:
        e -= tmp
        if e >= 0:
            count += 1
        else:
            break
        tmp += 1
        
print(count)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def integer_factorization(n):
    prime_count = collections.Counter()
    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n //= i
            prime_count[i] += 1
    if n > 1:
        prime_count[n] += 1
    return prime_count

def main():
    n = I()
    d = integer_factorization(n)
    cnt = 0
    for key, val in d.items():
        cur = 1
        used = set()
        while val > 0:
            if cur > val:
                break
            val -= cur
            cnt += 1
            used.add(cur)
            cur += 1
    print(cnt)
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
N=int(input())
A=factorization(N)
ans=0
if N==1:
 print(0)
else:
 for i in range(len(A)):
  ans+=int((2*A[i][1]+0.25)**(0.5)-0.5)
 print(ans)

Submission status: Accepted

Solution code:
def primes(n):
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1, int(n**0.5)//3+1):
        if sieve[i]:
            k = 3*i+1|1
            sieve[k*k//3::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2, 3] + [3*i+1|1 for i in range(1, n//3-correction) if sieve[i]]
from collections import defaultdict

n=int(input())
primelist=primes(int(n**0.5+1))+[n+1]
factors=defaultdict(lambda :0)
for prime in primelist:
    if prime>n:
        factors[n]+=1
        break
    while n%prime==0:
        n=n//prime
        factors[prime]+=1
factors[n]=1

ans=0
for i in factors:
    if i!=1:
        f=factors[i]
        for j in range(1,50):
            f-=j
            if f<0:
                break
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
import math
def Sieve_of_Eratosthenes(N):
    if N<2:
        prime = [False for i in range(N+1)]
        return prime
 
    prime = [True for i in range(N+1)]
    prime[0] = False
    prime[1] = False
 
    for i in range(2, int(N**0.5)+1):
        if prime[i]:
            for j in range(i*2, N+1, i):
                prime[j] = False
 
    return prime

n=int(input())
prime=Sieve_of_Eratosthenes(int(n**0.5)+100)
ans=0
for p in range(len(prime)):
    if prime[p]==True:
        tp=p
        while n%tp==0:
            ans+=1
            n//=tp
            tp*=p
        
        while n%p==0:
            n//=p
if n!=1: ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,copy
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

#素因数分解
def prime_factorize(n):
    if n == 1:
        return [1]
    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 = inp()
if n == 1:
    print(0)
    quit()
c = Counter(prime_factorize(n))
res = 0
for key in list(c):
    va = c[key]
    cnt = 0
    for i in range(1,100000):
        cnt += i
        if va < cnt:
            res += i-1
            break
print(res)

Submission status: Accepted

Solution code:
import sys
import math

sys.setrecursionlimit(10**7)

n = int(input())
l = []
if n%2 == 0:
    l.append(0)
    while n%2 == 0:
        l[0] += 1
        n /= 2

i = 3
while i*i <= n:
    if n%i == 0:
        l.append(0)
        while n%i == 0:
            l[-1] += 1
            n /= i
    i += 2
if n != 1:
    l.append(1)

ans = 0
for i in range(len(l)):
    j = 1
    while True:
        l[i] -= j
        j += 1
        if l[i] < 0:
            break
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter, defaultdict, deque
import math
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def eratosthenes(n):
    p = []
    t = [True] * n

    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i]:
            p.append(i)
            for j in range(2*i, n, i):
                t[j] = False

    for j in range(i+1, n):
        if t[j]:
            p.append(j)

    return p

P = eratosthenes(10**6+1)


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo

def f(n):
    return (n**2 + n) // 2

@mt
def slv(N):
    if N == 1:
        return 0

    d = Counter()
    for p in P:
        n = 0
        while N % p == 0:
            n += 1
            N //= p
        if n != 0:
            d[p] = n
        if N == 1:
            break
    if N != 1:
        d[N] = 1
    ans = 0
    for p, n in d.items():
        i = Bisect(f).bisect_left(n+1, 0, 10**18)-1
        ans += i

    return ans


def main():
    N = read_int()
    print(slv(N))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

tri = [1]
for i in range(2,30):
    tri.append(tri[-1]+i)
n = int(input())
a = factorize(n)
ans = 0
for num,v in a:
    for k,i in enumerate(tri):
        if i > v:
            ans += k
            break
print(ans)

Submission status: Accepted

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

N=int(input())
if N==1:
    print(0)
    exit()
arr=factorization(N)
ans=0
for i in range(len(arr)):
    if arr[i][0]==1:
        continue
    cnt=1
    while arr[i][1]>0:
        if arr[i][1]>=cnt:
            arr[i][1]-=cnt
            ans+=1
            cnt+=1
        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

n=int(input())
a=factorization(n)
b=[ele[1] for ele in a]

ans=0

for num in b:
    now=num
    for cnt in range(1,101):
        if cnt<=now:
            now-=cnt
            ans+=1
        else:
            break

if n==1:
    print(0)
else:
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")

from collections import Counter


def factorial(n):
    prime_count = Counter()

    for i in range(2, int(n**0.5) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[int(n)] += 1

    return prime_count


def main():
    N = int(input())
    pc = factorial(N)                # O(N**0.5)

    ans = 0
    for k, v in pc.items():
        count = 0
        for i in range(1, v+5):
            v -= i
            if v < 0:
                break
            count += 1
        # print(k, v, count)
        ans += count
    print(ans)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
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())
ans=0
if n>1:
    array=factorization(n)
    # print(array)
    ans=0
    for a in array:
        ans+=(-1+math.sqrt(1+8*a[1]))//2
        # print(ans)

print(int(ans))