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:
n = int(input())
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
c = collections.Counter(prime_factorize(n))

ans = 0
for i in c:
    tmp = c[i]
    num = 1
    while tmp >= 0:
        tmp -= num 
        if tmp >= 0:
            ans += 1
        num += 1
        
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n=int(input())
def f(n):
  num=int(np.sqrt(2*n))
  while True:
    if num*(num+1)//2 > n:
      return num-1
    num+=1
p=[]
p_tf=[1 for i in range(int(np.sqrt(n))+1)]
p_tf=np.array(p_tf)
for i in range(2,int(np.sqrt(n))+1):
  if p_tf[i] and n%i==0:
    p.append(i)
    p_tf[i::i]-=1
p2=p.copy()
for i in p2:
  num=n//i
  t=True
  for j in p2:
    if num%j==0:
      t=False
  if t:
    p.append(num)
if len(p)==0 and n!=1:
  p=[n]
ans=0
for i in p:
  j=1
  while True:
    if n%i==0:
      n//=i
      j+=1
    else:
      j-=1
      break
  ans+=f(j)
print(ans)

Submission status: Accepted

Solution code:
import collections

N=int(input())
ans=0

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


if N==1:
	print(0)
	
else:
	lis=collections.Counter(prime_factorize(N))
	lis_=list(lis.values())
	for i in range(len(lis_)):
		for h in range(1,45):
			if lis_[i]>=h*(h+1)/2:
				ans+=1
	print(int(ans))

Submission status: Accepted

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

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

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

    return arr

n = int(input())
result=0
flg=0
for i in range(len(fac(n))):
  target = fac(n)[i][1]
  if fac(n)[i][0] <= 1:
    flg=1
    break
  sikii=0
  for j in range(1,target+1):
    sikii += j
    if sikii <= target < (sikii+j+1):
      result += j
      break
if flg == 1:
  print('0')
else:
  print(result)

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

pf = prime_factorize(N)
setpf = set(pf)

import collections
cpf = collections.Counter(pf)

cnt = 0
for i in setpf:
    tmp = cpf[i]
    for j in range(1,50):
        tmp -= j
        if tmp < 0:
            break
        else:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
def make_divisors(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 check(n,divisors):
    for i in divisors:
        if n % i == 0:
            k  = n
            while True:
                n = n / i

                if n == 1:
                    return k

                if n % i != 0:
                    return 0
     

n = int(input())
divisors = make_divisors(n)
count = 0

divisors.pop(0)

ds = []

for a in divisors:
    result = check(a,divisors)
    if result != 0:
        ds.append(result)
    
for divisor in ds:
    if n % divisor == 0:
        n = n / divisor
        count += 1

print(count)

Submission status: Accepted

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

import math

if n == 1:
    print(0)
else:
    l = fctr1(n)
    ans = 0
    for i in l:
        ans += math.floor((-1+math.sqrt(1+8*i[1]))/2)
    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

c = Counter(prime_factorize(N))
n = 0
for prime in c:
    wa = 1
    count = 1
    length = c[prime]
    while True:
        if c[prime] >= wa:
            n += 1
            count += 1
            wa += count
        else:
            break
print(n)

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

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

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

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

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input().split())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input().split()) for _ in range(n) ]

n = I()

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

# nまでの自然数が素数かどうかを表すリストを返す
# Sieve of Eratosthenes
def makePrimeChecker(n):
    isPrime = [True] * (n + 1)
    isPrime[0] = False
    isPrime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if isPrime[i]:
            for j in range(i * i, n + 1, i):
                isPrime[j] = False
    return isPrime

# """nを素因数分解"""
# """2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
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(m))
## [[2, 3], [3, 1]] 
##  24 = 2^3 * 3^1

a = factorization(n)
# print(a)

ls = []
count = -1
wa = 0
for i in range(40):
    count += 1
    wa += count
    ls.append(wa)
# print(ls)

ans = 0
for _,m in a:
    ind = bisect_right(ls,m)
    ans += ind-1
print(ans)

Submission status: Accepted

Solution code:
import sys

n = int(input())

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

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

c = collections.Counter(prime_factorize(n))
v = list(c.values())

count= 0
for e in v:
    for i in range(1,40):

        e -= i
        if e >= 0:
            count += 1
        else:
            break

print(count)

Submission status: Accepted

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

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

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

    return arr
def wa(x):
    return x*(x+1)/2

ans = []
n = int(input())
if n == 1:
    print(0)
else:
    fac = factorization(n)
    for i in range(len(fac)):
        j = 1
        while True:
            if wa(j) <= fac[i][1] and fac[i][1] < wa(j+1):
                break
            else:
                j += 1
        ans.append(j)
    print(sum(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))

s = 0

def check(x):
    k = 1
    l = 0
    while x >= l + k:
        l += k
        k += 1
    return k-1


for v in c.values():
    s += check(v)



print(s)

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

c = collections.Counter(prime_factorize(int(input())))
ans = 0
for k in c.keys():
    d = c[k]
    m =1
    while d>0:
        d -= m
        if d <= m:
            ans += m
            break
        m += 1
print(ans)

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

s=factorization(a) 
ans=0
for i in s:
    if i[0]>1:
        tmp=0
        count=0
        while True:
            tmp+=count
            if i[1]<tmp:
                count-=1
                break
            else:
                count+=1
                
        ans+=count
            
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)

import math

import logging

from collections import defaultdict

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)


def prime_factor(n: int):
    """素因数分解
    
    Args:
        n (int): [description]
    
    Returns:
        [type]: [description]
    """
    res: defaultdict = defaultdict(int)
    res[1] = 1
    for i in range(2, math.ceil(math.sqrt(n))):
        while (n % i == 0):
            res[i] += 1
            n = n // i

    if (n != 1):
        res[n] = 1

    return res


def count(n):
    i = 0
    a = 1
    while (True):
        n = n - a
        if n >= 0:
            i += 1
            a += 1
        else:
            break

    return i


def resolve():
    # S = [x for x in sys.stdin.readline().split()][0]  # 文字列 一つ
    N = [int(x) for x in sys.stdin.readline().split()][0]  # int 一つ
    # N, D = [int(x) for x in sys.stdin.readline().split()]  # 複数int
    # h_list = [int(x) for x in sys.stdin.readline().split()]  # 複数int

    # grid = [list(sys.stdin.readline().split()[0]) for _ in range(N)]  # 文字列grid
    # v_list = [int(sys.stdin.readline().split()[0]) for _ in range(N)]
    # grid = [[int(x) for x in sys.stdin.readline().split()]
    #         for _ in range(N)]  # int grid

    factors = prime_factor(N)

    logger.debug('{}'.format([factors]))

    ret = 0

    for key, value in factors.items():
        if key != 1:
            ret += count(value)

    print(ret)


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """24"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """1"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """64"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """1000000007"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_5(self):
        input = """997764507000"""
        output = """7"""
        self.assertIO(input, output)

Submission status: Accepted

Solution code:
import math
def primeFactors(n):
    pri = []
    while n % 2 == 0:
        pri.append(2)
        n = n // 2
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        while n % i == 0:
            pri.append(i)
            n = n // i
    if n > 2:
        pri.append(n)
    return pri
n = int(input())
if n==1:
    print(0)
    exit(0)
fact = set()
for i in range(2,int(n**0.5)+1):
    if n%i==0:
        fact.add(i)
        fact.add(n//i)
fact.add(n)
fact = sorted(fact)
cnt = 0
for i in fact:
    p = primeFactors(i)
    if p.count(p[0])==len(p):
        if n%i==0:
            n//=i
            # print(i, n)
            if n >= 1:
                cnt += 1
            else:
                break
print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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())
so = factorization(n)
#print(so)

#print(len(so))
flg = 0
for i in range(len(so)):
    if so[i][0] == 1: continue
    var = 1
    sta = 1 
    while(so[i][1]>=sta):
        #print(var,so[i][1])
        flg+=1
        var+=1
        sta +=var

print(flg)

Submission status: Accepted

Solution code:
#import math
#=input()
n=int(input())
#a,b=map(float,input().split())
#=list(map(int,input().split()))
#=[list(map(int,input().split())) for _ in range()]
import collections
def pf(x):
    a = []
    while x % 2 == 0:
        a.append(2)
        x //= 2
    f = 3
    while f ** 2 <= x:
        if x % f == 0:
            a.append(f)
            x //= f
        else:
            f += 2
    if x != 1:
        a.append(x)
    return a
c = collections.Counter(pf(n))
if n == 1:
    counts = [0]
else:
    values, counts = zip(*c.most_common())
ans = 0
for i in range(len(counts)):
    q = counts[i]
    for j in range(100):
        if (j * (j + 1)) > (2 * q):
            j -= 1
            break
    ans += j
print(ans)

Submission status: Accepted

Solution code:

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

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

    return True

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と正の整数eを用いて、z=P**eと表せる
# N%z==0
# z=まだ選んでない素数だけ選ぶ
# N = N/zに置き換える


# n = 24
# 24を素因数分解する
# z=2, 2*1
# n = 24/2

# n = 12
# z=2, 3*1
# n = 24/2


N = int(input())
#cnt = 0
z = []

def solve(N, cnt):
  #print("N:", N)
  f = factorization(N)
  #print(f)

  
  # 素因数分解の要素数分ループ
  for i in range(len(f)):
    # Pが素数かチェック
    p = f[i][0]
    #print("p:", f[i][0])
    if is_prime(p):
      # 指数の数だけループ
      for e in range(1, f[i][1]+1):
        # 未採用のzを見つける. 割り切れる数を見つける
        if (p**e in z) == False and N % (p**e) ==0:
          # 使用済みリストに追加
          z.append(p**e)
          #print("z:", p**e, "p**e:", p,e)
          cnt +=1
          #print("cnt", cnt)
          cnt = solve(N//p**e, cnt)
          return cnt
  return cnt


cnt = solve(N, 0)
print(cnt)

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

P = factorization(N)

flag = 0

for i in range(len(P)):
  for j in range(40):
    P[i][1] = P[i][1] - (j + 1)
    if P[i][1] >= 0:
      flag += 1
    else:
      break
if N == 1:
  print(0)
else:
  print(flag)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)



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

import math
def isPrime(num):
    if num < 2: return False
    elif num == 2: return True
    elif num % 2 == 0: return False
    for i in range(3, math.floor(math.sqrt(num))+1, 2):
        if num % i == 0:
            return False
    return True

if isPrime(n):
    print(1)
    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

sisu=(factorization(n))
#print(sisu)
cnt=0
for item in sisu:
    i=1
    tmp=item[1]
    while tmp>=i:
        tmp-=i
        cnt+=1
        i+=1

print(cnt)

Submission status: Accepted

Solution code:
import math
n=int(input())
X=[0]*(10**6+1)
if n==1:
    ans=0
else:
    p=int(math.sqrt(n))
    for i in range(2,int(math.sqrt(n)+1)):
        cnt=0
        while n%i==0:
            n//=i
            cnt+=1
        X[i]=cnt
    ans=0
    for x in X:
        if x>=55:
            ans+=10
        elif x>=45:
            ans+=9
        elif x>=36:
            ans+=8
        elif x>=28:
            ans+=7
        elif x>=21:
            ans+=6
        elif x>=15:
            ans+=5
        elif x>=10:
            ans+=4
        elif x>=6:
            ans+=3
        elif x>=3:
            ans+=2
        elif x>=1:
            ans+=1

    if n!=1:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import math
from collections import defaultdict


def main():
    n = int(input().strip())

    divs = get_divs(n)
    ans = 0
    for p in divs:
        ans += s_to_n(divs[p])
    print(ans)


def get_divs(n: int) -> dict:
    divs = defaultdict(int)
    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            divs[i] += 1
            n //= i
    if n != 1:  # n が残ってたら、それも入れる
        divs[n] += 1
    return divs


def s_to_n(s: int):
    ss = 0
    n = 1
    while ss < s:
        n += 1
        ss += n
    return n - 1


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    from math import log
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    N = int(input())
    prime = [True for i in range(int(N**.5)+2)]
    ans = 0
    if N == 1:
        print(0)
        exit()
    while True:
        # print('N = {}'.format(N))
        max_ = int(N ** .5) + 1
        for p in range(2, max_):
            if not prime[p]:
                continue
            for q in range(p, max_, p):
                prime[q] = False
            if N % p != 0:
                continue
            # print('p = {}'.format(p))
            t = 1
            p_ = p
            while N % p_ == 0:
                t += 1
                p_ *= p
            t -= 1
            l, r = 0, 10 ** 6
            # print('t = {}'.format(t))
            while l + 1 < r:
                m = (l + r) // 2
                if m * (m + 1) // 2 <= t:
                    l = m
                else:
                    r = m
            # print('ans += {}'.format(l))
            N //= (p ** t)
            ans += l
            break
        else:
            if N != 1:
                ans += 1
            break
    if ans == 0:
        ans = 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import floor,sqrt
N=int(input())

p = [1]*floor((10**6))
p[0]=p[1]=0
prime=[]
for i in range(2,len(p)):
    if p[i]==0:
        continue
    prime.append(i)
    for j in range(i*2,len(p),i):
        p[j]=0

ans=0
for x in prime:
    if N%x!=0:
        continue
    cnt=0
    while N%x==0:
        cnt+=1
        N//=x
    ans+=floor((-1+sqrt(1+8*cnt))/2)
print(ans+int(N!=1))

Submission status: Accepted

Solution code:
import sys
import collections

N = int(input())

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 collections.Counter(a).items()

list = factorize(N)
ans = 0
tmp = [0,1,3,6,10,15,21,28,36,45,55,66,78,91]
for k,v in list:
    for j in range(len(tmp)):
        if v < tmp[j]:
            ans += j - 1
            break

print(ans)

Submission status: Accepted

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *					# ll = deepcopy(l)
from heapq import *					# heappush(hp,x)
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *				# bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin				# bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize				# minn = -maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *				# pre = [0] + list(accumulate(l))
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''
24
'''

def isPrime(x):
	if(x == 1 or x == 4):
		return False
	elif(x in [2,3,5]):
		return True
	for i in range(2,int(sqrt(x))+1):
		if(x%i == 0):
			return False
	return True

def primeFactors(n):
	d = defaultdict(int)
	if(isPrime(n)):
		return {n:1}
	else:
		while(not n%2):
			n //= 2
			d[2] += 1
		for i in range(3,int(sqrt(n))+1,2):
			while(not n%i):
				n //= i
				d[i] += 1
		if(n > 2):
			d[n] += 1
	return dict(d)

def solve(l):
	ans = 0
	d = primeFactors(l)
	for i in d:
		l = d[i]
		ans += max(0,int((sqrt(1+8*l)-1)/2))
	return ans

N = int(stdin.readline())
ans = solve(N)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = int(n**0.5)+1

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


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


def waru(n, s, ans):
    a = int(n**0.5)+1
    for i in range(s, a+1):
        j = 1
        frag = 0
        while 1:
            if n % pow(i, j) == 0:
                frag = 1
                n = n//pow(i, j)
                ans += 1
                j += 1
            elif frag == 1:
                return (n, i, ans)
            else:
                break


a = prime_factorize(n)
c = set(a)
b = int(n**0.5)+1
ans = 0
for i in c:
    s = a.count(i)
    j = 1
    while 1:
        if s-j >= 0:
            ans += 1
            s = s-j
            j = j+1
        else:
            break
if ans == 0:
    print(1)
    exit()
print(ans)

Submission status: Accepted

Solution code:
import math
import bisect

N = int(input())

def printCount(N):
    if N <= 1:
        print(0)
        return

    num = N
    primeDivisions = []

    limit = [1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595, 630, 666, 703, 741, 780]

    primeCounts = []
    for factor in range(2, int(math.sqrt(N)) + 1):
        if num % factor != 0:
            continue
        count = 0
        while num % factor == 0:
            count += 1
            num //= factor
        primeCounts.append(count)
    if num != 1:
        primeCounts.append(1)

    if len(primeCounts) == 0:
        print(1)
    else:
        result = 0
        for count in primeCounts:
            index = bisect.bisect_right(limit, count)
            result += index
        print(result)

printCount(N)

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

def main():
    n = int(input())
    c = collections.Counter(prime_factorize(n))
    li = list(c.values())
    ans = 0
    for i in li:
        k = i
        for j in range(60):
            k -= j
            if k < 0:
                ans += j - 1
                break
    print(ans)

 
 
if __name__ == '__main__':
  main()

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

num_list = prime_factorize(N)

from collections import defaultdict
d = defaultdict(int)

for key in num_list:
    d[key] += 1

cnt = 0
for key,value in d.items():
    for i in range(1,value+1):
        if value-i >= 0:
            cnt+=1
            value -= i
            
print(cnt)

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

PrimeFactors = collections.Counter(prime_factorize(N))
countPrime = PrimeFactors.values()
cnt = 0
for i in countPrime:
    counter = 0
    for j in range(1,20):
        i = i - j
        if i >= 0:
            cnt += 1
        else:
            break
print(cnt)

Submission status: Accepted

Solution code:
N=int(input())
import math
 
# 素数判定関数
def isPrime(num):
    # 2未満の数字は素数ではない
    if num < 2: return False
    # 2は素数
    elif num == 2: return True
    # 偶数は素数ではない
    elif num % 2 == 0: return False
 
    # 3 ~ numまでループし、途中で割り切れる数があるか検索
    # 途中で割り切れる場合は素数ではない
    for i in range(3, math.floor(math.sqrt(num))+1, 2):
        if num % i == 0:
            return False
 
    # 素数
    return True
 
# 素数判定
def callIsPrime(input_num=1000):
    numbers = []
    # ループしながら素数を検索する
    for i in range(1, input_num):
        if isPrime(i):
            numbers.append(i)
 
    # 素数配列を返す
    return numbers
 
# 関数の呼び出し
 
P=callIsPrime(int(math.sqrt(N))+1)
#print(P)
ans=0
#ans+=isPrime(N)
for i in P:
  count=1
  #print(i)
  while(N%(i**count)==0):
    ans+=1
    N=N//(i**count)
    #print(i**count)
    count+=1
  while(N%i==0):
    N=N//i
ans+=isPrime(N)
    
 
#print(make_divisors(N))
#print(N)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# n,m = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(sys.stdin.readline() for _ in range(n)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# n = int(sys.stdin.readline())
# INF = float("inf")
# sys.setrecursionlimit(10000)
import sys,collections,math
sys.setrecursionlimit(100000)
N = int(sys.stdin.readline())
i = 2
lim = N**0.5
res = []
while i <= lim:
    if N%i != 0:
        i += 1
        continue
    ex = 0
    while N%i == 0:
        ex += 1
        N = N/i
    res.append((i,ex))
    i += 1
if N != 1: res.append((N,1))
def num(n):
    s = 1
    ret = 1
    while s+ret < n: # 1 ok #2 ok
        ret += 1
        s += ret
    return ret

# for i in range(11):
#     print(num(i))

#print(res,[num(x) for _,x in res])
print(sum(num(x) for _,x in res))