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:
from collections import Counter
import math

def div(n):
    if n == 1:
        return []
    prime = []
    tmp = int(math.sqrt(n)) + 1
    
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            prime.append(num)
    
    if len(prime) == 0:
        return [1]
    else:
        return prime

n = int(input())
prime_div = dict(Counter(div(n)))
ans = 0
divs = list(prime_div.values())

for i in range(len(divs)):
    k = 0
    for j in range(1, 10):
        k += j
        if k > divs[i]:
            break
        ans += 1

print(ans)

Submission status: Wrong Answer

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


def primes(n):
    ps = {}
    for i in range(2, int(n ** 0.5) + 20):
        if n == 1:
            break
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                n = n // i
                cnt += 1

            ps[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)

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

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

#素数リスト
M = int(math.sqrt(N))+1
sosu = [2]
a = 0
for i in range(3,M,2):
  if sosu[a] <= math.sqrt(i):
    a += 1
  hantei = (i%x for x in sosu[:a+1])
  if 0 not in hantei:
    sosu.append(i)

soin = []
for p in sosu:
    for j in range(1,N+1):
        pe = p**j
        if N % pe != 0:
            if pe != p:
                soin.append(j-1)
            break

Ans = 0
for k in soin:
    for n in range(1,k+1):
        if (n*(n+1))//2 > k:
            Ans += n-1
            break
print(max(Ans,1))

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
primelist = []
count = 0
for i in range(2, int(math.sqrt(N))+1):
    if N % i == 0:
        N = N / i
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
# coding: utf-8

import sys
import math
from collections import Counter
import itertools
import fractions
from decimal import *
#import numpy as np
#from functools import reduce

# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SR(): return sys.stdin.readline().rstrip()

ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_uppercase2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'

# リストを改行区切りで出力する
p2D = lambda x: print(*x, sep="\n")
p2E = lambda x: print(''.join(x))
p2S = lambda x: print(*x, sep=" ")

# ###########################################
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=II()

current = 2
ans = factorization(N)

cnt = 0

for an in ans:
    if an[0] != 1:
        k = an[1]
        i = 1

        if k == 1:
            cnt += 1
        if k == 2:
            cnt += 1
        if k == 3:
            cnt += 2
        if k == 4:
            cnt += 1
        if k == 6:
            cnt += 3
        if k == 10:
            cnt += 4
        if k == 15:
            cnt += 5


print(cnt)

Submission status: Wrong Answer

Solution code:
N=int(input())
p=[i for i in range(2,N+1)]
count=0
for item in p:
  N=N/item
  count+=1
  p.remove(item)
  if N==1:
    break
print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())

d = dict()


ans = 0

k=n
for i in range(2, int(k ** 0.5)):
    if n % i == 0 and (i not in d):
        n /= i
        ans += 1
        d[i] = True
        

if n > 1 and (n not in d):
    ans += 1
    

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
ans=0
r=int(n**0.5)+1
for i in range(2,r):
    if n%i==0:
        ans+=1
        n/=i
if ans==0 and not n==0:
    ans=1
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8

import sys
import math
from collections import Counter
import itertools
import fractions
from decimal import *
#import numpy as np
#from functools import reduce

# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SR(): return sys.stdin.readline().rstrip()

ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_uppercase2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'

# リストを改行区切りで出力する
p2D = lambda x: print(*x, sep="\n")
p2E = lambda x: print(''.join(x))
p2S = lambda x: print(*x, sep=" ")

# ###########################################
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=II()

current = 2
ans = factorization(N)

cnt = 0
print(ans)
for an in ans:
    if an[0] != 1:
        k = an[1]
        i = 1

        if k == 1:
            cnt += 1
        if k == 2:
            cnt += 1
        if k == 3:
            cnt += 2
        if k == 4:
            cnt += 1
        if k == 6:
            cnt += 3
        if k == 10:
            cnt += 4
        if k == 15:
            cnt += 5


print(cnt)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

t = N
ans = 0

arr = []
for s in range(2, N):
    if t < s:
        break
    if t % s == 0:
        if s % 2 == 0:
            if math.log2(s) % 1 == 0:
                t /= s
                ans += 1
        else:
            if all(s % s2 != 0 for s2 in arr):
                arr.append(s)
                is_so = True
            elif all(math.log(s, s2) % 1 == 0 for s2 in arr):
                is_so_baisu = True
            if is_so or is_so_baisu:
                t /= s
                ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math
def eratos(n):
    isprime = [True for i in range(n+1)]
    isprime[0] = False
    isprime[1] = False
    for i in range(2, int(math.sqrt(n))+13):
        if isprime[i]:
            j = i + i
        while j <= n:
            isprime[j] = False
            j = j + i
    return isprime
N = int(input())
ans = 0
is_prime = eratos(10**6)
for i in range(2, 10**6+1):
    if not is_prime[i]:
        continue
    x = i
    while N % x == 0:
        ans += 1
        N //= x
        x *= i
        # print(N)
if ans == 0 and N != 1:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import math

a=int(stdin.readline())
PP=0
K=0

if a==1:
    print(0)
    K=1
L=list()

for b in range(2,int(math.floor(math.sqrt(a)))+1):
    count=0
    if a%b==0:
        while a%b==0:
            count+=1
            a=a/b
    if count>0:
       L.append(count)

if len(L)==0 and K==0:
    print(1)
    PP=1
sum=0
print(L)
for k in range(0,len(L)):
    p=L[k]
    sum+=int(math.floor((-1+math.sqrt(1+8*p))/2))

if PP==0 and K==0:
   print(sum)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [0 for i in range(int(N**0.5)+1)]
c = 0
i = 2
m = 0
while i < N**0.5:
    if N % i == 0:
        a[i] += 1
        N = N / i
        m = i
        i -= 1
    i += 1
    if N == 1:
        break 
for j in range(2, m+1):
    if a[j] != 0:
        d = 0
        while a[j] > d:
            a[j] -= d+1
            d += 1
        c += d
print(c+1, end='')

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

p = [1,1,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,5,5,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,9,10,10,10,10,10,10,10,10,10,10,10,11,11,11,11,11,11,11,11,11,11,11,11,12,12,12,12,12,12,12,12,12,12,12,12,12,13,13,13,13,13,13,13,13,13,13,13,13,13,13,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15]

n = int(input())
if n == 0:
    print(0)
else:
    ans = 0
    for j in factorization(n):
        ans += p[j[1]-1]

    print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    if n == 1:
        print(0)
        exit()

    mid = int(n ** (0.5))
    cnt = 0
    for i in range(2, mid + 1):
        if n % i == 0:
            cnt += 1
            n //= i

    if cnt == 0:
        print(0)
    else:
        print(cnt)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math


n = int(input())
cnt_list = [1,3,6,10,15,21,28,36]

def get_list(i):
    loop_cnt = int(math.sqrt(i)) + 1
    ret_list = []
    j = 2
    cnt = 0
    while j <= loop_cnt:
        if i % j == 0:
            i /= j
            cnt += 1
        else:
            if cnt > 0:
                for k in range(8):
                    if cnt < cnt_list[k]:
                        break
                for _ in range(k):
                    ret_list.append(j)
                cnt = 0
            j += 1
    if i != 1:
        ret_list.append(i)
    return ret_list

len(get_list(n))

Submission status: Wrong Answer

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

    if n!=1:
        ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10**6)

n=int(input())

m=int(np.sqrt(n))+1

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

ans=0
for i in range(2,m):
    cnt=0
    for j in range(40):
        if n%i==0:
#            print("i=",i,"n=",n)
            n=n/i
            cnt+=1
        else:
            break
    if 1<=cnt<3:
        ans+=1
    if 3<=cnt<6:
        ans+=2
    if 6<=cnt<10:
        ans+=3
    if 10<=cnt<15:
        ans+=4
    if 15<=cnt<21:
        ans+=5
    if 21<=cnt<28:
        ans+=6
    if 28<=cnt<36:
        ans+=7
    if 36<=cnt<45:
        ans+=8

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

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

#f = open('./input_D.txt')
#N = int(f.readline())

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

fact_N = factorization(N)
fact_N = np.array(fact_N)
num_sosuu = fact_N[:,1]

num_sosuu_max = num_sosuu.max()
ans = 0
for i in range(len(num_sosuu)):
    num_i = num_sosuu[i]
    for j in range(np.uint64(np.sqrt(2*num_sosuu_max))):
        if num_i >= j+1:
            ans += 1
            num_i -= j+1
        else:
            break

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)


n=int(input().rstrip())
a=[]
tmp=n
for i in range(2,int(n**0.5)+1):
    if tmp%i==0:
        while tmp%i==0:
            a.append(i)
            tmp//=i
#print(a)
if tmp!=1:
    a.append(tmp)
s=set()
t=1
for i in a:
    if i not in s:
        s.add(i)
    else:
        t*=i
        if t not in s:
            s.add(t)
            t=1
    #print(t,s)
if t not in s and t!=1:
    s.add(i)
print(len(s))

Submission status: Wrong Answer

Solution code:
#D
import math
N = int(input())
Nsyo = N
count = 0
div = 2
while N > 1 and div <= math.sqrt(N):
    if N%div == 0:
        N = N/div
        count = count +1
    else:
        pass
    div = div +1
if N == Nsyo and N>0:
    count = count +1
else:
    pass
print(count)

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

p = [1,1,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,5,5,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,9,10,10,10,10,10,10,10,10,10,10,10,11,11,11,11,11,11,11,11,11,11,11,11,12,12,12,12,12,12,12,12,12,12,12,12,12,13,13,13,13,13,13,13,13,13,13,13,13,13,13,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15]

n = int(input())
if n == 0:
    print(0)
else:
    ans = 0
    print(factorization(n))
    for j in factorization(n):
        ans += p[j[1]-1]

    print(ans)

Submission status: Wrong Answer

Solution code:
import math
primes = []

def isnprimt(n) :
    i = 0
    while i<len(primes) and primes[i]*primes[i] <= n :
        if n%primes[i] == 0 :
            return False
        i += 1
    return True

def solve() :
    n = int(input())
    m = int(math.sqrt(n))+1
    is_prime = [True]*m
    ans = 0
    used = set()
    if n == 1 :
        return 0
    for i in range(2, m) :
        if is_prime[i] :
            primes.append(i)
            j=i 
            while n%j == 0 :
                n//=j 
                used.add(j)
                j*=i
                ans += 1
            j=i+i 
            while j<m :
                is_prime[j] = False
                j += i 
    if n != 1 and n not in used and isnprimt(n):
        ans += 1 
    return ans

print(solve())

Submission status: Wrong Answer

Solution code:
def is_prime(n):
    for p in PRIME:
        if n in DONE and not n % p:
            return False
    return True


N = int(input())

DONE = []
PRIME = []

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

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

print(len(DONE))

Submission status: Wrong Answer

Solution code:
# 2020/05/31
# AtCoder Beginner Contest 169 - D

import math

# 素因数分解(参考: https://qiita.com/snow67675476/items/e87ddb9285e27ea555f8)
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

# Input
n = int(input())

# Calc
flist = factorization(n) 
ans = 0
for i in range(len(flist)):
    wkcnt = math.ceil((math.log2(flist[i][1])))
    ans = ans + max(wkcnt, 1)

if n == 1:
    ans = 0

# Output
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
p=[i for i in range(2,N)]
count=0
for item in p:
  N=N/item
  count+=1
  p.remove(item)
  if N==1:
    break
print(count)

Submission status: Wrong Answer

Solution code:

import collections
def factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
def numcount(n):
    if n <= 2:
        return 1
    ret = 0
    i = 1
    while True:
        n -= i

        if n < i:
            break
        i += 1
    return i
A = int(input())
L = factorize(A)
C = collections.Counter(L)
ret = 0
for c in C:
    ret += numcount(C[c])
print(ret)