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):
    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)
if(n==1):
    print(0)
    exit()
ans = 0
for i in arr:
    for j in range(1,1000):
        if(i[1]+1<=j*(j+1)//2):
            ans += j-1
            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

import sys
N = int(input())
if N == 1:
    print(0)
    sys.exit()
A = factorization(N)
ans = 0
for i in range(len(A)):
    for j in range(1,A[i][1]+1):
        if N % A[i][0]**j == 0:
            ans += 1
            N //= A[i][0]**j
        else:
            break

print(ans)

Submission status: Accepted

Solution code:

import numpy as np


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

N = int(input())

# A,B = list(map(float, input().split()))

primes = prime_factorize(N)

prime2num = {}
for prime in primes:
    if prime in prime2num:
        prime2num[prime] += 1
    else:
        prime2num[prime] = 1

ans = 0
for prime, num in prime2num.items():
    i = 1
    c = 0
    while True:
        c += i
        if c > num:
            break
        i += 1
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
import math
l = []
n = int(input())
for i in range(2,int(math.sqrt(n))+1):
  flg = 0
  while n % i == 0:
    if flg == 0:
      l.append(1)
      flg = 1
    else:
      l[-1] += 1
    n = n//i

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

ans = 0
for i in range(len(l)):
  c = 1
  while l[i] - c >= 0:
    l[i] -= c
    c += 1
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
def primeFactorize(n):
    fac = []
    if n < 2: return fac
    while n%2 == 0:
        n //= 2
        fac.append(2)
    for i in range(3,int(n**0.5)+1,2):
        while n%i == 0:
            n //= i
            fac.append(i)
    if n != 1: fac.append(n)
    return fac

n = int(input())
s = set()
ans = 0
x = 1
p = -1
for f in primeFactorize(n):
    if p != f: x = 1
    x *= f
    p = f
    if x not in s:
        ans += 1
        s.add(x)
        x = 1
print(ans)
# print(primeFactorize(n))

Submission status: Accepted

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

N = int(input())
n_root = prime_factorize(N)
n_set = list(set(n_root))

ans = 0
for num in n_set:
    item = n_root.count(num)
    i = 1
    while item >= i:
        item -= i
        ans += 1
        i += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from functools import lru_cache
from bisect import bisect_right as bir
from collections import Counter
N = int(input())


def prime(n):
    ret = []
    while n % 2 == 0:
        ret.append(2)
        n //= 2

    f = 3
    while f*f <= n:
        if n % f == 0:
            ret.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        ret.append(n)
    return ret


D = Counter(prime(N))

comb = []
m = 0
for i in range(1, 10000):
    m += i
    comb.append(m)


ans = 0
for k, v in D.items():
    ans += bir(comb, v)

print(ans)

Submission status: Accepted

Solution code:
import itertools
import copy
from collections import deque
import heapq
n = int(input())
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

#エラトステネスの篩
def factory(n):
    num = int(n**0.5)+1
    prime = primes(num)
    disassembly = {}
    for i in prime:
        if n < i:
            return(disassembly)
            break
        count = 0
        while n % i == 0:
            n = n // i
            count += 1
        if not count == 0:
            disassembly[i] = count
    if n != 1:
        disassembly[n] = 1
    if disassembly == {}:
        disassembly[n] = 1
    return(disassembly)
ans = factory(n)
ans_list = []
for i in ans:
    for j in range(1,ans[i]+1):
        ans_list.append(i**j)
ans_list.sort()
answer = 0
for i in ans_list:
    if n%i == 0:
        answer += 1
        n = n//i
print(answer)

Submission status: Accepted

Solution code:
n = int(input())

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

list_n = prime_factorize(n)
dic = {}
for i in list_n:
    if i in dic:
        dic[i]+=1
    else:
        dic[i]=1
ans = 0
for i in dic.values():
    count=0
    while True:
        count+=1
        if i>=count:
            i-=count
        else:
            ans+=count-1
            break
print(ans)

Submission status: Accepted

Solution code:
def resolve():
    from collections import defaultdict
    import bisect
    def factorization(n):
        dic = defaultdict(int)
        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
                dic[i] = cnt

        if temp != 1:
            dic[temp] = 1
        if not dic:
            dic[n] = 1

        return dic
    n = int(input())
    a = factorization(n)
    total = []
    sums = 0
    for i in range(1,100):
        sums += i
        total.append(sums)
    ans = 0
    for i in a.keys():
        test = a[i]
        ans += bisect.bisect_right(total, test)
    if n == 1:
        print(0)
    else:
        print(ans)
resolve()

Submission status: Accepted

Solution code:
def 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 ra(a):
    ll,l=[],1
    for i in range(len(a)-1):
        if a[i]==a[i+1]:
            l+=1
        else:
            ll.append(l)
            l=1
    ll.append(l)
    return ll

import bisect
n=int(input())
if n==1:
    print(0)
    exit()
a=ra(factorize(n))
b=0
c=[-1]
for i in range(100):
    c.append(i+c[-1])
c.pop(0)
for i in a:
    b+=bisect.bisect_left(c,i)-1
print(b)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
from fractions import gcd
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

from itertools import permutations
from math import factorial, hypot

#############
# Main Code #
#############

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

def factime(ny):
    cnt = 1
    sum = 0
    while True:
        if sum + cnt > ny:
            break
        sum += cnt
        cnt += 1
    return cnt - 1

def prime_factorize(n):
    divisors = []
    # 27(2 * 2 * 7)の7を出すためにtemp使う
    temp = n
    for i in range(2, int(math.sqrt(n)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                # 素因数を見つけるたびにtempを割っていく
                temp //= i
            divisors.append([i, cnt])
    if temp != 1:
        divisors.append([temp, 1])
    if divisors == []:
        divisors.append([n, 1])

    return divisors

ans = 0
for i in prime_factorize(N):
    ans += factime(i[1])
print(ans)

Submission status: Accepted

Solution code:
import collections

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

n=int(input())
f=prime_factorize(n)
c = collections.Counter(f)
count=0
res={}
for i in range(len(f)):
    num=c[f[i]]#素数f[i]の個数
    for j in range(1,num+1):
        if f[i]**j not in res:
            res[f[i]**j]=1
            count+=1
            c[f[i]]-=j
            break
print(count)

Submission status: Accepted

Solution code:
N = int(input())
from collections import Counter
from itertools import accumulate
from bisect import bisect_right
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
cum_lis = list(accumulate([i for i in range(1000)]))
c = Counter(prime_factorize(N))
ans = 0
for num in c.values():
    ans += bisect_right(cum_lis, num)-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())

dat = factorization(n)
#print(dat)

buf = []

for a,b in dat:
    for j in range(b):
        buf.append(a)
dat.sort(key=lambda x: x[0])

used = dict()
cur = 1
res = 1

for a, b in dat:
    if a == 1:
        continue
    cur = 1
    for i in range(b):
        cur *= a
        if cur not in used:
            used[cur] = True
            res += 1
            cur = 1

print(len(used))

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import accumulate
from bisect import bisect_left
N=int(input())
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
A=prime_factorize(N)
a=list(range(1,11))
b=list(accumulate(a))
ans=0
for i,value in Counter(A).items():
    if value in b:
        ans+=b.index(value)+1
    else:
        ans+=bisect_left(b,value)
print(ans)

Submission status: Accepted

Solution code:
from math import sqrt

N = int(input())

rn = int(sqrt(N))
sieve = [0] * (rn + 1)
sieve[0] = -1
sieve[1] = -1
t = [0] * (rn + 1)
for i in range(2, rn + 1):
    if sieve[i] != 0:
        continue
    sieve[i] = i
    j = i
    while j < rn + 1:
        t[j] = 1
        j *= i
    for j in range(i * i, rn + 1, i):
        if sieve[j] == 0:
            sieve[j] = i

result = 0
last = -1
for i in range(2, rn + 1):
    if t[i] == 0:
        continue
    if N % i == 0:
        result += 1
        N //= i
        last = i
if N != 1 and N > rn:
    result += 1
print(result)

Submission status: Accepted

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


a=factorization(n)
#print(a)

def makearray(l):
    arr=[]
    for i in range(len(l)):
        for j in range(1,l[i][1]+1):
            arr.append(l[i][0]**j)
    arr.sort()
    return arr

b=makearray(a)
#print(b)
cnt=0

for i in b:
    if n%i==0:
        cnt+=1
        n//=i
        #print(i)
        #print('a')

if m==1:
    print(0)
else:
    print(cnt)

Submission status: Accepted

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

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

maxi = int(n**0.5)
sets = []
for i in range(2,maxi+1):
    aset = 0
    while(n%i == 0):
        aset += 1
        n /= i
    if(aset != 0):
        sets.append(aset)

count = 0
if(n > maxi):
    count += 1
for i in sets:
    start = 1
    while(i >= start):
        i -= start
        count += 1
        start += 1

print(count)

Submission status: Accepted

Solution code:
n = int(input())
if(n==1):
    print(0)
    exit()

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

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

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

    return arr

arr = factorization(n)

ans = 0
for i,j in arr:
    for k in range(1,100):
        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
  
if __name__=="__main__":
  n=int(input())
  if n==1:
    print(0)
  else:
    soinnsuu=factorization(n)
    ans = 0
    for sosuu in soinnsuu:
      x = 1
      while True:
        if sosuu[1]>=x:
          ans+=1
          sosuu[1]-=x
          x+=1
        else:
          break
    print(ans)

Submission status: Accepted

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

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

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

    return arr

def max(num):
    k = int(sqrt(2*num))
    for i in range(k):
        if (k-i)*(k-i+1)<=2*num:
            return k-i
    return

n = int(input())

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

li = factorization(n)

ans = 0
for i in li:
     ans +=max(i)
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())  
if n == 1:
  print(0)
  quit()
soinsu = factorization(n)
ans = 0
for i in range(len(soinsu)):
  a = 1
  b = 2
  temp = soinsu[i][1]
  num = 0
  while a <= temp:
    a += b
    b += 1
    num +=1
  ans+=num
  
print(ans)

Submission status: Accepted

Solution code:
import math
from collections import Counter
def pf(n):
    l = []
    while n % 2 == 0: 
        l.append(2)
        n = n / 2
    for i in range(3,int(math.sqrt(n))+1,2): 
        while n % i== 0: 
            l.append(i)
            n = n / i 
    if n > 2: 
        l.append(n)
    return l
def count(n):
    i = 1
    sum = 0
    while sum <= n:
        sum += i
        i+=1
    return (i-2)
n = int(input())
l = Counter(pf(n))
ans = 0
for x in l:
    ans += count(l[x])
print (ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import math

N = int(input())

d = defaultdict(int)
for i in range(2, int(math.sqrt(N)) + 1):
    while N % i == 0:
        d[i] += 1
        N //= i
if N > 1:
    d[N] = 1

ans = 0
for v in d.values():
    k = 1
    while k <= v:
        ans += 1
        v -= k
        k += 1
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
if N == 1:
  print(0)
  exit(0)
f = factorization(N)
#print(f)
ans = 0
amari_cnt = 0
for a,b in f:
  wk = b
  tempc = 1
  while wk  - tempc >= 0:
    wk -= tempc
    ans += 1
    tempc += 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


i = 0
n = int(input())
if n == 1:
    print(0)
else:
    arr = factorization(n)
    for a, b in arr:
        i += int((-1 + (1 + 8 * b)**(1 / 2)) // 2)
    print(i)

Submission status: Accepted

Solution code:
n = int(input())

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

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

l = factrize(n)
from collections import Counter
dic = Counter(l)

ans = 0
for i in dic.values():
    j = 0
    k = 1
    while i >= k:
        i -= k
        j += 1
        k += 1
    ans += j
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())

LIM = int(N ** .5) + 10
P = [True] * LIM
P[0] = P[1] = False
for i in range(4, LIM, 2): P[i] = False
i = 3
while i * i < LIM:
	if P[i]:
		j = i * i
		while j < LIM:
			P[j] = False
			j += 2 * i
	i += 2

pr = []
for i in range(2, LIM):
	if P[i]:
		pr.append(i)


if N == 1:
	print(0)
else:
	factors = Counter()
	for p in pr:
		if p > N: break
		while N % p == 0:
			factors[p] += 1
			N //= p

	if N > 1:
		factors[N] += 1

	r = 0
	for k, v in factors.items():

		i = 1
		while v >= i:
			r += 1
			v -= i
			i += 1
	print(r)

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])
    if (n==1):
        arr=[]
    return arr

n=int(input())
List=factorization(n) 
#print(List)
number=len(List)
ans=0
for i in range(number):
    k=1
    while (k<=List[i][1]):
        ans+=1
        List[i][1]-=k
        #print(List[i][1])
        k+=1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import collections
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

lis = prime_factorize(N)
c = collections.Counter(lis)
ans =0
for i in c.values():
    cnt = 0
    for j in range(1,i+1):
        cnt += j
        if cnt <= i:
            ans +=1
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import 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


n = int(readline())
memo = prime_decomposition(n)
cnt = 0
for v in Counter(memo).values():
    c = 1
    while v > 0:
        if v >= c:
            cnt += 1
            v -= c
        else:
            break
        c += 1
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
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])
    # 上のループを通した後にtempが1じゃなかったら、だけど、nが素数以外にそんなケースある？
    if temp!=1:
        arr.append([temp, 1])
    
    # 素数だったときの処理
    if arr == []:
        arr.append([n,1])

    return arr
fact = factorization(n)
ans = 0
for base, times in fact:
    if base == 1:
        continue
    i = 1
    while True:
        times -= i
        if times >= 0:
            ans += 1
        else:
            break
        i += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

#nの約数列挙
def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    ass.sort()
    return ass #sortされていない

#[[素因数,数]]を出力
def fctr1(n): 
    f = []
    c = 0
    for i in range(2,int(n**0.5)+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

D = divisor(N)
ans = 0
for d in D:
    if d == 1:
        continue
    if N >= d and N%d == 0 and len(fctr1(d)) == 1:
        N //= d
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
from decimal import *

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)
else:
    arr = factorization(n)

    arr = np.array(arr)

    kazu = arr[:,1]
    sum = 0
    for i in range(1, 1000000):
        if len(kazu) ==0:
            break
        sum += len(kazu)
        kazu -= (i)
        tugi =[]
        for k in kazu:
            if k < 0:
                sum -=1
                pass
            elif k == 0:
                pass
            else:
                tugi.append(k)
        kazu = np.array(tugi)
    print(sum)

Submission status: Accepted

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

a=collections.Counter(prime_factorize(n)).values()
res=0
for count in a:
    i=1
    while count>=0:
        count-=i
        i+=1
        res+=1
    res-=1
print(res)

Submission status: Accepted

Solution code:
N=int(input())
def PrimeFactor(n):
    ret=[]
    for i in range(2,int(-(-n**0.5//1))+1):
        if i!=2 and i%2==0:
            continue
        cnt=0
        while n%i==0:
            cnt+=1
            n//=i
        if cnt!=0:
            ret.append([i,cnt])
    if n!=1:
        ret.append([n,1])
    return ret
L = PrimeFactor(N)
ans=0
for l in L:
    x = l[1]
    temp=1
    while x>=temp:
        ans+=1
        x-=temp
        temp+=1
print(ans)

Submission status: Accepted

Solution code:
import sys

# 実行環境(0:vscode, 1:atcoder)
MODE = 1

# 入力の次元
DIMENSION = 0

# int型に変換
INT_TYPE = 1

if not (MODE):
    with open("input.txt", "r") as f:
        s = f.read()
else:
    s = sys.stdin.read()

if DIMENSION == 0:
    if INT_TYPE == 1:
        s = int(s)
elif DIMENSION == 1:
    if INT_TYPE == 0:
        s = s.split()
    elif INT_TYPE == 1:
        s = [int(x) for x in s.split()]
elif DIMENSION == 2:
    if INT_TYPE == 0:
        s = [x.split() for x in s.splitlines()]
    elif INT_TYPE == 1:
        s = [[int(y) for y in x.split()] for x in s.splitlines()]

if s == 1:
    print(0)
else:

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

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

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

        return arr

    F = factorization(s)

    cnt = 0
    for i in range(len(F)):
        num = 1
        while 1:
            F[i][1] -= num
            if F[i][1] < 0:
                break
            else:
                num += 1
                cnt += 1
    print(cnt)

Submission status: Accepted

Solution code:
n=int(input())

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


def factorization(n):
    p=2
    fcr=[]
    while p*p<=n:
        while n%p==0:
            fcr.append(p)
            n//=p
        p+=1
    if n>1:
        fcr.append(n)
    return fcr


l=divisore(n)[1:]

ans=0
for i in l:
  t_l=factorization(i)
  if len(set(t_l))!=1:
    continue


  if n%i==0:
    ans+=1
    n//=i

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
def soinsu(n, lists):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return soinsu(n // i, lists + [i])
    return lists + [n]
    
    
N = int(input())
if N == 1:
    print(0)
    exit()

a = soinsu(N, [])
ans = 0
    
tmp = Counter(a)

for i in tmp.values():
    s = 1
    counts = 1
    while True:
        counts += 1
        if i >= s:
            ans += 1
            s += counts
        else:
            break

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter


def pf(n):
    primes = Counter()
    c = 2
    while n // c > 0:
        if c**2 > n:
            primes[n] += 1
            break
        while n % c == 0:
            primes[c] += 1
            n //= c
        c += 1
    return primes


def count(t):
    n = 0
    ret = 0
    while True:
        if n * (n + 1) // 2 <= t < (n + 1) * (n + 2) // 2:
            ret = n
            break
        n += 1
    return ret


def main():
    N = int(input())
    primes = pf(N)
    print(sum(list(map(count, primes.values()))))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right

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)
    sys.exit()

L = factorization(N)
A = [i for i in range(1,101)]
for i in range(99):
    A[i+1] += A[i]

ans = 0
for _, l in L:
    ans += bisect_right(A,l)
print(ans)

Submission status: Accepted

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

c = collections.Counter(prime_factorize(N))

cnt = 0
for i in c.values():
    a = i
    b = 1
    while a - b >= 0:
        cnt += 1
        a -= b
        b += 1

print(cnt)

Submission status: Accepted

Solution code:
import sys
from math import ceil, floor, gcd, sqrt
from collections import defaultdict as dd, deque, Counter as C
mod = pow(10, 9) + 7
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


n = int(data())
dp = dd(int)
i = 2
while i * i <= n:
    while n % i == 0:
        dp[i] += 1
        n //= i
    i += 1
if n > 1:
    dp[n] = 1
answer = 0
for i in dp.keys():
    temp = floor((-1 + sqrt(8 * dp[i] + 1)) / 2)
    answer += temp
out(answer)