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: Time Limit Exceeded

Solution code:
n= int(input())

def div(x):
	for p in primes:
		if p>x**0.5:
			break
		if x%p== 0:
			return False
	return True

primes= [2]
for num in range(3, int(n**0.5)):
	if div(num):
		primes.append(num)

###

prime_factors= {}

while n != 1:
	for p in primes:
		if n%p==0:
			if p in prime_factors:
				prime_factors[p]+=1
				n/=p
				break
			else:
				prime_factors[p]=1
				n/= p
				break
		elif div(n):
			if n in prime_factors:
				prime_factors[n]+=1
				n/=n
				break
			else:
				prime_factors[n]=1
				n/= n
				break
tot= 0
for p in prime_factors:
	if prime_factors[p]>=36:
		tot+= 8
	elif prime_factors[p]>=28:
		tot+=7
	elif prime_factors[p]>=21:
		tot+=6
	elif prime_factors[p]>=15:
		tot+=5
	elif prime_factors[p]>=10:
		tot+=4
	elif prime_factors[p]>=6:
		tot+=3
	elif prime_factors[p]>=3:
		tot+=2
	else:
		tot+=1
print(tot)

Submission status: Time Limit Exceeded

Solution code:
#23ぐらいまでで良さそう。
z = [2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23]

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]]

sosuu = primes(10001000)
count = [0] * len(sosuu)
convert = [0] * 56

N = int(input())
ans = 0

flag = True
while (flag):
        flag = False
        for i in range(len(sosuu)):
                if N % sosuu[i] == 0:
                        N = N // sosuu[i]
                        count[i] += 1
                        flag = True

tmp = 0
for i in range(1, 11):
        tmp += i
        convert[tmp] = i
for i in range(1, len(convert)):
        if convert[i] == 0:
                convert[i] = convert[i - 1]


for i in count:
        ans += convert[i]

if N > sosuu[-1] and ans == 0:
        ans = 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

def using_sqrt(limit,elm):
    n = 0
    if limit < 2:
        return 0

    elm.append(2)

    for k in range(3, limit+1,2):
        factor = 0

        # 2以外の偶数は素数ではないので無視する
        if k % 2 == 0 and k != 2:
            continue

        # 繰り返しの上限を対象の平方根にする
        max = math.floor(math.sqrt(k))+1
        for divisor in range(3, max, 2):
            if k % divisor == 0:
                factor += 1

        if factor == 0:
            elm.append(k)
            n += 1

    return n


N = int(input())
A = []

using_sqrt(N,A)

A_len=len(A)

for i in range(A_len):
    chk = A[i]
    while True:
        chk *= A[i]
        if chk <= N:
            A.append(chk)
        else:
            break

A.sort()

A_len=len(A)
cnt = 0
chk_N = N
for i in range(A_len):
    if chk_N % A[i] == 0:
        chk_N = int(chk_N / A[i])
        cnt += 1

    if chk_N == 1:
        break

print(cnt)

Submission status: Time Limit Exceeded

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

from functools import reduce

import math

def is_prime(n):
    if n % 2 == 0 and n > 2: 
        return False
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True

def sieve(n):
    n=int(n)
    # Create a boolean array "prime[0..n]" and initialize 
    # all entries it as true. A value in prime[i] will 
    # finally be false if i is Not a prime, else true. 
    prime = [True for i in range(n + 1)] 
    p = 2
    while (p * p <= n): 
          
        # If prime[p] is not changed, then it is a prime 
        if (prime[p] == True): 
              
            # Update all multiples of p 
            for i in range(p * 2, n + 1, p): 
                prime[i] = False
        p += 1
    prime[0]= False
    prime[1]= False

    return [i for i, p in enumerate(prime) if p]

def inthroot(x,n):
    "calculate floor(x**(1/n))"
    return math.floor(x**(1/n))

def is_a_power(n):
    "return (a,b) if n=a**b otherwise throw ValueError"
    for b in sieve( math.log2(n) +1 ):
        if b == 0:
            raise ValueError
            
        a = inthroot(n,b)
        if a**b == n:
            return a,b
    raise ValueError
    


def smooth_factorization(n):
    "return (p,e) where p is prime and n = p**e if such value exists, otherwise throw ValueError"
    e=1
    p=n
    while True:
        try:
            p,n = is_a_power(p)
            e = e*n
        except ValueError:
            break
    if is_prime(p): 
        return p,e


# def factors(n):
#     return set(
#         reduce(
#             list.__add__,
#             ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0),
#         )
#     )

def factors(n):    
        l1, l2 = [], []
        for i in range(1, int(n ** 0.5) + 1):
            q,r = n//i, n%i     # Alter: divmod() fn can be used.
            if r == 0:
                l1.append(i) 
                l2.append(q)    # q's obtained are decreasing.
        if l1[-1] == l2[-1]:    # To avoid duplication of the possible factor sqrt(n)
            l1.pop()
        l2.reverse()
        return l1 + l2
        
def solve(N: int):
    count = 0
    picked_z = set([])

    while True:
        zs = list(factors(N))
        zs.remove(1)

        for i, z in enumerate(zs):
            is_prime_power = smooth_factorization(z)
            if is_prime_power and z not in picked_z:
                picked_z.add(z)
                N = N / z
                count += 1
                break

        if len(zs) == 0:
            break

    print(count)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#d
n = int(input())
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
if is_prime(n):
    print("1")
    
else:
    used = []
    ans = 0
    for i in range(2,10**12):
        if is_prime(i):
            if n%i ==0:
                n = n/i
                used.append(i)
                ans += 1    

        else:
            for j in used:
                k = j**2
                count = 2
                flag = 0

                while k <= i:
                    k = j**count
                    if k == i:
                        if n % i == 0:
                            n = n/i
                            ans += 1
                            flag = 1
                            break
                    count+= 1
                if flag == 1:
                    break
        if i > n:
            break
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
x = int(input())
import math
from collections import defaultdict


def isprime(n):
    if n <= 1:
        return 0
    m = int(math.sqrt(n)) + 1
    for i in range(2, m):
        if n % i == 0:
            return 0
    return 1


if isprime(x):
    print(1)
else:
    res = 0
    value = defaultdict(int)


    def bprime(n):
        cnt = 2
        while n != 1:
            while n % cnt == 0:
                n //= cnt
                value[cnt] += 1
            cnt += 1
    def cal(n):
        j = 1
        cnt = 0
        while n >= j:
            n -= j
            j += 1
            cnt += 1
        return cnt
    bprime(x)
    for key in value.keys():
        res += cal(value[key])
    print(res)

Submission status: Time Limit Exceeded

Solution code:
import collections
n=int(input())
i=2
l=[]
while True:
  if n==1:
    break
  if n%i==0:
    l.append(i)
    n=n//i
  else:
    i+=1
c=collections.Counter(l)
v=list(c.values())
ans=0
for vv in v:
  wa=1
  s=1
  while True:
    if vv<wa:
      break
    s+=1
    wa+=s
  ans+=(s-1)
print(ans)

Submission status: Time Limit Exceeded

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

n = int(input())
l = []
l_s = callIsPrime(n)
cnt = 0
for i in l_s:
    s = i
    while s <= n :
        l.append(s)
        #print(i)
        s *= i

l = set(l)

l = sorted(l)

for i in l :

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

    if i == 1 :
        break

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
target = int(input())
ans = 0
waru = 2
while target >= waru:
  if target % waru == 0:
    for i in range(2, waru + 1):
      if waru % i == 0:
        waruwaru = i
        break
    waru_copy = waru
    while waru_copy != 1:
      if waru_copy % waruwaru == 0:
        waru_copy /= waruwaru
      else:
        break
    else:
      target /= waru
      ans += 1
  waru += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
i=1
facts = []
ans = 0
Number  =n
for i in range(2, Number + 1):
    if(Number % i == 0):
        isprime = 1
        for j in range(2, (i //2 + 1)):
            if(i % j == 0):
                isprime = 0
                break
        if (isprime == 1):
            facts.append(i)

facts = sorted(facts)
for i in range(len(facts)):
    cnt = 1
    while(n >= facts[i]**cnt):
        if(n%(facts[i]**cnt)==0):
            n//=(facts[i]**cnt)
            ans+=1
        cnt+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def soinsu(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=soinsu(n)
c=[]
if n>=2:
    for i in range(max(a)):
        c.append(0)
for i in a:
    c[i-1]+=1
z=0
for i in c:
    d=1
    e=1
    while e<=i:
        z+=1
        d+=1
        e=d*(d+1)/2
print(z)

Submission status: Time Limit Exceeded

Solution code:
x = int(input())
import math
from collections import defaultdict
def isprime(n):
    if n <= 1:
        return 0
    m = int(math.sqrt(n)) + 1
    for i in range(2, m):
        if n % i == 0:
            return 0
    return 1
if isprime(x):
    print(1)
else:
    res = 0
    value = defaultdict(int)
    def bprime(n):
        cnt = 2
        while n != 1:
            while n % cnt == 0:
                n //= cnt
                value[cnt] += 1
            cnt += 1
    def cal(n):
        j  = 1
        cnt = 0
        while n >= j:
            n -= j
            j += 1
            cnt += 1
        return cnt
    bprime(x)
    for key in value.keys():
        res += cal(value[key])
    print(res)

Submission status: Time Limit Exceeded

Solution code:
import math

n = int(input())


sosu = set([2])
tansaku = set(range(3,n+1))
kari = set(tansaku)

while math.sqrt(n) > max(sosu):
    for var in tansaku:
        if var % max(sosu) == 0:
            kari.discard(var)
    tansaku = set(kari)
    sosu.add(min(tansaku))
sosu = sosu | tansaku

i = 1
j = 0
kari = set(sosu)

while n != 1:
    for var in sosu:
        if n % (var ** i) == 0:
            n = n / (var ** i)
            j += 1
        else:
            kari.discard(var)
    sosu = set(kari)

    i += 1
    if i > 1000:
        break

print(j)

Submission status: Time Limit Exceeded

Solution code:
n= int(input())

def div(x):
	for p in primes:
		if p>x**0.5:
			break
		if x%p== 0:
			return False
	return True

primes= [2]
for num in range(3, int(n**0.5)):
	if div(num):
		primes.append(num)

###

prime_factors= {}

while n != 1:
	for p in primes:
		if n%p==0:
			if p in prime_factors:
				prime_factors[p]+=1
				n/=p
				break
			else:
				prime_factors[p]=1
				n/= p
				break
		elif div(n):
			if n in prime_factors:
				prime_factors[n]+=1
				n/=n
				break
			else:
				prime_factors[n]=1
				n/= n
				break
tot= 0
for p in prime_factors:
	if prime_factors[p]>=36:
		tot+= 8
	elif prime_factors[p]>=28:
		tot+=7
	elif prime_factors[p]>=21:
		tot+=6
	elif prime_factors[p]>=15:
		tot+=5
	elif prime_factors[p]>=10:
		tot+=4
	elif prime_factors[p]>=6:
		tot+=3
	elif prime_factors[p]>=3:
		tot+=2
	else:
		tot+=1

print(tot)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

n = N
memo = []
cnt = 0
while N > 1:
    for i in range(2,N+1):
        if i in memo:
            continue
        if N % i == 0:
            memo.append(i)
            n = N // i
            cnt += 1
        N = n    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
PRIME = []


def is_prime(n):
    for p in PRIME:
        if n in DONE or not n % p:
            return False
    PRIME.append(n)
    return True


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

DONE = []
for i in range(2, int(N**0.5) + 1):
    if N == 1 or N in DONE:
        break

    if is_prime(i) and not N % i:
        z = i
        DONE.append(z)
        N /= z
        z *= i
        while not N % z:
            DONE.append(z)
            N /= z
            z *= i
else:
    DONE.append(N)

print(len(DONE))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

count = 0
nums = []
while n != 1:
    for i in range(2, 10*12):
        v, m = divmod(n, i)
        if m == 0:
            if i in nums:
                continue
            
            nums.append(i)
            n = v
            count += 1
        else:
            pass

print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = [2,3,5,7,11,13,17,19,23,29]
for i in range(2,int(n**0.5)+1):
    x = 1
    for j in range(len(p)):
        if(i%p[j] == 0):
            x = 0
            break
    if(x == 1):
        p.append(i)
t = {}
for i in range(len(p)):
    if(n%p[i] == 0):
        t[p[i]] = 1
        n //= p[i]
        while(n%p[i] == 0):
            n //= p[i]
            t[p[i]] += 1
        if(n == 1):
            break
if(n != 1):
    z = 1
else:
    z = 0
k = list(t.keys())
for i in range(len(k)):
    j = 1
    while(1):
        if(t[k[i]] - j >= 0):
            t[k[i]] -= j
            z += 1
            j += 1
        else:
            break
print(z)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

N = I()
pn=[2]
for L in range(3, N // 2):
    chk=True
    for L2 in pn:
        if L%L2 == 0:chk=False
    if chk==True:pn.append(L)

pn2 = list(map(lambda x: x ** 2, pn))
pn3 = list(map(lambda x: x ** 3, pn))
pn4 = list(map(lambda x: x ** 4, pn))
pn5 = list(map(lambda x: x ** 5, pn))
pn6 = list(map(lambda x: x ** 6, pn))
pn7 = list(map(lambda x: x ** 7, pn))
pn8 = list(map(lambda x: x ** 8, pn))
pn9 = list(map(lambda x: x ** 9, pn))
pn10 = list(map(lambda x: x ** 10, pn))
pnall = pn + pn2 + pn3 + pn4 + pn5 + pn6 + pn7 + pn8 + pn9 + pn10
pnallall = list(dict.fromkeys(pnall))
counter = 0
ans = 0
while 1:
    if N % pnallall[counter] == 0:
        N = N / pnallall[counter]
        counter += 1
        ans += 1
    else:
        counter += 1
        if len(pnallall) - 1 < counter:
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod=1000000007
p_l=[]
def prime_t(t):
    i=2
    while i**2<=t:
        if t%i==0:
            return 0
        i+=1
    return 1

def prime_list(tt):
    pl=[]
    for i in range(2,tt+1):
        if prime_t(i):
            pl.append(i)
    return pl

pc={}
ps=set([])
#pl=prime_list(10**12)
pl=prime_list(100000012)

n=int(input())
if n==1:
    print(0)
    exit()
ans=0
chk=1
for i in pl:
#    print(i)
    if n<i:
        break
    if n%i==0:
        chk=1
        x=i
        while 1:
            if n%x==0:
                ans+=1
                n//=x
                x*=i
            else:
                break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

def using_sqrt(limit,elm):
    n = 0
    if limit < 2:
        return 0

    elm.append(2)

    for k in range(3, limit+1,2):
        factor = 0

        # 2以外の偶数は素数ではないので無視する
        if k % 2 == 0 and k != 2:
            continue

        # 繰り返しの上限を対象の平方根にする
        for divisor in range(2, math.floor(math.sqrt(k))+1):
            if k % divisor == 0:
                factor += 1

        if factor == 0:
            elm.append(k)
            n += 1

    return n


N = int(input())
A = []

using_sqrt(N,A)

A_len=len(A)

for i in range(A_len):
    chk = A[i]
    while True:
        chk *= A[i]
        if chk <= N:
            A.append(chk)
        else:
            break

A.sort()

A_len=len(A)
cnt = 0
chk_N = N
for i in range(A_len):
    if chk_N % A[i] == 0:
        chk_N = int(chk_N / A[i])
        cnt += 1

    if chk_N == 1:
        break

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def fanctionA(n):
    AList = []
    BList = []
    tmp = 2
    
    while n > 1:
        if n % tmp == 0:
            if AList.count(tmp) == 0:
                AList.append(tmp)
                BList.append(1)
            else:
                BList[AList.index(tmp)] += 1
            n /= tmp
            tmp = 2
        else:
            tmp += 1
 
    
    return BList
  
    
N = int(input())
 
arr = fanctionA(N)
 
tmp = 1
count = 0
for a in arr:
    while 'true':
        if a >= tmp:
            a -= tmp
            count += 1
            tmp += 1
        else:
            tmp = 1
            break
 
print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

import heapq 
from collections import defaultdict

def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1

heap = [2]
cand = 3
heapq.heapify(heap)
ans = 0
dict_prime = defaultdict(int)
# dict_prime[2] = 2
cnt = 0
if is_prime(N):
    ans = 1
else:
    while(1):
        # print(N)
        # cnt += 1
        # if cnt > 10:break

        sub = heapq.heappop(heap)
        # print(sub)
        # print(cand)
        # print(heap)
        # print(cand)
        # print(heapq)
        if N < sub:
            # print(N,sub)
            # print("a")
            break
        if N % sub == 0:
            N = N // sub
            ans += 1
            if sub not in dict_prime:
                dict_prime[sub] = sub
                dict_prime[sub*sub] = sub
            else:
                dict_prime[sub*dict_prime[sub]] = dict_prime[sub]
                # print("a")
            heapq.heappush(heap, sub*dict_prime[sub])

        while(1):
            if is_prime(cand) and cand not in dict_prime:
                heapq.heappush(heap,cand)
                cand += 1
                break
            else:
                cand += 1


# print()
print(ans)
    



# sqrt(N)以下の素数の集合を求める
# heapqにいれる
# 一番小さいので割れなかったらスルー割れたら累乗してheapqへ入れる

# def get_primes(n):
#     ans = []
#     for i in range(1,n+1):
#         if is_prime(i):
#             ans.append(i)
#     return ans


# prime = get_primes(int(N**(1/2)))

Submission status: Time Limit Exceeded

Solution code:
#ある素数pについて1回目→1+2回割れるか
#割れる→1+2+3回割れるか 割れない→そこが個数
i=int(input())
if i==1:
  print(0)
elif i<=5:
  print(1)
else:
  ans=0
  lsosu=[]
  j=2
  p=i
  r=i**0.5
  lim=int(i//2)#素数を調べる限界
  while j<=lim:
    flag=True
    if j>r and i==p:
      ans=1
      break
    if j>i**0.5:
      ans+=1
      break
    for k in lsosu:
      if k>j**0.5:
        break
      if j%k==0:
        flag=False
        break
    if flag:
      lsosu.append(j)
      cnt=1
      jj=j
      while i%jj==0:
        i=i//(jj)
        jj=jj*j
        ans+=1
      while i%j==0:
        i=i//j
    if i==1:
      break
    if j==2:
      j+=1
    else:
      j+=2
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
count = 0
def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass
p_li = list(set(prime_factor(24)))

for z in range(2,n+1):
    for p in p_li:
        w = math.log(z)/math.log(p)
        div = n/z

        if w.is_integer() and div.is_integer():
            count+=1
            n = n/z

    
    

print(count)

Submission status: Time Limit Exceeded

Solution code:
def isprime(x):
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            return False
    return x!=1

dic={}
n=int(input())
i=2
if isprime(n):
    print(1)
    exit()
while n>1:
    if n%i==0:
        cnt=0
        if isprime(i):
            while n%i==0:
                cnt+=1
                n//=i
        dic[i]=cnt
        # cnt=0
        # if isprime(n//i):
        #     while n%(n//i)==0:
        #         cnt+=1
        #         n//=(n//i)
        #     dic[n//i]=cnt
    i+=1
ans=0
for i in dic:
    x=dic[i]
    r=(-1+(1+8*x)**0.5)//2
    ans+=r
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from math import sqrt
n = int(input())
cnt = defaultdict(int)
index = defaultdict(int)
ans = 0
flag = True

def judge_prime(i):
    cnt = 0
    for j in range(1, int(sqrt(i)) + 1):
        if i % j == 0:
            cnt += 1
    
    if cnt == 1 and i != 1:
        return True
    else:
        return False
while flag == True:
    flag = False
    if judge_prime(n):
        if cnt[n] == 0:
            ans += 1
        break
    for i in range(2, n):
        if judge_prime(i):
            j = index[i] + 1
            while 1:
                if n % (i ** j) == 0 and cnt[i ** j] == 0:
                    n //= i ** j
                    ans += 1
                    flag = True
                    cnt[i ** j] += 1
                    index[i] = j
                    break
                elif i ** j > n:
                    break 
                j += 1
        if flag:
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
 
def f(c):

	cumul = 0
	step = 1
	cc = 0
	while(cumul < c):
		cc +=1
		cumul += step
		step += 1
	if cumul > c: cc -=1
	return cc

d = 2
count = 0
on = n
while(n != 1):
	if n%d==0:
		c = 0
		while(n%d == 0): 
			c += 1
			n /= d
		count += f(c)
	d+=1
print count

Submission status: Time Limit Exceeded

Solution code:
import math
import random


class Prime:
    seed_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

    def is_prime(self, n):

        is_prime_common = self.is_prime_common(n)
        if is_prime_common is not None:
            return is_prime_common

        if n < 2000000:
            return self.is_prime_brute_force(n)
        else:
            return self.is_prime_miller_rabin(n)

    def is_prime_common(self, n):
        if n == 1: return False
        if n in Prime.seed_primes: return True
        if any(map(lambda x: n % x == 0, self.seed_primes)): return False

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

    def is_prime_miller_rabin(self, n):
        

        d = n - 1
        while d & 1 == 0:
            d >>= 1

        # use one of these lines / upper is more efficient.
        witnesses = self.get_witnesses(n)
        # witnesses = [random.randint(1, n - 1) for _ in range(100)]

        for w in witnesses:
            y = pow(w, d, n)

            while d != n - 1 and y != 1 and y != n - 1:
                y = (y * y) % n
                d <<= 1

            if y != n - 1 and d & 1 == 0:
                return False

        return True

    def get_witnesses(self, num):
        def _get_range(num):
            if num < 2047:
                return 1
            if num < 1373653:
                return 2
            if num < 25326001:
                return 3
            if num < 3215031751:
                return 4
            if num < 2152302898747:
                return 5
            if num < 3474749660383:
                return 6
            if num < 341550071728321:
                return 7
            if num < 3825123056546413051:
                return 9
            return 12

        return self.seed_primes[:_get_range(num)]

    def gcd(self, a, b):
        if a < b:
            return self.gcd(b, a)
        if b == 0:
            return a
        while b:
            a, b = b, a % b
        return a

    @staticmethod
    def f(x, n, seed):
       
        p = Prime.seed_primes[seed % len(Prime.seed_primes)]
        return (p * x + seed) % n

    def find_factor(self, n, seed=1):
        
        if self.is_prime(n):
            return n

        x, y, d = 2, 2, 1
        count = 0
        while d == 1:
            count += 1
            x = self.f(x, n, seed)
            y = self.f(self.f(y, n, seed), n, seed)
            d = self.gcd(abs(x - y), n)

        if d == n:
            return self.find_factor(n, seed+1)
        return self.find_factor(d)

    def find_factors(self, n):
        primes = {}
        if self.is_prime(n):
            primes[n] = 1
            return primes

        while n > 1:
            factor = self.find_factor(n)

            primes.setdefault(factor, 0)
            primes[factor] += 1

            n //= factor

        return primes
l=[0]*60
index=1
for i in range(1,10):
  for j in range(index,index+i+1):
    l[j]=i
  index=index+i+1
prime=Prime()
N=int(input())
choice=0
x=0
ans=0
dic=prime.find_factors(N)

for key in dic.keys():
  ans+=l[dic[key]]
print(ans)

Submission status: Time Limit Exceeded

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

import sys
from collections import deque, Counter
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())

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 = list(Counter(prime_factorize(N)).values())

ans = 0
used = {}

for i in range(len(c)):
    acc = 0
    cnt = 1
    while True:
        if c[i] >= acc + cnt:
            c[i] -= acc+cnt
            acc = acc+cnt
            ans += 1
        else:
            break
c = sorted(c)[::-1]

hoge = 1
for hoge in range(1, 1000):
    for _ in range(100000):
        for i in range(len(c)-1):
            if min(c[i:i+hoge+1]) >= 1:
                for k in range(hoge+1):
                    c[i+k]-=1
                ans += 1
        c = sorted(c)[::-1]

print(ans)

Submission status: Time Limit Exceeded

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

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

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

    return arr

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

S = factorization(N)
ans = 0

for i in S:
    cnt = 1
    while i[1] > 0:
        if  i[1] >= cnt:
            i[1] -= cnt
            cnt += 1
            ans += 1
        else:
            continue;

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
def sosu(n):
    sosu=1
    if n==1:
        sosu=0
    sq=int(math.sqrt(n))
    for x in range(2,sq+2):
        if n%x==0 and x<n:
            sosu=0
            break
    return sosu  #素数なら1、そうでなければ0
n=int(input())
so=[]
count=0
if n==1:
    count=0
elif sosu(n)==1:
        count=1
else:
    for x in range(2,int(n/2)+2):
        if x>n:
            break
        hantei=sosu(x)
        shisu=1
        if hantei==1:
            while n%(x**shisu)==0:
                count+=1
                shisu+=1
                n=n/(x**(shisu-1))
print(count)

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
L = N
if L == 1:
    print(0)
else:
    num = 0
    for i in range(2, L):
        if N % i == 0:
            N = N / i
            num = num + 1

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

Submission status: Time Limit Exceeded

Solution code:
n= int(input())

def div(x):
	for p in primes:
		if p>x**0.5:
			break
		if x%p== 0:
			return False
	return True

primes= [2]
for num in range(3, int(n**0.5)):
	if div(num):
		primes.append(num)

###

prime_factors= {}

while n != 1:
	for p in primes:
		if n%p==0:
			if p in prime_factors:
				prime_factors[p]+=1
				n/=p
				break
			else:
				prime_factors[p]=1
				n/= p
				break
		elif p==999983:
			prime_factors[n]=1
			n=1
			break
tot= 0
for p in prime_factors:
	if prime_factors[p]>=36:
		tot+= 8
	elif prime_factors[p]>=28:
		tot+=7
	elif prime_factors[p]>=21:
		tot+=6
	elif prime_factors[p]>=15:
		tot+=5
	elif prime_factors[p]>=10:
		tot+=4
	elif prime_factors[p]>=6:
		tot+=3
	elif prime_factors[p]>=3:
		tot+=2
	else:
		tot+=1


print(tot)

Submission status: Time Limit Exceeded

Solution code:
import math
n=int(input())
count=0
for i in range(2,math.floor(n)+1):
    if n%i==0:
        for j in range(2,i+1):
            if math.log(i,j)==math.floor(math.log(i,j)):
                n=n/i
                count+=1
                break
print(count)