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: Wrong Answer

Solution code:
def prime_factorize_dict(n):
    d = dict()
    while not n & 1:
        d[2] = d.get(2, 0) + 1
        n >>= 1
    f = 3
    while f * f <= n:
        if not n % f:
            d[f] = d.get(f, 0) + 1
            n //= f
        else:
            f += 2
    if n != 1:
        d[n] = d.get(n, 0) + 1
    return d

N = int(input())
l = list(prime_factorize_dict(N).values())
n = len(l)
total = sum(l)
ans = 0
i = 1
while True:
    ans += min(total // i, n)
    total -= min(total // i, n) * i
    if not total // i:
        break
    i += 1
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

##### 進数の変換 #####
# bin_str = bin(i)[2:]
# oct_str = oct(i)[2:]
# hex_str = hex(i)[2:]

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()

	tmp = factorize(N)
	ans = 0

	for i,val in enumerate(tmp):
		sosuu,kai = val
		kai -= 1
		ans += 1

		tmptmp = kai // 2
		ans += tmptmp

	print(ans)



def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct



#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# 2分検索のリバース
def bisect_left_reverse(a, x):
    if a[0] <= x:
        return 0
    if x < a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] <= x:
            ok = mid
        else:
            ng = mid
    return ok

def bisect_right_reverse(a, x):
    if a[0] < x:
        return 0
    if x <= a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# 2分検索
# 存在しない場合: None 存在する場合: その値
def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid -1
        else:
            low = mid + 1
    return None

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# N 個のボールを K グループに分ける場合のパターン数
def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

U = 10 ** 6 + 10
is_prime = np.zeros(U, np.bool)
is_prime[2] = 1
is_prime[3::2] = 1
for p in range(3, U, 2):
    if p*p > U:
        break
    if is_prime[p]:
        is_prime[p*p::p+p] = 0

M = 10 ** 3
small_primes = np.where(is_prime[:M])[0].tolist()

N = ir()
answer = 0
used = set()
for p in small_primes:
    d = p
    while N%d == 0:
        answer += 1
        N //= d
        used.add(d)
        d *= p

if N > 1 and N not in used:
    answer += 1

print(answer)

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999
MOD = 10**9+7

n = int(input())

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

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

    if len(arr) == 0:
        arr.append((n, 1))
    return arr

fac = factorization(n)
log(fac)

ans = 0
for p,e in fac:
    x = e
    for i in range(1, 99999999):
        if x >= i:
            x -= i
            ans += 1
        else:
            break

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
li=[0]*(10**6+1)
flag=False
for i in range(2,int(N**0.5)+1):
  while N%i==0:
    flag=True
    N/=i
    li[i]+=1
if flag==False:
  print(1)
  exit()
ans=0
for count in li:
  use=1
  while count-use>=0:
    ans+=1
    count-=use
    use+=1
print(ans)

Submission status: Wrong Answer

Solution code:
def sieve(x):
    """
    Sieve of Eratosthenes
    :param x: max value
    :return: list of bool
    """

    is_prime = [True] * (x + 1)
    is_prime[0] = is_prime[1] = False

    for i in range(2, x + 1):
        if is_prime[i]:
            for j in range(i * 2, x + 1, i):
                is_prime[j] = False

    return is_prime


n = int(input())

is_prime = sieve(10 ** 6)
primes = [i for i, e in enumerate(is_prime) if e]

ans = 0
for e in primes:
    div = e
    while n % div == 0:
        n //= div
        ans += 1
        div *= e


def f(x):
    if x < 2:
        return False

    for e in primes:
        if x % e == 0:
            return False

    return True

ans += f(n)

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
_n=n
ans=0
for i in range(2,1000002):
    if n%i==0:
        ans+=1
        n/=i
        # print(i,ans)
    if n==1:
        break

if n==_n:
    ans+=1
if _n==1:
    ans-=1
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right

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

N = int(input())
L = prime_factorize(N)
A = [i for i in range(1,51)]
for i in range(49):
    A[i+1] += A[i]

ans = 0
for l in L:
    ans += bisect_right(A,l)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
import numpy as np
from heapq import heapify, heappop, heappush
import copy
from math import gcd, ceil
from collections import deque
# queueとして使う場合 push, popleftを使う
from bisect import bisect_left, bisect_right
# bisect_left: 配列の順序関係が崩れない条件で挿入することができる一番左の点
# bisect_right: 配列の順序関係が崩れない条件で挿入することができる一番右の点
# A = [1, 1, 1, 2, 2, 2, 4]
# print(bisect_left(A, 2))  # 3
# print(bisect_right(A, 2))  # 6
# print(bisect_left(A, 3))  # 6
# print(bisect_right(A, 3))  # 6


def is_prime(N):
    """Nを2~int(N**0.5)までで割る"""
    for i in range(2, int(N**0.5)+1):
        if N % i == 0:
            return False
    return True


def main():
    N = int(input())
    if N == 1:
        print(0)
        sys.exit()
    if is_prime(N):
        print(1)
        sys.exit()
    num = ceil(N ** 0.5)
    count = 0
    for i in range(2, num):
        if N % i == 0:
            N = N // i
            count += 1
    print(count)
    




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
_n=n
ans=0
for i in range(2,1000002):
    if n%i==0:
        ans+=1
        n/=i
        # print(i,ans)
    if n==1:
        break

if n==_n:
    ans+=1
if n==1:
    ans-=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
import bisect

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

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

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

        return arr
    
    c = factorization(N)
    
    can = []
    for i in range(1,50):
        can.append((i*(i+1))//2)

    ans = 0
    for _,cnt in c:
        ind = bisect.bisect_right(can,cnt)
        ans += ind
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

dat = factorization(n)
#print(dat)

buf = []

for a,b in dat:
    for j in range(b):
        buf.append(a)
#print(buf)

used = dict()
#print(used)
cur = 1
res = 0
for i in range(len(buf)):

    if buf[i] == 1:
        continue
    #print("i", i, "buf", buf[i])
    cur = cur * buf[i]
    #print("cur", cur)
    if cur not in used:
        #print("not use", cur)
        used[cur] = True
        #print(used)
        res += 1
        cur = 1

#print(used)
print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())
p = 2
ans = 0
while n > 1:
    if p > 10 ** 6:
        ans = 1
        break
    e = 1
    while n % (p ** e) == 0:
        n = n // (p ** e)
        e += 1
        ans += 1
    while n % p == 0:
        n = n // p
    p += 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
if n==1:
  print(0)
  exit()
a=0
f=0
i=1
while n!=1 and f==0:
  i=i+1
  if i*i>=n:
    f=1
    continue
  if n%i==0:
    n=n//i
    a=a+1
print(a+1)

Submission status: Wrong Answer

Solution code:
n=int(input())
_n=n
ans=0
for i in range(2,1000002):
    if n%i==0:
        ans+=1
        n/=i
        # print(i,ans)
    if n==1:
        break

if n==_n:
    ans+=1
print(ans)

Submission status: Wrong Answer

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

N=int(input())
arr=factorization(N)
ans=0
for i in range(len(arr)):
    cnt=1
    while arr[i][1]>0:
        if arr[i][1]>=cnt:
            arr[i][1]-=cnt
            ans+=1
            cnt+=1
        else:
            break
print(ans)

Submission status: Wrong Answer

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

    return arr


n = int(input())
factors = factorization(n)

ans = 0
for factor, count in factors:
    use = 1
    while count >= use:
        count -= 1
        use += 1
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
sosu = [1 for _ in range(10**6+5)]
sosu[0] = 0
sosu[1] = 0
for i in range(2, len(sosu)):
    if sosu[i]:
        j = i+i
        while j < len(sosu):
            sosu[j] = 0
            j += i

z_list = [0 for _ in range(10**6+5)]
for i in range(2, len(sosu)):
    if sosu[i]:
        j = i
        while j < len(sosu):
            z_list[j] = 1
            j *= i

# print(z_list[:20])

n = int(input())
o_n = n
cnt = 0
for i in range(len(z_list)):
    if z_list[i]:
        if n % i == 0:
            cnt += 1
            n //= i

if cnt == 0:
    i = 2
    cnt = 1
    if o_n == 1:
        cnt = 0
    while i*i <= o_n:
        if o_n % i == 0:
            cnt = 0
            break
        i += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
factors = []
while n%2 == 0:
    n //= 2
    factors.append(2)

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

fd = set()
rem = 1
c = 0
for f in factors:
    f = f*rem
    if not f in fd:
        fd.add(f)
        c += 1
        rem = 1
    else:
        rem *= f
print(c)

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999
MOD = 10**9+7

n = int(input())

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

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

    if len(arr) == 0:
        arr.append((n, 1))
    return arr

fac = factorization(n)
# log(fac)

ans = 0
for p,e in fac:
    x = e
    for i in range(1, 999):
        if x >= i:
            x -= i
            ans += 1

print(ans)

Submission status: Wrong Answer

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

def is_prime(n):
    if n == 2: return True
    if n < 2 or n%2 == 0: return False
    m = 3
    while m*m <= n:
        if n%m == 0: return False
        m += 2
    return True
if is_prime(N):
    print(1)
    exit()

z = 2
ans = 0
while z <= N:
    if N%z==0:
        N //= z
        ans += 1
    z += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()

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

from collections import Counter
import bisect

c = Counter(res)

tt = []
i = 1
for _ in range(40):
    i *= 2
    tt.append(i-1)

ans = 0
for v in c.values():
    ans += bisect.bisect_right(tt,v)

print(ans)

Submission status: Wrong Answer

Solution code:
import collections
import bisect

n = 10 ** 4
fl = [1] * n
fl[0] = 0
fl[1] = 0
lprime = []
for i in range(n):
    if fl[i] == 1:
        lprime.append(i)
        ti = i * 2
        while ti < n:
            fl[ti] = 0
            ti += i


def prime_factorize(n):
    global lprime
    a = []
    for p in lprime:
        if p * p > n:
            break
        while n % p == 0:
            a.append(p)
            n //= p
    if n != 1:
        a.append(n)
    return a


N = int(input())
tres = prime_factorize(N)
ctres = collections.Counter(tres)
sl = [1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66]
res = 0
for c in ctres.values():
    res += bisect.bisect_right(sl, c)
print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

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

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

    return arr

arr = factorization(n)

ans = 0
for (i,j) in arr:
    for k in range(1,100):
        j -= k
        if(j<0):
            break
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect as bi
def fact(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=[i*(i+1)//2 for i in range(1,100)]
c=0
for t in fact(n):
  c+=bi.bisect_right(l,t[1])
print(c)

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = 0
n = int(N**0.5)
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
for i in range(2,n):
    A = factorization(i)
    if len(A) == 1:
        ans = 1
        N = N // i
    if N == 1:
        break
if N != 1:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

#nの約数列挙
def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    ass.sort()
    return ass #sortされていない

D = divisor(N)
ans = 0
for d in D:
    if d == 1:
        continue
    if N%d == 0:
        N //= d
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def prime_factorize(n):
    ret = defaultdict(int)
    while n % 2 == 0:
        n //= 2
        ret[2] += 1
    d = 3
    while d * d <= n:
        while n % d == 0:
            n //= d
            ret[d] += 1
        d += 2
    if n > 1:
        ret[n] += 1
    return dict(ret)


n = int(input())
pf = prime_factorize(n)
ans = 0
for c in pf.values():
    ans += int((c * 2 - 1) ** 0.5)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import math
N = int(input())
ps = defaultdict(int)
for i in range(2, int(math.sqrt(N))+1):
    while N % i == 0:  
        ps[i] += 1
        N //= i
    i += 1
if N > 1:
    ps[N] += 1
ans = 0
for p in ps:
    k = 1
    while ps[p] >= k:
        ans += 1
        ps[p] -= 1
        k += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

"""nを素因数分解"""
"""2以上の整数n => [(素因数, 指数), ...]の2次元リスト"""

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(n**0.5)+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

li = factorization(N)
ans = 0
for i in li:
    k = i[1]
    loop = 1
    while True:
        k -= loop
        if k>=0:
            ans += 1
        else:
            break
        loop += 1
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n, = map(int,input().split())

x = [0,1,3,6,10,15,21,28,36,45,55,66]

from bisect import bisect_left
ans = 0
N = 10**6
for i in range(2,N):
    r = 0
    while n%i==0:
        n//=i
        r += 1
    
    if r>0:
        ans += bisect_left(x,r)        
        
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, defaultdict, Counter
from itertools import accumulate, product, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush
from math import ceil, floor, sqrt, gcd, inf
from copy import deepcopy
import numpy as np
import scipy as sp

def trial_division(n):
    a = []
    f = 2
    while n > 1:
        if n % f == 0:
            a.append(f)
            n /= f
        else:
            f += 1
    return a

INF = inf
MOD = 1000000007

n = int(input())

tmp = 0
res = 0

cnt = Counter(trial_division(n))
for i in cnt.values():
    res += floor((-1 + sqrt(1 + 8 * i)) / 2)

print(res)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
nums = []
exps = {}
import math
p = 2
while True:
  if N % p == 0:
    nums.append(p)
    e = 0
    z = p
    while True:
      if N % z == 0:
        z *= p
        e += 1
      else:
        exps[p] = e
        break
#    print(p, exps[p])
    N /= p ** exps[p]
    if N <= 1:
      break
  if p == 2:
    p  = 3
  else:
    p += 2
if not len(nums):
  exps[N] = 1
  nums.append(N)

import numpy as np
prod = 0
for p in nums:
  num = 0
  cum = 0
  while True:
    cum += num
    num += 1
    if exps[p] - cum < num:
      break
      
#  print(p, exps[p], num - 1)
  prod += num - 1
print(prod)

Submission status: Time Limit Exceeded

Solution code:
#D - Div Game
N = int(input())

def Prime_factorize(n):
    cnt = 0
    A = []
    #2の倍数で割っていく
    z = 2
    while n%z==0 and (n>=z):
        cnt += 1
        n //= z
        
        A.append(z)
        #割るたびに2倍
        z *= 2
    #割る始めの数をfとして保持
    f = 3
    z = 3
    #sqrt(n)以内に全ての素因数は含まれる
    while f*2 <= N:
        if n%z == 0:
            cnt += 1
            n //= z
            A.append(z)
            
            #割るたびにf倍
            z = z*f
        #fで割り切れなかったら(f+2)してf_divもリセット
        else:
            f += 2
            z = f
    
    #残ったnが以前に選んだもので割り切れないとき
    if n != 1 and all((n%i != 0 for i in A)):
        A.append(z)
        cnt += 1
    #素数のとき
    if cnt == 0:
        cnt = 1
    return cnt
if N == 1:
    ans = 0
else:
    ans = Prime_factorize(N)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#D - Div Game
N = int(input())

def Prime_factorize(n):
    cnt = 0
    A = []
    #2の倍数で割っていく
    z = 2
    while n%z==0 and (n>=z):
        cnt += 1
        n //= z
        
        A.append(z)
        #割るたびに2倍
        z *= 2
    #割る始めの数をfとして保持
    f = 3
    z = 3
    #sqrt(n)以内に全ての素因数は含まれる
    while f*2 <= N:
        if n%z == 0:
            cnt += 1
            n //= z
            A.append(z)
            
            #割るたびにf倍
            z = z*f
        #fで割り切れなかったら(f+2)してf_divもリセット
        else:
            f += 2
            z = f
    
    #残ったnが以前に選んだもので割り切れないとき
    if n != 1 and all((n%i != 0 for i in A)):
        A.append(z)
        cnt += 1
    #素数のとき
    if cnt == 0:
        cnt = 1
    return cnt
if N == 1:
    ans = 0
else:
    ans = Prime_factorize(N)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import bisect

line=[i*(i+1)//2 for i in range(10**7+1)]

N=int(input())

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

do=[0 for i in range(10**6+1)]

for i in range(2,int(N**0.5)+1):
    while N%i==0:
        N/=i
        do[i]+=1

ans=0
judge=True

for _,item in enumerate(do):
    index=(bisect.bisect_right(line,item))-1
    ans+=index
    if index!=0:
        judge=False

print(ans+1 if judge else ans)

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt

n = int(input())

i = 2
j = 0
c = []

while n != 1:
    
    if n%i == 0:
        j += 1
        n = n/i
        if n == 1:
            c.append(j)
    else:
        if j != 0:
            c.append(j)
        i += 1
        j = 0
        
d = 0        
if c == []:
    print(d)
else:
    for k in c:
        d += int((sqrt(1 + 8*k)-1)/2)
    print(d)

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
ans = [int(i) for i in range(n+1)]
ans[1] = 0
i = 2
sosu = []
while i <= int(math.sqrt(n)):
    if ans[i] != 0:
        j = i
        sosu.append(i)
        for j in range(j,(n//j)+1):
            ans[i*j] = 0
    i += 1
f = []
tmp = n
for i in range(len(sosu)):
    if tmp%sosu[i]==0:
        cnt = 0
        while tmp%sosu[i]==0:
            cnt += 1
            tmp = tmp//sosu[i]
        f.append([sosu[i],cnt])
if tmp != 1:
    f.append([tmp,1])
count = 0
for i in range(len(f)):
    j = 1
    while j <= f[i][1]:
        n = n//(f[i][0]*j)
        f[i][1] -= j
        count += 1
        j += 1
#print(f)
print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
if N == 1:
    print(0)
    exit()
primes = []
i = 2
tmp = N
flag = False
while i**2 <= tmp:
    if N % i == 0:
        flag = True
        count = 0
        while N % i == 0:
            N //= i
            count += 1
        primes.append((i, count))
    i += 1

if (not N == 1) and flag:
    i = 2
    tmp = N
    while N > 1:
        if N % i == 0:
            count = 0
            while N % i == 0:
                N //= i
                count += 1
            primes.append((i, count))
        i += 1

if not primes:
    print(1)
    exit()

count = 0
for p in primes:
    c = 0
    t = 0
    for i in range(1, 10 ** 9):
        c += i
        t += 1
        if c > p[1]:
            count += t - 1
            break
        elif c == p[1]:
            count += t
            break

print(count)

Submission status: Time Limit Exceeded

Solution code:
def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return table
#引数nが素数かどうかを判定
def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1

N = int(input())
p_list = sieve(10000000)
cnt = 0
for i in range(100000):
    for j in range(1,100):
        q, mod = divmod(N, (p_list[i] ** j))
        if mod == 0:
            cnt += 1
            N = q
        else:
            break
    if N > 104743:
        a = is_prime(N)
        if a == True:
            cnt += 1
            break
print(cnt)