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:
#ある素数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
  lim=int(i//2)#素数を調べる限界
  while j<=lim:
    flag=True
    if j>p**0.5 and i==p:
      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:
N = int(input())

import math


n = math.sqrt(N) + 1

cm = []
idx = 2
while True:
    if N % idx == 0:
        N //= idx
        cm.append(idx)
    else:
        idx += 1
     
    if N == 1:
        break
        
    if (idx > n+1) and len(cm) == 0:
        print(1)
        exit()
        
    if idx > n+1:
        cm_ = cm
        for i in cm_:
            cm.append(N//i)
        break

#print(cm)

su = [0] * 1000
s = 0
for i in range(1, 40+1):
    s += i
    #print(s)
    su[s] = i
    
#print(su)

f = 0
for i in range(1000):
    if su[i] == 0:
        su[i] = f
    else:
        f = su[i]

#print(su)

count = 0
for i in list(set(cm)):
    #print(cm.count(i))
    count += su[cm.count(i)]

    
print(count)

Submission status: Time Limit Exceeded

Solution code:
a = int(input())

ans = 0

pn=[2];A=a+1
for L in range(3,A):
    chk=True
    for L2 in pn:
        if L%L2 == 0:chk=False
    if chk==True:pn.append(L)

for p in pn:
  t=1
  while a%(p**t)==0:
    ans+=1
    a=a//(p**t)
    t+=1

print(str(ans))

Submission status: Time Limit Exceeded

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 gen_list_n_removed(l, n):
    return [i for i in l if i != n]



N = int(input())

num_list = set()

hoge = [i for i in range(2, 10000000) if is_prime(i)]

for i in range(1, 30):
    for j in hoge:
        res = j ** i
        if res > 10 ** 12:
            break
        num_list.add(j ** i)

num_list = sorted(num_list)

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

count = 0
while True:
    for i in num_list:
        if N % i == 0:
            N = N / i
            count += 1
            num_list = gen_list_n_removed(num_list, i)
            break
        if i == num_list[-1]:
            print(count)
            exit(0)

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):
        """
        prime test (hybrid)

        see also: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """
        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):
        """
        brute force prime test
        use with is_prime_common if you want to skip seed_primes

        :param n:
        :return: boolean
        """
        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):
        """
        miller rabin prime test
        use with is_prime_common if you want to skip seed_primes

        see also
            algorithm: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
            implementation: https://qiita.com/srtk86/items/609737d50c9ef5f5dc59
            improvement: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """

        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):
        """
        pseudo prime generator
        :param x:
        :param n:
        :param seed:
        :return: pseudo prime
        """
        p = Prime.seed_primes[seed % len(Prime.seed_primes)]
        return (p * x + seed) % n

    def find_factor(self, n, seed=1):
        """
        find one of factor of n
        this function is based to Pollard's rho algorithm

        see also
            algorithm: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
            implementation: https://qiita.com/gushwell/items/561afde2e00bf3380c98

        :param n:
        :param seed:
        :return: factor
        """
        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:
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, 10**6):
	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

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


def ps(n): 
    t=0
    while n % 2 == 0: 
        t=1 
        n = n / 2
    for i in range(3,int(math.sqrt(n))+1,2):
        if(n%i==0):
            t+=1
        while n % i== 0: 
            n = n / i
            if(t>1):
                return 0 
    if n > 2: 
        t+=1
        if(t>1):
            return 0
    return 1 

n=int(input())
j=2
c=0
if(pc(n)==1):
    print("1")
    exit()
while(n>1):
    if(ps(j)==1)and(n%j==0):
        n/=j
        c+=1
    j+=1
print(c)

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, 10**6):
	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
			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:
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())
flag = 0
if N == 1:
    flag = -1
M = len(factorization(N))
num = [1,3,6,10,15,21,28,36]
ans = 0
for i in range(M):
    for j in range(len(num)):
        if num[j] <= factorization(N)[i][1]:
            ans += 1

if flag == -1:
    print(0) 
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from math import sqrt
n = int(input())
cnt = 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 = 1
            while 1:
                if n % (i ** j) == 0 and cnt[i ** j] == 0:
                    n //= i ** j
                    ans += 1
                    flag = True
                    cnt[i ** j] += 1
                    break
                elif i ** j > n:
                    break 
                j += 1
        if flag:
            break
print(ans)

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:
import decimal
import math

N = int(input())

ans = 0
loop = min(N//2, 10**12)
for i in range(2, loop):
  if N % i == 0:
    ans += 1
    N = (N // i)

print (ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
d = 2
count = 0 
def f(c):
	
	cumul = 0
	step = 1
	stack = []
	while(cumul < c):
		stack.append(step)
		cumul += step
		step += 1
	if cumul > c:
		cumul -= stack.pop()
	return len(stack)



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:
# coding: utf-8
import sys

# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict

sys.setrecursionlimit(10 ** 7)
# import math
# from itertools import product, accumulate, combinations, product
# import bisect# lower_bound etc
#import numpy as np
# from copy import deepcopy
#from collections import deque
#import numba
import math

def run():
    N = int(input())

    primes = []
    p = [0] * 1000000

    for i in range(2, 1000000):
        done = False
        m = int(i ** (1/2))
        for k in primes:
            if k > m:break
            if i % k == 0:
                done = True
                break
        if not done:
            primes.append(i)
            p[i] = 1


    count = 0

    for i in primes:
        if p[2]:
            s = i
            while True:
                if not N % s:

                    N = N // s
                    count += 1
                    s *= i

                else:break
            s = s // i
            while s > 0:
                if not N % s:
                    N = N // s
                else:
                    s = s // i

    if count == 0 and N != 1:
        print(1)
    elif N != 1:
        print(count + 1)
    else:
        print(count)



if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

import math


n = math.sqrt(N) + 1

cm = []
idx = 2
while True:
    if N % idx == 0:
        N //= idx
        cm.append(idx)
    else:
        idx += 1
     
    if N == 1:
        break
        
    if (idx > n+1) and len(cm) == 0:
        print(1)
        exit()

#print(cm)

su = [0] * 1000
s = 0
for i in range(1, 40+1):
    s += i
    #print(s)
    su[s] = i
    
#print(su)

f = 0
for i in range(1000):
    if su[i] == 0:
        su[i] = f
    else:
        f = su[i]

#print(su)

count = 0
for i in list(set(cm)):
    #print(cm.count(i))
    count += su[cm.count(i)]

    
print(count)

Submission status: Time Limit Exceeded

Solution code:
def cin(): # To take limited number of inputs
    return map(int,input().split())

def cins(): # To take space sepreated strings
    return input.split()

def cino(test=False): # To take individual int input (test = False)
    if not test:
        return int(input())
    else: # To take string input (test = True)
        return input()

def cina(): # array input
  return list(map(int,input().split()))

def ssplit(): # multiple string input
    return list(input().split())

def printlist(l): # To print space seperated array
    for i in l:
        print(i,end=" ")

import math
import sys
import fractions
import random
def sieve(n):
	sqrtn = int(n**0.5)
	sieve = [True] * (n+1)
	sieve[0] = False
	sieve[1] = False
	for i in range(2, sqrtn+1):
		if sieve[i]:
			m = n//i - i
			sieve[i*i:n+1:i] = [False] * (m+1)
	return sieve
isprime=sieve(100000)
write = sys.stdout.write
def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
def mr_pass(a, s, d, n):
    a_to_power = pow(a, d, n)
    if a_to_power == 1:
        return True
    for i in range(s-1):
        if a_to_power == n - 1:
            return True
        a_to_power = (a_to_power * a_to_power) % n
    return a_to_power == n - 1
def is_prime(n):
	if n<100000:
		return isprime[n]
	d = n - 1
	s = 0
	while d % 2 == 0:
		d >>= 1
		s += 1
	for repeat in range(3):
		a=random.randint(1,n-1)
		if not mr_pass(a, s, d, n):
			return False
	return True
def prime_power(n):
	power =int(math.log(n,2))
	for i in range(1,power+1):
		if i==1:m=n
		elif i==2:m=int(math.sqrt(n))
		else:m=int(round(math.exp(math.log(n)/i),0))
		if(n==(m**i) and is_prime(m)):
			return 1
	return 0

def main():
    a = cino()
    i = 2
    cnt = 0
    while(a>1):
        if prime_power(i):
            if a%i==0:
                a = a//i
                cnt += 1
        i += 1
        
    print(cnt)
        


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

def get_prime(N):
    prime_list = [2]
    for num in range(3,N+1,2):
      if all( num % prime != 0 for prime in prime_list) and N % 2 == 0:
        prime_list.append(num)
    return prime_list

n = int(input())
init_n = n
lst = get_prime(n)
tmp = lst.copy()
for i in tmp:
  hoge = 2
  while True:
    foo = i**hoge
    if foo > n:
      break
    lst.append(foo)
    hoge += 1

lst.sort()
c = 0
for i in range(len(lst)):
  a = lst.pop(0)
  if n % a == 0:
    n = n / a
    c += 1
if init_n == 1:
  print(0)
else:
  print(c)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def is_prime(a):
  if a == 1:
    return False
  
  for i in range(2, 1+int(a**0.5)):
    if a % i == 0:
      return False
  return True

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]

n = int(input())

ans = 0
z = 2

while True:
  if z > n:
    break
  if is_prime(n):
    ans += 1
    break
    
  if n % z != 0:
    z += 1
    continue
  
  tmp_divisors = make_divisors(z)
  for p in tmp_divisors[1:]:
    if not is_prime(p):
      continue
    tmp = np.log(z)/np.log(p)
    if tmp > 0 and tmp == int(tmp):
      n = n/z
      ans += 1
      z += 1
      break
  else:
    z += 1

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))

def prime_factorization(n):
    r = []
    while not n & 1:
        r += [2]
        n >>= 1
    i = 3
    maxv = sqrt(n)
    while i < n / 2:
        while not n % i:
            r += [i]
            n //= i
        i += 2
    if n != 1: r += [n]
    return r

n = int(input())
if n == 1:
    print(0)
    sys.exit()
p = prime_factorization(n)
#print(p)
ans = 0
for i in range(2, max(p)+1):
    m = p.count(i)
    v = 0
    cnt = 0
    while v <= m:
        v += cnt + 1
        cnt += 1
        #print(v, cnt)
    #print(i, m, cnt - 1)
    ans += cnt - 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
if n <= 1:
    print(0)
else:
    prime = True
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            prime = False
            break
    if prime:
        print(1)
    else:
        num = 2
        initial = 1
        track = 1
        count = 0
        while num <= n:
            if n % num == 0:
                track -= 1
                if track == 0:
                    count += 1
                    initial += 1
                    track = initial
                n = n // num
            else:
                num += 1
                initial = 1
                track = 1
        print(count)

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
# A, B = [i for i in input().split()]
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
n = N
count = 0
i = 1
while True:
    if n == 1 or i > n:
        break
    if n % i == 0:
        if i == 1:
            if is_prime(n):
                count += 1
                n //= n
        elif is_prime(i):
            x = i
            while True:
                if n % x != 0:
                    break
                if x > n:
                    break
                n //= x
                count += 1
                x *= i
    i += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input(""))

count = 0
z = 2
while N > 1:
  r = N % z
  if r == 0:
    N = N//z
    count += 1
    z += 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):
        """
        prime test (hybrid)

        see also: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """
        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):
        """
        brute force prime test
        use with is_prime_common if you want to skip seed_primes

        :param n:
        :return: boolean
        """
        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):
        """
        miller rabin prime test
        use with is_prime_common if you want to skip seed_primes

        see also
            algorithm: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
            implementation: https://qiita.com/srtk86/items/609737d50c9ef5f5dc59
            improvement: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """

        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):
        """
        pseudo prime generator
        :param x:
        :param n:
        :param seed:
        :return: pseudo prime
        """
        p = Prime.seed_primes[seed % len(Prime.seed_primes)]
        return (p * x + seed) % n

    def find_factor(self, n, seed=1):
        """
        find one of factor of n
        this function is based to Pollard's rho algorithm

        see also
            algorithm: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
            implementation: https://qiita.com/gushwell/items/561afde2e00bf3380c98

        :param n:
        :param seed:
        :return: factor
        """
        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

prime=Prime()
N=int(input())
choice=0
x=0
ans=0
dic=prime.find_factors(N)
memo={}
for key in dic.keys():
  memo[key]=1
while True:
  v=float('inf')
  for key in dic.keys():
    if memo[key]>dic[key]:continue
    if v>key**(memo[key]):
      v=key**(memo[key])
      choice=key
      x=memo[key]
  if v==float('inf'):
    break
  dic[choice]-=x
  memo[choice]+=1
  ans+=1
print(ans)

Submission status: Time Limit Exceeded

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 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())
z = 2
count = 0
if is_prime(n): exit(print(1))
while True:
    if n%z==0:
        n /= z
        count += 1
    while True:
        z += 1
        t = math.sqrt(z)
        t = prime_factorize(z)
        if is_prime(z) or sum(t)==t[0]*len(t): break
    if n < z: break
print(count)

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())
l = factorization(n)
dic = []
for i in range(len(l)):
    tmp = l[i][0]
    dic.append(tmp)
    while n >= tmp:
        tmp *= l[i][0]
        if n < tmp:
            break
        dic.append(tmp)
dic.sort()
cnt = 0
while n != 1:
    flag = True
    for i in range(len(dic)):
        if n%dic[i] == 0:
            n //= dic[i]
            cnt += 1
            dic.pop(i)
            flag = False
            break
    if flag:
        break
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n = II()
    ans = 0
    d = defaultdict(int)
    d[1] = 1 
    for i in range(2, int(sqrt(n - 1)) + 2):
        x = i
        while 1:
            if n % x == 0 and d[x] != 1:
                ans += 1
                n //= x
                d[x] = 1
            else:
                break
            x *= i
        l = i
        for i in range(i + 1):
            d[l*i] = 1
    if d[n]:
        print(ans)
    else:
        print(ans + 1)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n = int(input())
if n <= 1:
    print(0)
else:
    prime = True
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            prime = False
            break
    if prime:
        print(1)
    else:
        store = defaultdict(int)
        num = 2
        while num <= n:
            if n % num == 0:
                store[num] += 1
                n = n // num
            else:
                num += 1
        count = 0
        for v in store.values():
            k = v
            for i in range(1, v+1):
                if k >= i:
                    k -= i
                    count += 1
                else:
                    break
        print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def is_prime(a):
  if a == 1:
    return False
  
  for i in range(2, 1+int(a**0.5)):
    if a % i == 0:
      return False
  return True

n = int(input())

ans = 0
z = 2
while True:
  if z > n:
    break
  if is_prime(n):
    ans += 1
    break
    
  if n % z != 0:
    z += 1
    continue
  for p in range(2, z+1):
    if not is_prime(p):
      continue
    tmp = np.log(z)/np.log(p)
    if tmp > 0 and tmp == int(tmp):
      n = n/z
      ans += 1
      z += 1
      break
  else:
    z += 1

print(ans)