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


n = int(input())
already = []
primes = []

def is_prime(n):
    for p in range(2, n):
        if n % p == 0:
            return False
    return True

def is_dev(num):
    for p in range(2, num):
        if is_prime(p):
            if num % p == 0:
                return True  
    return False

test = []
for p in range(2, n):
    if is_prime(p):
        primes.append(p)
for prime in primes:
    tmp = 1
    
    while True:
        tmp *= prime
        if tmp > n:
            break
        test.append(tmp)

test.sort()

for item in test:
    if n % item == 0:
        already.append(item)
        n = n // item

print(len(already))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

up = int((n//2)**.5)
mp = set(p for p in range(3, up + 1, 2))
mp.add(2)
for i in range(3, up+1, 2):
    #if mp[i] == False:
    if i not in mp:
        continue
    j = 2
    while i*j < up:
        if i*j in mp:
            mp.remove(i*j)
        j += 1
ps = mp

# -----------------------------
mp = {p:1 for p in ps}

ops = 0
while n != 1:
    for p in ps:
        if p > n:
            break

        e = mp[p]
        z = p**e
        if n % p == 0:
            if n % z == 0:
                #print('new ops')
                #print(p, e, n//z)
                n //= z
                mp[p] += 1
                ops += 1
            else:
                #print('shadow ops')
                while n % p == 0:
                    n //= p
                # no ops

print(ops)

Submission status: Time Limit Exceeded

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

nums = [i for i in range(2,n//2+1)]
nums.append(n)

ans = 0
x = 0

if n != 1:
    while x == 0:
        for index, i in enumerate(nums):
            if 0 == n % i:
                ans += 1
                nums.remove(i)
                n = n / i
                break
        if len(nums) == index+1:
            x = 1


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
a = int(input())
count = 0
first = 2
def num_div(num):
  a = 2
  while num!=1:
    if num % a == 0:
      num /= a
      while True:
        if num % a ==0:
          num /= a
        elif num == 1:
          return 0
        else:
          return -1
    a += 1

#print(num_div(2))
#sys.exit(0)

while a!=1:
  #素因数は一つ？
  if a % first == 0:
    if num_div(first) == -1:
      first += 1
      continue
    else:
      a /= first
      count += 1
  first += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import math

def factorization(n):
    arr = []
    temp = n

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

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

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

    return arr


N = int(input())
seen = set()
count = 0

while N > 1:
	divisor = factorization(N)

	for x in divisor:
		if x not in seen and N > 1:
			N = N / x
			count += 1
			seen.add(x)
			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())
ans = 0
B = N
for z in range(2, int(N**(1/2))+1):
    if B == 1:
        break
    if B < z:
        break
    cnt = len(factorization(z))
    if cnt == 1 and B % z == 0:
        B = B // z
        #print(z)
        ans += 1

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
# N = (2 ** 16) * (3 ** 16)
ans = 0
t = []
primeList = [2]
maxNumber = 2 * 10 ** 5
for x in range(3, maxNumber):
    for y in primeList:
        if x % y == 0:
            break
    else:
        primeList.append(x)  # 割り切れるものがなければリストに追加

for i in primeList:
    for x in range(1, 40):
        y = i ** x
        if N // y == N / y:
            ans += 1
            N = N // y
        else:
            break

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

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]]
 
 
N = int(input())
 
num_list = set()
 
hoge = primes(25000000)
 
for i in range(1, 10):
    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:
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:
def prime(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

N = int(input())
a = prime(N)
a.sort()
import copy
b = copy.copy(a)
b = list(set(b))
b.sort()
m = 0
def cnt(c_, used, ans,now):
    m = ans
    for i in range(len(c_)):
        for j in range(1,a.count(b[i])+1-c_[i]):
            if now*b[i]**j > N:
                break
            if used.count(b[i]**j) != 0:
                continue
            c = copy.copy(c_)
            c[i] += j
            m = max(m, cnt(c, used+[b[i]**j], ans+1, now*b[i]**j))
    return m

m = cnt([0]*len(b), [], 0, 1)
print(m)

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]

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]]
 
 
N = int(input())
 
num_list = set()
 
hoge = primes(30000000)
 
for i in range(1, 10):
    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
N = int(input())
H = N
count = 0
coun = 0
flag = False
lis = list()
for i in range(2,int(math.sqrt(N))+1):
  if N % i == 0:
    flag = True
    j = max(i,N//i)
    k = min(i,N//1)
    break
if flag == True:
  for i in range(k,j+1):
    if N%i == 0:
      count = 0
      while N%i == 0:
        N = N//i
        count += 1
      lis.append(count)
  M = len(lis)
  for i in range(M):
    su = 1
    for j in range(lis[i]):
      if lis[i] - su >= 0:
        lis[i] -= su
        su += 1
        coun += 1
if flag == True or H == 1:
  print(coun)
else:
  print(1)

Submission status: Time Limit Exceeded

Solution code:
import random

def is_prime(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

n = int(input())
count = 0
zlist = []
N = n

while True:
    for i in range(n):
        for e in range(1, 10):
            #print('i=',i,'e=', e)
            if is_prime(i) and N % (i**e) == 0 and i**e not in zlist:
                z = i ** e
                zlist.append(i**e)
                N /= z     
                count += 1
                #print('i=', i, 'n=', N, 'z=', z, 'zlist=',zlist,'count=', count)
            if N == 1:
                print(count)
                exit()

    if i == n - 1:
        break

print(count)

Submission status: Time Limit Exceeded

Solution code:
pn=[2];A=80000
for L in range(3,A):
    chk=True
    for L2 in pn:
        if L%L2 == 0:chk=False
    if chk==True:pn.append(L)
      
ln=[]
for i in range(len(pn)):
  for j in range(8):
    ln.append(pn[i]**j)
mn=sorted(list(set(ln)))

n=int(input())

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

count=0
for k in range(1,len(mn)):
  if n%mn[k]==0:
    n=n//mn[k]
    count+=1
    if n==1:
      break
if count==0:
  print(1)
  exit()
print(count)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
n=int(input())
i=0
l=list()
n2=n
while True:
        i=i+1
        n1=n2/(2**i)
        if n1-math.floor(n1)>0:
            l.append(i-1)
            break
        n2=n1
for p in range (3,6*(10**6)-1,2): 
    i=0
    while True:
        i=i+1
        n1=n2/(p**i)
        if n1-math.floor(n1)>0:
            l.append(i-1)
            while True:
                if n2/p-math.floor(n2/p)>0:
                    break
                else:
                    n2=n2/p
            break
        n2=n1
    if n2<p:
        break
if n2>p:
    print(1)
else:
    print(sum(l))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
total=[]
#n以下の素数の組を探す
p =[]
if n>=2:
  for i in range(2,n):
    q =1
    for j in range(2,i):
      if i % j ==0:
        q*=0
      else:
        q *=1 
    if q ==1:
        p.append(i)
#print(p)

if n==1:
  total =[0]
else:
  for i in p:
    cnt =0
    while True:
      if n % i ==0:
        cnt +=1
        n /= 2
      else:
        break
    #print(cnt)
    t =0
    s=1
    while True:
      if cnt >= s:
        t +=1
        cnt -= s
        s +=1
      else:
        break
    total.append(t)
print(sum(total))

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
primelist=[2]

num = int(N/2)+1
for i in range(3,num,2):
    if N % i == 0:
        for j in primelist:
            if i % j == 0:
#                 k = 0
                break
        else:
            primelist.append(i)
# print(primelist)
count = 0
for j in primelist:    
    i = j
    while N % i == 0:
        N = N / i
        i *= j
        count += 1
if count == 0 and N != 1:
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:

 
n=int(input())
a=[]
i=1
while n!=1:
    i+=1
    b=0
    c=0
    while n%i==0:
        n=n//i
        b+=1
    while not c*(c+1)<=2*b<(c+1)*(c+2):
        c+=1
    a.append(c)
print(sum(a))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())


P = []


def isPrime(n):
    if n == 0 or n == 1:
        return False

    i = 2
    while i ** 2 <= n:
        if n % i == 0:
            return False
        i += 1
    else:
        P.append(n)
        return True


def isAbleDiv(a, prime):
    for i in range(1, a):
        x = prime ** i
        if a < x:
            return False

        if a % prime == 0 and a == x:
            return True


if isPrime(N):
    print(1)
    exit()

ans = 0
for z in range(2, N+1):
    if z > N:
        break

    if isPrime(z):
        if N % z == 0:
            ans += 1
            N //= z
            continue

    for p in P:
        if isAbleDiv(z, p):
            if N % z == 0:
                ans += 1
                N //= z
                break


print(ans)

Submission status: Time Limit Exceeded

Solution code:


lsp = [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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
N, count = eval(input()), 0
x = N % 2
for i in range(2, N):
    if i in lsp:
        for f in range(1, N):
            d = i**f
            if N % d == 0:
                count += 1
                N = N // d
print(count)

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
H = N
count = 0
coun = 0
flag = False
lis = list()
for i in range(2,int(math.sqrt(N))+1):
  if N % i == 0:
    flag = True
    j = max(i,N//i)
    break
if flag == True:
  for i in range(2,j+1):
    if N%i == 0:
      count = 0
      while N%i == 0:
        N = N//i
        count += 1
      lis.append(count)
  M = len(lis)
  for i in range(M):
    su = 1
    for j in range(lis[i]):
      if lis[i] - su >= 0:
        lis[i] -= su
        su += 1
        coun += 1
if flag == True or H == 1:
  print(coun)
else:
  print(1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

cnt = 0
start = 2
z = 1

#nの素数判定
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 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
    
if is_prime(N) == False:
    while N != 1:
        for i in range(start, N+1):
            prime = prime_factorize(i)
            if N % i == 0 and prime[0] == prime[-1]:
                z = i
                start = i+1
                cnt += 1
                break
        # cnt += 1
        N = N // z
        # print(z, N, start)
        if z >= N:
            break
    print(cnt)

# 素数の時は必ず1
else:
    print(1)

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(math.floor(math.sqrt(N)),A)

A_len=len(A)
chk_N = N
for i in range(A_len):
    if chk_N % A[i] == 0:
        chk_N =0
        break

if chk_N != 0:
    A.append(N)

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:
from decimal import Decimal
N = Decimal(int(input()))
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]

divisors = make_divisors(N)[1:]
count = 0
for i in divisors:
  if N<i:
    break
  if N%i == 0:
    N = N/Decimal(i)
    count +=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
"""AtCoder Beginner Contest 169: D - Div Game
https://atcoder.jp/contests/abc169/tasks/abc169_d
"""

__author__ = 'bugttle <bugttle@gmail.com>'

import math

cache = {}
answer = 0

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_list(n):
    prime_list = [2]
    for L in range(3, n+1, 2):
        if all(L % L2 != 0 for L2 in prime_list):
            prime_list.append(L)
    return prime_list

def calc_p_e(z):
    for p in prime_list(z):
        # print("  z:{} p:{}".format(z, p))
        e = math.log(z, p)
        # print("  e:{}".format(e))
        if int(e) == e:
            return [p, e]
    return [None, None]

def calc(n):
    global answer
    # print("N={}".format(n))

    for z in range(2, n+1):
        # print("z={}".format(z))
        if z in cache:
            # print("     1:{}".format(z))
            continue
        if n % z != 0:
            # print("     2:{}".format(z))
            continue
        # print(z)
        p, e = calc_p_e(z)
        if p is None:
            continue
        answer += 1
        # print('z = {}(={}**{}) => N={}'.format(z, p, e, int(n / z)))
        cache[z] = True
        return calc(int(n/z))
    # answer += 1
    return n

    # for p in prime_list(n):
    #     print(p)
    #     max_e = math.log(n, p)
    #     for e in range(1, int(max_e+1)):
    #         z = p ** e
    #         if z not in cache and n % z == 0:
    #             print('z = {}(={}**{}) => N={}'.format(z, p, e, int(n / z)))
    #             cache[z] = True
    #             return calc(int(n / z))
    return n

def main():
    N = int(input())
    # N = 24

    if N < 2:
        print(0)
    elif is_prime(N):
        print(1)
    else:
        calc(N)
        print(answer)

    # print(is_prime(1000000007))
    # if N < 2:
    #     print(0)
    # else:
    #     print(calc(N))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
pn=[2];A=100000
for L in range(3,A):
    chk=True
    for L2 in pn:
        if L%L2 == 0:chk=False
    if chk==True:pn.append(L)
      
ln=[]
for i in range(len(pn)):
  for j in range(8):
    ln.append(pn[i]**j)
mn=sorted(list(set(ln)))

n=int(input())

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

count=0
for k in range(1,len(mn)):
  if n%mn[k]==0:
    n=n//mn[k]
    count+=1
    if n==1:
      break
if count==0:
  print(1)
  exit()
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys

n=int(input())
a=[]
i=1
while n!=1:
    i+=1
    b=0
    c=0
    while n%i==0:
        n=n//i
        b+=1
    while not c*(c+1)<=2*b<(c+1)*(c+2):
        c+=1
    a.append(c)
print(sum(a))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from math import sqrt
n = int(input())
cnt = defaultdict(int)
ans = 0
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

def calc_ans(cnt):
    ans = 0
    for v in cnt.values():
        i = 1
        cnt = 0
        while cnt + i <= v:
            cnt += i
            i += 1
        ans += i - 1
    return ans
if judge_prime(n):
    print(ans + 1)
    exit()
for i in range(2, n):
    if judge_prime(i):
        j = 0
        while n % (i ** (j + 1)) == 0:
            j += 1
        n //= i ** j
        
        cnt[i] = j
        if n == 1:
            break
print(calc_ans(cnt))

Submission status: Time Limit Exceeded

Solution code:
from math import floor, sqrt


def func(x):
    return floor((sqrt(1 + 8 * x) - 1) / 2)


N = int(input())
limit = floor(sqrt(N))

primes = [2]

count = 0
flag = True
p = 2
while 1:
    #print(p,N)
    isprime = True
    if N == 1:
        break
    if p > sqrt(N):
        count += 1
        break
    if p > 3:
        for i in primes:
            if i >= sqrt(p):
                break
            if p % i == 0:
                isprime = False
                break
        if not isprime:
            p += 2
            continue
        primes.append(p)
    a = 0
    while N % p == 0:
        #print("while",p, a)
        a += 1
        N = N // p
    count += func(a)
    if p == 2:
        p = 3
    else:
        p += 2
print(count)

Submission status: Time Limit Exceeded

Solution code:

def prime(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

N, count = eval(input()), 0
x = N % 2
for i in range(2, N):
    if prime(i):
        for f in range(1, N):
            d = i**f
            if N % d == 0:
                count += 1
                N = N // d
print(count)

Submission status: Time Limit Exceeded

Solution code:
import random

def is_prime(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

n = int(input())
count = 0
zlist = []
N = n

while True:
    for i in range(n):
        for e in range(1, 10):
            #print('i=',i,'e=', e)
            if is_prime(i) and N % (i**e) == 0 and i**e not in zlist:
                z = i ** e
                zlist.append(i**e)
                N /= z     
                count += 1
                #print('i=', i, 'n=', N, 'z=', z, 'zlist=',zlist,'count=', count)

    if i == n - 1:
        break

print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

repeat = [1]*9
for i in range(1,10):
    repeat[i-1] = i*(i+1)//2

d = 1
ans = 0
judge = False
while n != 1:
    d += 1
    count = 0
    if n%d == 0:
        judge = True
        j = -1
    while n%d == 0:
        n = n//d
        count += 1
    while judge:
        j += 1
        if count < repeat[j]:
            ans += j
            judge = False

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
H = N
count = 0
coun = 0
flag = False
lis = list()
for i in range(2,int(math.sqrt(N))+1):
  if N % i == 0:
    flag = True
    break
if flag == True:
  for i in range(2,int(math.sqrt(N))+50000000):
    if N%i == 0:
      count = 0
      while N%i == 0:
        N = N//i
        count += 1
      lis.append(count)
  M = len(lis)
  for i in range(M):
    su = 1
    for j in range(lis[i]):
      if lis[i] - su >= 0:
        lis[i] -= su
        su += 1
        coun += 1
if flag == True or H == 1:
  print(coun)
else:
  print(1)

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 primes(n):
    ps = {}
    x = n
    for i in range(2, n):
        if x == 1:
            break
        cnt = 0
        while x % i == 0:
            x = x // i
            cnt += 1
        if cnt > 0:
            ps[i] = cnt
        # print(n,i,cnt)

    return ps


def main():
    import decimal

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

    if is_prime(n):
        print(1)
        exit()

    ps = primes(n)
    # print(ps)
    ans = sum(int((-1 + (1 + 8 * v) ** 0.5) / 2) for v in ps.values())

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
i=2
n=0
素因数=0
while True:
    if N%i==0:
        N/=i
        素因数+=1
    else:
        j=1
        while True:
            if 素因数-j>=0:
                n+=1
                素因数-=j
                j+=1
            else:
                break
        if N==1:
            break
        素因数=0
        if i==2:
            i+=1
        else:
            i+=2
print(n)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import decimal
import math
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 iskaijo(n):
    i=1
    while True:
        if(n==1):
            break
        if(n%i==0):
            n=n/i
            i=i+1
        else:
            i=-1
            break
    return i

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


ng=False
ans=0
List =factorization(N)
#c=collections.Counter(List)
for i in range(len(List)):
    test = List[i][1]
    i=1
    while True:
        test=test-i
        i=i+1
        ans=ans+1
        if(test == 0):
            break
        # elif(test < 0 ):
        #     ng = True
        #     break

if N!=1:
    print(ans)
else:
    print(0)

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 primes(n):
    ps = {}
    x = n
    for i in range(2, n):
        if x == 1:
            break
        cnt = 0
        while x % i == 0:
            x = x // i
            cnt += 1
        if cnt > 0:
            ps[i] = cnt
        # print(n,i,cnt)

    return ps


def main():
    import decimal

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

    if is_prime(n):
        print(1)
        exit()

    ps = primes(n)
    # print(ps)
    ans = sum(int(decimal.Decimal((-1 + (1 + 8 * v) ** 0.5) / 2)) for v in ps.values())

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal
N = Decimal(int(input()))
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]

divisors = make_divisors(N)[1:]
count = 0
for i in divisors:
  if N%i == 0:
    N = N/Decimal(i)
    count +=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
count = 0
while n > 1:
    for z in range(2, n+1):
        if n % z == 0:
            n = n / z
            count += 1
    break

print(count)

Submission status: Time Limit Exceeded

Solution code:
def check(i, p):
  if i == p:
    return True
  elif i % p == 0:
    return check(i//p, p)
  else:
    return False


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


N = int(input())
primes = []
cnt = 0
for i in range(2, N+1):
  if N % i != 0:
    continue
  elif N < i:
    break
  if is_prime(i):
    N /= i
    cnt += 1
    primes.append(i)
    continue

  for p in primes:
    if check(i, p):
      N /= i
      cnt += 1
      break
print(cnt)

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(r+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())
L = N
if L == 1:
    print(0)
else:
    num = 0
    if L > 100000000:
        limit = L#int(math.sqrt(L)) + 2
    else:
        limit = L
    for i in range(2, limit):
        if N % i == 0:
            N = N / i
            num = num + 1

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