Problem:


Score : 400 points

Problem Statement

Given is a positive integer N. Consider repeatedly applying the operation below on N:

First, choose a positive integer z satisfying all of the conditions below:

z can be represented as z=p^e, where p is a prime number and e is a positive integer;

z divides N;

z is different from all integers chosen in previous operations.

Then, replace N with N/z.

Find the maximum number of times the operation can be applied.

Constraints

All values in input are integers.

1 \leq N \leq 10^{12}

Input

Input is given from Standard Input in the following format:

N

Output

Print the maximum number of times the operation can be applied.

Sample Input 1

24

Sample Output 1

3

We can apply the operation three times by, for example, making the following choices:

Choose z=2 (=2^1). (Now we have N=12.)

Choose z=3 (=3^1). (Now we have N=4.)

Choose z=4 (=2^2). (Now we have N=1.)

Sample Input 2

1

Sample Output 2

0

We cannot apply the operation at all.

Sample Input 3

64

Sample Output 3

3

We can apply the operation three times by, for example, making the following choices:

Choose z=2 (=2^1). (Now we have N=32.)

Choose z=4 (=2^2). (Now we have N=8.)

Choose z=8 (=2^3). (Now we have N=1.)

Sample Input 4

1000000007

Sample Output 4

1

We can apply the operation once by, for example, making the following choice:

z=1000000007 (=1000000007^1). (Now we have N=1.)

Sample Input 5

997764507000

Sample Output 5

7



Sample input:
24


Sample output:
3

Submission status: Accepted

Solution code:
import math

def primeFactors(n): 
	  
	# Print the number of two's that divide n 
	d = {}
	while n % 2 == 0: 
	    # print 2, 
	    # x.add(2)
	    if(2 not in d):
	    	d[2] = 1
	    else:
	    	d[2]+=1
	    n = n / 2
	      
	# n must be odd at this point 
	# so a skip of 2 ( i = i + 2) can be used 
	for i in range(3,int(math.sqrt(n))+1,2): 
	      
	    # while i divides n , print i ad divide n 
	    while n % i== 0: 
	        # print i, 
	        # x.add(i)
	        if(i not in d):
	        	d[i] = 1
	        else:
	        	d[i]+=1
	        n = n / i 
	          
	# Condition if n is a prime 
	# number greater than 2 
	if n > 2: 
	    # print n 
	    # x.add(n)
	    if(n not in d):
	    	d[n] = 1
	    else:
	    	d[n]+=1
	return d

n = int(input())

d = primeFactors(n)
if(not d):
	print(0)
else:
	ans = 0
	for i in d:
		if(d[i] == 1):
			ans+=1
		else:
			ans += int((-1 + math.sqrt(1 + 8 * d[i])) // 2);

	print(ans)

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

cnt = 0 
for i in range(len(F)):
  m = 1
  while F[i][1] >= m*(m+1)/2:
    cnt += 1
    m += 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))+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

whole = factorization(n)

count = 0

if whole == [[1, 1]]:
  print(count)
  exit()

#print(whole)
for s in whole:
  #print(s)
  c = 0
  for i in range(1, s[1] + 1):
    shou = n / (int(s[0]) ** (i * (i + 1) / 2))
    seisuu = n // (int(s[0]) ** (i * (i + 1) / 2))
    if shou == seisuu:
      #print(shou, seisuu)
      c += 1
    else:
      break
  count += c

print(count)

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


def is_prime(n):
    for d in range(2, math.floor(math.sqrt(n)) + 1):
        if n % d == 0:
            return False
    return True


N = int(input())
if N == 1:
    print(0)
elif is_prime(N):
    print(1)
else:
    res = 0
    for _, count in factorization(N):
        if count <= 2:
            res += 1
        else:
            i = 1
            while count - i >= 0:
                count -= i
                i += 1
            res += (i - 1)
    print(res)

Submission status: Accepted

Solution code:
import collections

m = 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(m))
# index = list(c.keys())
number = list(c.values())
ans = 0
for i in number:
    step = 1
    key = 1
    while key <= i:
        ans += 1
        step += 1
        key += step

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

def pr(n):
    d = defaultdict(lambda:0)
    i = 2
    while (n > 1) and (i < int(n**0.5)+1):
        if n % i == 0:
            d[i] += 1
            n //= i
        else:
            i += 1
            
    if n > 1:
        d[n] += 1
    return d

def t(x):
    i = 1
    while x >= i:
        x -= i
        i += 1
    return i-1

n = int(input())
d = pr(n)
r = 0
for i in d.values():
    r += t(i)
print(r)

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())
c = collections.Counter(prime_factorize(N))
d = list(c.values())
ans = 0
for j in range(len(d)):
  for i in range(1,40):
    k = i*(i+1)/2
    if d[j] == k:
      ans += i
      break
    elif d[j] < k:
      ans += i-1
      break
    else:
      continue
print(ans)

Submission status: Accepted

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

def cc(n):
    ans = 0
    i = 1
    while True:
        n = n - i
        ans += 1
        i += 1
        if n < i:
            break
    return ans

s_list = prime_factorize(N)
c = collections.Counter(s_list)
values,counts = zip(*c.most_common())
j = 0
for i in range(len(counts)):
    counter += cc(counts[i])
print(counter)

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)
n = len(A)
sum = 0
if N ==1:
    print(0)
else:
    for i in range(n):
        d =A[i][1]
        for j in range(100):
            if j*(j+1) <= 2*d < (j+1)*(j+2):
                sum = sum + j
                break
    print(sum)

Submission status: Accepted

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

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

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

    return ans

N = int(input())
if N == 1:
    print(0)
    exit();


print(factorization(N))

Submission status: Accepted

Solution code:
a=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
ww=factorization(a)
ans=0
if a==1:
    ans=0
else:
    for j in range(len(ww)):
        if 2>=ww[j][1]>=1:
            ans+=1
        if 5>=ww[j][1]>=3:
            ans+=2
        if 9>=ww[j][1]>=6:
            ans+=3 
        if 14>=ww[j][1]>=10:
            ans+=4
        if 20>=ww[j][1]>=15:
            ans+=5
        if 27>=ww[j][1]>=21:
            ans+=6
        if 35>=ww[j][1]>=28:
            ans+=7
        if ww[j][1]>=36:
            ans+=8
print(ans)

Submission status: Accepted

Solution code:
N=int(input())

if N==1:
    print(0)
    exit()
# N > 1
l=[]
ans=0
for i in range(2,int(N**0.5)+1):
    cnt=0
    while N % i ==0:
        cnt+=1
        N //=i
    if cnt > 0:
        l.append( (i,cnt) )
        ans += int( (-1+(1+8*cnt)**0.5)/2 )
if N > 1:
    l.append((N,1))
    ans +=1

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

prime_list=prime_factorize(N)
prime_dict=collections.Counter(prime_list)
ans=0

for k,v in prime_dict.items():
    cnt=1
    if v <= 2:
        ans += 1
    else:
        while (cnt <= v):
            v = v - cnt
            cnt += 1
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import random

def primesbelow(N):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    #""" Input N>=6, Returns a list of primes, 2 <= p < N """
    correction = N % 6 > 1
    N = {0:N, 1:N-1, 2:N+4, 3:N+3, 4:N+2, 5:N+1}[N%6]
    sieve = [True] * (N // 3)
    sieve[0] = False
    for i in range(int(N ** .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 + 4*k - 2*k*(i%2)) // 3::2*k] = [False] * ((N // 6 - (k*k + 4*k - 2*k*(i%2))//6 - 1) // k + 1)
    return [2, 3] + [(3 * i + 1) | 1 for i in range(1, N//3 - correction) if sieve[i]]

smallprimeset = set(primesbelow(100000))
_smallprimeset = 100000
def isprime(n, precision=7):
    # http://en.wikipedia.org/wiki/Miller-Rabin_primality_test#Algorithm_and_running_time
    if n < 1:
        raise ValueError("Out of bounds, first argument must be > 0")
    elif n <= 3:
        return n >= 2
    elif n % 2 == 0:
        return False
    elif n < _smallprimeset:
        return n in smallprimeset


    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1

    for repeat in range(precision):
        a = random.randrange(2, n - 2)
        x = pow(a, d, n)

        if x == 1 or x == n - 1: continue

        for r in range(s - 1):
            x = pow(x, 2, n)
            if x == 1: return False
            if x == n - 1: break
        else: return False

    return True

# https://comeoncodeon.wordpress.com/2010/09/18/pollard-rho-brent-integer-factorization/
def pollard_brent(n):
    if n % 2 == 0: return 2
    if n % 3 == 0: return 3

    y, c, m = random.randint(1, n-1), random.randint(1, n-1), random.randint(1, n-1)
    g, r, q = 1, 1, 1
    while g == 1:
        x = y
        for i in range(r):
            y = (pow(y, 2, n) + c) % n

        k = 0
        while k < r and g==1:
            ys = y
            for i in range(min(m, r-k)):
                y = (pow(y, 2, n) + c) % n
                q = q * abs(x-y) % n
            g = gcd(q, n)
            k += m
        r *= 2
    if g == n:
        while True:
            ys = (pow(ys, 2, n) + c) % n
            g = gcd(abs(x - ys), n)
            if g > 1:
                break

    return g

smallprimes = primesbelow(1000) # might seem low, but 1000*1000 = 1000000, so this will fully factor every composite < 1000000
def primefactors(n, sort=False):
    factors = []

    for checker in smallprimes:
        while n % checker == 0:
            factors.append(checker)
            n //= checker
        if checker > n: break

    if n < 2: return factors

    while n > 1:
        if isprime(n):
            factors.append(n)
            break
        factor = pollard_brent(n) # trial division did not fully factor, switch to pollard-brent
        factors.extend(primefactors(factor)) # recurse to factor the not necessarily prime factor returned by pollard-brent
        n //= factor

    if sort: factors.sort()

    return factors

def factorization(n):
    factors = {}
    for p1 in primefactors(n):
        try:
            factors[p1] += 1
        except KeyError:
            factors[p1] = 1
    return factors

totients = {}
def totient(n):
    if n == 0: return 1

    try: return totients[n]
    except KeyError: pass

    tot = 1
    for p, exp in factorization(n).items():
        tot *= (p - 1)  *  p ** (exp - 1)

    totients[n] = tot
    return tot

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

def lcm(a, b):
    return abs((a // gcd(a, b)) * b)
l=[0, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 0, 0, 0, 0, 0]
N=int(input())
choice=0
x=0
ans=0
dic=factorization(N)

for key in dic.keys():
  ans+=l[dic[key]]
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

z = int(input())
dividers = factorization(z)

# zが1の場合
if (z == 1):
  print(0)
  sys.exit()
# そうでない場合
else:
  ans = 0
  for divider in dividers:
    i = 0
    while i*(i+1)/2 <= divider[1]:
      i += 1
    ans += i - 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

factors = []

rem = 1
while n%2 == 0:
    n //= 2
    rem *=2
    if not rem in factors:
        factors.append(rem)
        rem = 1

for f in range(3, int(n**0.5)+ 1, 2):
    rem = 1
    while n%f == 0:
        n //= f
        rem *= f
        if not rem in factors:
            factors.append(rem)
            rem = 1

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

print(len(factors))

Submission status: Accepted

Solution code:
import math
def D():
    N = int(input())
    if N == 1:
        print(0)
        return
    temp = N
    count = 0
    while temp % 2 == 0: 
       temp //= 2
       count += 1
    track = 1
    # print(count)
    while count-track >= 0:
        count -= track
        track += 1
    # print(temp, track-1)
    ans = track - 1
    for i in range(3,int(math.sqrt(temp))+1,2): 
        count = 0
        while temp % i== 0: 
            temp //= i
            count += 1
        track = 1
        while count-track >= 0:
            count -= track
            track += 1
        ans += track - 1
    if temp > 2:
        ans += 1
    print(ans)
D()

Submission status: Accepted

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

def prime_factorize( n ):
    a = {}
    while n % 2 == 0:
        try:
            a[ 2 ] += 1
        except KeyError:
            a[ 2 ] = 1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            try:
                a[ f ] += 1
            except KeyError:
                a[ f ] = 1
            n //= f
        else:
            f += 2
    if n != 1:
        try:
            a[ n ] += 1
        except KeyError:
            a[ n ] = 1
    return a

a = prime_factorize( n )
ans = 0
for p in a.keys():
    ans += int( ( -1 + math.sqrt( 1 + 8 * a[ p ] ) ) / 2 )

print( ans )

Submission status: Accepted

Solution code:
import math
from bisect import bisect


def primeFactors(n):
    ar = []
    for i in range(1, 101):
        ar.append(i * (i + 1) // 2)
    d = dict()
    while n % 2 == 0:
        if d.get(2) is None:
            d[2] = 1
        else:
            d[2] += 1
        n = n // 2
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        while n % i == 0:
            if d.get(i) is None:
                d[i] = 1
            else:
                d[i] += 1
            n = n // i
    if n > 2:
        d[n] = 1
    cnt = 0
    for i in d.values():
        if i == 1:
            cnt += 1
        else:
            b = bisect(ar, i)
            cnt += b
    return cnt


print(primeFactors(int(input())))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

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

# N: 素因数分解する数
#リストで返す
res = []
x = n

y = 2
while y*y <= x:
    while x % y == 0:
        res.append(y)
        x //= y
    y += 1
if x > 1:
    res.append(x)



dic=Counter(res)
ans=0
#print(dic)
for i in dic:
    p=dic[i]
    #print(p)
    chk=0
    cnt=0
    for q in range(1,24):
        if chk+q<=p:
            cnt+=1
            chk+=q
        
        
    ans+=cnt
    #print(i,cnt,chk)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np

input = sys.stdin.readline


def S():
    return input().rstrip()


def I():
    return int(input())


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


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 = I()
result = factorization(n)

a = np.arange(1, 10)
a = np.cumsum(a)

if n == 1:
    print("0")
    exit()
else:
    ans = 0
    for l in result:
        ans += len(a[a <= l[1]])

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from math import sqrt
input = stdin.readline
N = int(input())

s = [0] * (int(sqrt(N)) + 1)

ans = 0

for i in range(2, int(sqrt(N)) + 1):
    tmp = i

    while N % tmp == 0:
        N //= tmp
        s[tmp] += 1

for i in s:
    for j in range(10 ** 5):
        if (j * (j + 1)) // 2 > i:
            k = j
            break

    ans += k - 1

for i in range(2, int(sqrt(N)) + 1):
    if N % i == 0:
        print(ans)
        exit()

if N != 1:
    ans += 1


print(ans)

Submission status: Accepted

Solution code:

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


def q4():
    N = int(input())
    arr = prime_factorize(N)
    if not arr:
        print(0)
        return

    ans_count = 0
    count = 1

    min_val = min(arr)
    while arr:
        if arr.count(min_val) < count:
            arr = list(filter(lambda a: a != min_val, arr))
            count = 1
            if not arr:
                break
            min_val = min(arr)
            continue
        arr = arr[count:]
        ans_count += 1
        count += 1
    print(ans_count)


q4()

Submission status: Accepted

Solution code:
import collections

n = int(input())
# n = 840

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)
    
    a = collections.Counter(a)
    return dict(a)



dic = prime_factorize(n)
# print(dic)


list_keys = list(dic.keys())

cnt = 0
for key in list_keys:
    c = 1
    while True:
        dic[key] -= c
        c += 1
        cnt += 1
        if dic[key] < c:
            break

print(cnt)

Submission status: Accepted

Solution code:
def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


def prime_len(n):
    a = set()
    while n % 2 == 0:
        a.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.add(n)
    return len(a)


n = int(input())
c = 0
for z in make_divisors(n):
    if prime_len(z) == 1:
        tmp = n / z
        if tmp.is_integer():
            n = tmp
            c += 1
        else:
            continue

print(c)

Submission status: Accepted

Solution code:
import math
n = int(input())
n1 = n
if n == 1:
    print(0)
else:
    a = [0]*(int(math.sqrt(n)) + 1)
    a[1] = 1
    ans = 0
    for i in range(2, int(math.sqrt(n)) + 1):
        if a[i] == 0:
            for j in range(i+i, int(math.sqrt(n)) + 1, i):
                a[j] = 1
    for i in range(2, len(a)):
        if a[i] == 0:
            k = 1
            s = i
            while n % s == 0:
                # print(s)
                ans += 1
                n //= s
                s *= i
            while n % i == 0:
                n //= i
    # print(n)
    f = 1
    for j in range(2, int(math.sqrt(n)) + 2):
        if n % j == 0:
            f = 0
            break
    if f and n != 1:
        ans += f
    # print(n1 // i)

    if ans == 0:
        print(1)
    else:
        print(ans)
    # print(len('997764507000'))

Submission status: Accepted

Solution code:
N=int(input())
def factorize(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
a=factorize(N)

q={}
for i in range(len(a)):
  if a[i] in q:
    q[a[i]]+=1
  else:
    q[a[i]]=1
def k(n):
    B=[i*(i+1) for i in range(20)]
    s=0
    for j in range(20):
      if 2*n>=B[j]:
        s=j
      else:
        s=s
    return s
c=0
for key in q.keys():
  c+=k(q[key])
print(c)

Submission status: Accepted

Solution code:
n = int(input())

def isPrime(n):
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

def f(n):
    if n == 0:
        return 0
    i = 1
    while not(i * (i + 1) // 2 <= n and n < (i + 1) * (i + 2) // 2):
        i += 1
    return i

p = {}

answer = 0
if n % 2 == 0:
    c = 0
    while n % 2 == 0:
        n //= 2
        c += 1
    answer += f(c)

q = 3
while q * q <= n:
    c = 0
    while n % q == 0:
        n //= q
        c += 1
    answer += f(c)
    q += 2

if n > 1:
    answer += 1
print(answer)

Submission status: Accepted

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

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

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

    return arr


N = int(input())
fact = factorization(N)
ans = 0
for f in fact:
    if f[0] >= 2:
        remain = f[1]
        tmp = 1
        while True:
            remain -= tmp
            if remain >= 0:
                ans += 1
            else:
                break
            tmp += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())

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

ans = 0
n = 1
for i, v in Counter(prime_factorize(N)).items():
    # print(i, v)
    while True:
        # print("v", v)
        v -= n
        if v >= 0:
            ans += 1
            n += 1
        else:
            break
    n = 1
print(ans)

Submission status: Accepted

Solution code:
from math import sqrt
from sys import stdin, stdout

int_in = lambda: int(stdin.readline())
arr_in = lambda: [int(x) for x in stdin.readline().split()]
mat_in = lambda rows: [arr_in() for y in range(rows)]
str_in = lambda: stdin.readline().strip()
out = lambda o: stdout.write("{}\n".format(o))
arr_out = lambda o: out(" ".join(map(str, o)))
bool_out = lambda o: out("YES" if o else "NO")
tests = lambda: range(1, int_in() + 1)
case_out = lambda i, o: out("Case #{}: {}".format(i, o))


def prime_factors(n):
    i = 2
    result = []
    while i * i <= n:
        if n % i == 0:
            n //= i
            result.append(i)
        else:
            i += 1
    if n > 1:
        result.append(n)
    return result

def solve(n):
    primes = sorted(prime_factors(n))
    used = set()
    result = 0
    i = 0
    while n > 1 and i < len(primes):
        curr = primes[i]
        while curr in used:
            i += 1
            if i == len(primes):
                return result
            if primes[i - 1] != primes[i]:
                curr = primes[i]
            else:
                curr *= primes[i]
        n //= curr
        used.add(curr)
        result += 1
        i += 1
    return result

if __name__ == "__main__":
    n = int_in()
    out(solve(n))

Submission status: Accepted

Solution code:
def solve(n):
    l = []
    k = int(n**0.5)
    i = 2
    tmp = 0
    while i <= n and i <= k:
        if n % i == 0:
            n = n // i
            tmp += 1
        else:
            if tmp != 0:
                l.append(tmp)
                tmp = 0
            i += 1
    if n == 1:
        l.append(tmp)
    else:
        l.append(1)
    res = 0
    for z in l:
        i = 1
        z -= i
        while z >= 0:
            res += 1
            i += 1
            z -= i
    return res





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

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache


@lru_cache(maxsize=None)
def solve(n):
    ans = 0
    for i in range(1, 10*10):
        if n - i >= 0:
            ans += 1
            n -= i
        else:
            return(ans)


n = int(input())


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


pf = {}
m = n
for i in range(2, int(m**0.5)+1):
    while m % i == 0:
        pf[i] = pf.get(i, 0)+1
        m //= i
if m > 1:
    pf[m] = 1

ans = list(pf.values())
ans = sum([solve(x) for x in ans])

print(ans)

Submission status: Accepted

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

def prime(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
ans = prime(N)
c = collections.Counter(ans)
count = 0
for i in c.keys():
  if c[i] <= 2:
    count += 1
  elif c[i] <= 5:
    count += 2
  elif c[i] <= 9:
    count += 3
  elif c[i] <= 14:
    count += 4
  elif c[i] <= 20:
    count += 5
  elif c[i] <= 27:
    count += 6
  elif c[i] <= 35:
    count += 7
  elif c[i] <= 44:
    count += 8

print(count)

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

import collections

N = int(input())
A = collections.Counter(prime_factorize(N))

ans = 0
for a in A.values():
	b = 1
	c = 1
	while True:
		if b > a:
			break
		c+=1
		b = b + c
	ans+=c-1
print(ans)




#import math

#A,B = input().split()



#C = int(int(A) * float(B) * 100)


#print(C // 100)

#N = int(input())
#As = list(map(int,input().split()))

#sum = 1

#if any(b == 0 for b in As):
#	sum = 0
#else:
#	for a in As:
#		sum*=a
#		if sum > 1000000000000000000:
#			sum = -1
#			break
#print(sum)


#A,B=map(int,input().split())

#print(A*B)

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

def main():
    c = prime_factorize(N)
    if c == []:
        print(0)
        return
    else:
        coll = collections.Counter(c).values()
        ans = 0
        for i in coll:
            tmp = 0
            while i > 0:
                if(tmp < i):
                    ans += 1
                    tmp += 1
                    i -= tmp
                else:
                    break
        print(ans)
        return

if __name__ == "__main__":
    main()