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:
import math
n = int(input())
l = int(math.sqrt(n))
ans = 0
  
insu = []
sisu = []
i = 2
while i <= l:
  if n % i == 0:
    if i in insu:
      sisu[insu.index(i)] += 1
    else:
      insu.append(i)
      sisu.append(1)
    n //= i
  else:
    i += 1
  
if not insu:
  if n == 1:
    print(0)
  else:
    print(1)
  exit()

for s in sisu:
  cnt = 1
  while cnt * (cnt + 1) / 2 <= s:
    ans += 1
    cnt += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
l = int(math.sqrt(n))
c = 0

for i in range(2, l+1):
  if n % i == 0:
    n //= i
    c += 1
  if n == 1:
    break

if c == 0:
  if n == 1:
    print(0)
  else:
    print(1)
else:
  print(c)

Submission status: Wrong Answer

Solution code:
from math import sqrt
n = int(input())
if n == 1:
    print(0)
if n == 2:
    print(1)
cnt = 0
for i in range(2, int(sqrt(n)) + 1):
    if n % i == 0:
        cnt += 1
        n /= i
if cnt:
    print(cnt)
else:
    print(1)

Submission status: Wrong Answer

Solution code:
def doit(n):
	c = 0
	temp = n
	for p in range(2, int(n ** 0.5) + 1):
		if temp % p == 0:
			e = 0
			while temp % p == 0:
				e += 1
				temp //= p
			c += int(0.5 * (-1 + (1 + 8 * e) ** 0.5))

	if temp == n:
		c += 1
	elif temp != 1:
		c += 1

	return c

print(doit(int(input())))

Submission status: Wrong Answer

Solution code:
N=int(input())

a={}
c=0
while N%2==0:
  N//=2
  c+=1
if c!=0:
  a[2]=c

f,c=3,0
while f*f<=N:
  if N%f==0:
    N//=f
    c+=1
    a[f]=c
  else:
    f+=2
    c=0
if N!=1:
  if N in a:
    a[N]+=1
  else:
    a[N]=1

t=0
for v in a.values():
  i=1
  while v>=i:
    t+=1
    i+=1
    v-=i

print(t)

Submission status: Wrong Answer

Solution code:
N=int(input())

a={}
c=0
while N%2==0:
  N//=2
  c+=1
if c!=0:
  a[2]=c

f,c=3,0
while f*f<=N:
  if N%f==0:
    N//=f
    c+=1
    a[f]=c
  else:
    f+=2
    c=0
if N!=1:
  if N in a:
    a[N]+=1
  else:
    a[N]=1

t=0
for v in a.values():
  i=1
  while v>=i:
    t+=1
    i+=1
    v-=1

print(t)

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())
print(factorization(N))

Submission status: Wrong Answer

Solution code:
from sys import stdin,stdout
from collections import deque,defaultdict
from math import ceil,floor,inf,sqrt,factorial,gcd,log2
from copy import deepcopy
ii1=lambda:int(stdin.readline().strip())
is1=lambda:stdin.readline().strip()
iia=lambda:list(map(int,stdin.readline().strip().split()))
isa=lambda:stdin.readline().strip().split()
mod=1000000007
n = ii1()
m = int(n**0.5)+1
count = 0
flag=0
for i in range(2,m):
    if n%i == 0:
        flag=1
        count+=1
        n=n//i
if n>1:
    print(1)
else:
    print(count)

Submission status: Wrong Answer

Solution code:
from sys import stdin,stdout
from collections import deque,defaultdict
from math import ceil,floor,inf,sqrt,factorial,gcd,log2
from copy import deepcopy
ii1=lambda:int(stdin.readline().strip())
is1=lambda:stdin.readline().strip()
iia=lambda:list(map(int,stdin.readline().strip().split()))
isa=lambda:stdin.readline().strip().split()
mod=1000000007
n = ii1()
m = int(n**0.5)+1
count = 0
flag=0
for i in range(2,m):
    if n%i == 0:
        flag=1
        count+=1
        n=n//i
if flag == 0:
    print(1)
else:
    print(count)

Submission status: Wrong Answer

Solution code:
from sys import stdin,stdout
from collections import deque,defaultdict
from math import ceil,floor,inf,sqrt,factorial,gcd,log2
from copy import deepcopy
ii1=lambda:int(stdin.readline().strip())
is1=lambda:stdin.readline().strip()
iia=lambda:list(map(int,stdin.readline().strip().split()))
isa=lambda:stdin.readline().strip().split()
mod=1000000007
n = ii1()
m = int(n**0.5)+1
count = 0
flag=0
for i in range(2,m):
    if n%i == 0:
        flag=1
        count+=1
        n=n//i
if flag == 1:
    print(1)
else:
    print(count)

Submission status: Wrong Answer

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

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


for t in range(len(arr)):
  cnt =1
  while arr[t] -cnt>=0:
    arr[t] -=cnt
    su +=1
    cnt +=1
    
   
print(su)

Submission status: Wrong Answer

Solution code:
arr = []
temp = int(input())
su =0
for i in range(2, int(-(-temp**0.5//1))+1):
  if temp%i==0:
    cnt=0
    store =i
    while temp%i==0 and temp !=i :
      cnt+=1
      
      temp //= i
      arr.append(i)
      su +=1
      i *=store
     
      
if temp!=1:
  if all(temp>s for s in arr):
    arr.append(temp)
    su +=1
    
  

if arr==[] and temp !=1:
  arr.append(n)
  su =1

        

print(su)

Submission status: Wrong Answer

Solution code:
arr = []
temp = int(input())
su =0
for i in range(2, int(-(-temp**0.5//1))+1):
  if temp%i==0:
    cnt=0
    store =i
    while temp%i==0:
      cnt+=1
      temp //= i

      arr.append(i)
      su +=1
      i *=store
      
if temp!=1:
  if all(temp>s for s in arr):
    arr.append(temp)
    su +=1
  

if arr==[] and temp !=1:
  arr.append(n)
  su =1

        

print(su)

Submission status: Wrong Answer

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

res = 0
if n <= 1:
	print(res)
else:
	max_num = int(math.sqrt(n + 1))
	org_n = n
	used_num_list = []
	for z in range(2, max_num + 1):
		# print(z, math.sqrt(n))
		if n == 1 or z >= math.sqrt(n):
			res += 1
			break
		if n % z == 0:
			# print(z, n, n//z)
			res += 1
			n = n // z
			if n == z:
				break
	if n == org_n:
		res += 1
	print(res)

Submission status: Wrong Answer

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

res = 0
if n <= 1:
	print(res)
else:
	max_num = int(math.sqrt(n))
	org_n = n
	num_list = list(range(2, max_num))
	z = num_list[0]
	while n > 1 and z <= math.sqrt(n + 1) and len(num_list) > 0:
		z = num_list[0]
		x = 1
		while True:
			y = z ** x
			if n % y == 0:
				n = n // y
				res += 1
			else:
				break
			x += 1
		if math.sqrt(n) - int(math.sqrt(n)) == 0 and n != 1:
			res += 1
			break
		used = list(range(z, max_num, z))
		num_list = sorted(list(set(num_list) - set(used)))
	if n in num_list:
		res += 1
	print(res)

Submission status: Wrong Answer

Solution code:
def main(n):

    prime = []
    if n < 2:
        prime.append((1,0))
    for p in range(2,int(n**0.5)):
        cnt = 0
        if p*p > n:
            break
        while n%p == 0:
            n //= p
            cnt += 1
        prime.append((p,cnt))
    if n > 1:
        prime.append((n,1))
    return prime
                    
n = int(input())    
pf = main(n)

ans = 0
for p, f in pf:
    cnt = 1
    while f >= cnt:
        f -= cnt
        ans += 1
        cnt += 1
    else:
        break

print(ans)

Submission status: Wrong Answer

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

res = 0
if n <= 1:
	print(res)
else:
	max_cnt = int(math.sqrt(n))
	org_n = n
	for z in range(2, max_cnt + 1):
		if n == 1 or z > math.sqrt(n):
			res += 1
			break
		if n % z == 0:
			# print(z, n, n//z)
			res += 1
			n = n // z
			if n == z:
				break
	if n == org_n:
		res += 1
	print(res)

Submission status: Wrong Answer

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

res = 0
if n == 1:
	print(res)
else:
	max_cnt = int(math.sqrt(n))
	org_n = n
	for z in range(2, max_cnt + 1):
		if n == 1 or z > math.sqrt(n):
			res += 1
			break
		if n % z == 0:
			# print(z, n, n//z)
			res += 1
			n = n // z
			if n == z:
				break
	if n == org_n:
		res += 1
	print(res)

Submission status: Wrong Answer

Solution code:
def isPrime(num):
    for i in range(3,int(num**0.5)+1):
        if(num%i==0):   return False
    return True

n = int(input())
i = 2 
count = 0
if(isPrime(n)==True):   print(1)
else:
    while(i<=int(n**0.5)+1):
        if(isPrime(i)==True):
            if(n%i==0):
                count+=1
        
        i+=1
        
    print(count)

Submission status: Wrong Answer

Solution code:
def isPrime(num):
    for i in range(3,int(num**0.5),2):
        if(num%i==0):   return False
    return True

n = int(input())
i = 2 
count = 0 
while(i<=n):
    if(isPrime(i)==True):
        if(n%i==0):
            count+=1
            n = n//i
        
    i+=1
        
print(count)

Submission status: Wrong Answer

Solution code:
def isPrime(num):
    for i in range(3,int(num**0.5),2):
        if(num%i==0):   return False
    return True

n = int(input())
i = 2 
count = 0
if(isPrime(n)==True):   print(1)
else:
    while(i<=n):
        if(isPrime(i)==True):
            if(n%i==0):
                count+=1
                n = n//i
        
        i+=1
        
    print(count)

Submission status: Wrong Answer

Solution code:
a =int(input())
list = []
b = 1
for i in range(2,44):
    list.append(b)
    b = b + i
n = 0
e = 0
k = 0
for i in range(2,1000000):
    if (a % i == 0):
        warikaisi = True
        while(warikaisi):
            if a % i == 0:
                list.append(i)
                a = a / i
                e = e + 1
                if (e == list[k]):
                    n = n + 1
                    k = k + 1
            else:
                e = 0
                k = 0
                warikaisi = False
if (n == 0 and a != 1):
    n = 1
if (a >= 1000000):
    n = n + 1
print(n)

Submission status: Wrong Answer

Solution code:
a =int(input())
list = []
b = 1
for i in range(2,44):
    list.append(b)
    b = b + i
n = 0
e = 0
k = 0
for i in range(2,1000000):
    if (a % i == 0):
        warikaisi = True
        while(warikaisi):
            if a % i == 0:
                list.append(i)
                a = a / i
                e = e + 1
                if (e == list[k]):
                    n = n + 1
                    k = k + 1
            else:
                e = 0
                k = 0
                warikaisi = False
if (n == 0 and a != 1):
    n = 1
if (a >= 1000000):
    n = 1
print(n)

Submission status: Wrong Answer

Solution code:
a =int(input())
list = []
b = 1
for i in range(2,44):
    list.append(b)
    b = b + i
n = 0
e = 0
k = 0
for i in range(2,10000000):
    if (a % i == 0):
        warikaisi = True
        while(warikaisi):
            if a % i == 0:
                list.append(i)
                a = a / i
                e = e + 1
                if (e == list[k]):
                    n = n + 1
                    k = k + 1
            else:
                e = 0
                k = 0
                warikaisi = False
if (n == 0 and a != 1):
    n = 1
print(n)

Submission status: Wrong Answer

Solution code:
a =int(input())
list = []
b = 1
for i in range(2,44):
    list.append(b)
    b = b + i
n = 0
e = 0
k = 0
for i in range(2,1000000):
    if (a % i == 0):
        warikaisi = True
        while(warikaisi):
            if a % i == 0:
                list.append(i)
                a = a / i
                e = e + 1
                if (e == list[k]):
                    n = n + 1
                    k = k + 1
            else:
                e = 0
                k = 0
                warikaisi = False
if (n == 0 and a != 1):
    n = 1
print(n)

Submission status: Wrong Answer

Solution code:
a =int(input())
list = []
b = 1
for i in range(2,44):
    list.append(b)
    b = b + i
n = 0
e = 0
k = 0
for i in range(2,100000):
    if (a % i == 0):
        warikaisi = True
        while(warikaisi):
            if a % i == 0:
                list.append(i)
                a = a / i
                e = e + 1
                if (e == list[k]):
                    n = n + 1
                    k = k + 1
            else:
                e = 0
                k = 0
                warikaisi = False
if (n == 0 and a != 1):
    n = 1
print(n)

Submission status: Wrong Answer

Solution code:
a =int(input())
list = []
b = 1
for i in range(2,44):
    list.append(b)
    b = b + i
n = 0
e = 0
k = 0
for i in range(2,1000000):
    if (a % i == 0):
        warikaisi = True
        while(warikaisi):
            if a % i == 0:
                list.append(i)
                a = a / i
                e = e + 1
                if (e == list[k]):
                    n = n + 1
                    k = k + 1
            else:
                e = 0
                k = 0
                warikaisi = False
print(n)

Submission status: Wrong Answer

Solution code:
a =int(input())
list= []
n = 0
for i in range(2,1000000):
    if (a % i == 0):
        warikaisi = True
        while(warikaisi):
            if a % i == 0:
                list.append(i)
                a = a / i
            else:
                n = n + 1
                warikaisi = False
print(n)

Submission status: Wrong Answer

Solution code:
import math
N=int(input())
S=[]
def is_prime(n):
    if n == 1: return False

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

    return True

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

ch=is_prime(N)
if ch==True:
    print(1)
    exit()
    
for i in range(2,610000):
    if i>=10 and i%2!=0 and i%3!=0:
        
        tmp=is_prime(i)
    else:
        tmp=is_prime(i)
    if tmp==True:
        
        R=i
        while R<=10**12:
            
            S.append(R)
            R*=i
S.sort()
count=0
nagasa=len(S)
for i in range(nagasa):
    if N%S[i]==0:
        N=N//S[i]
        count+=1

print(count)

Submission status: Wrong Answer

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

z_2 = 2
handan_1 = 0
while math.sqrt(N) >= z_2:
    if N % z_2 == 0:
        handan_1=1
    z_2+=1

if handan_1 == 0:
    z_s=[0,1]
else:
    z_s = [0]
    while N > max(z_s):
        z_1 = 2
        while True:
            handan = 0
            if N % z_1 == 0 and z_1 not in z_s:
                for i in range(2,z_1+1):
                    if z_1 % i == 0:
                        N = N // z_1
                        z_s.append(z_1)
                        handan = 1
                        break
            if handan == 1:
                break
            z_1 += 1
z_s.remove(0)            
print(len(z_s))

Submission status: Wrong Answer

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

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 tmp!=1:
        arr.append([tmp, 1]) # n is prime
    if arr == []:
        arr.append([n, 1]) # n==1 only
    return arr

def tri(m):
    if m==1:
        return 1
    s = 0
    ans = 0
    for i in range(1, m):
        s += i
        if s > m:
             break
        ans += 1
    return ans

n = int(input())
ans = 0
fts = factorization(n)
for i in fts:
    ans += tri(i[1])
print(ans)

Submission status: Wrong Answer

Solution code:
import math

def main():
    n = int(input())
    ans = solve(n)
    print(ans)

def solve(n):
    if n == 1:
        return 0
    cnt = [[i] * (i + 1) for i in range(20)]
    cnt = [i for inner in cnt for i in inner]
    factor = prime_factorization(n)
    ans = 0
    for p, e in factor:
        tmp = 1
        while e - tmp >= 0:
            e -= tmp
            tmp += 1
            ans += 1
    return ans

def prime_factorization(n):
    lim = math.floor(n ** (1 / 2))
    primelist = prime_list(lim)
    ans = []
    for p in primelist:
        if n % p == 0:
            e = 0
            while n % p == 0:
                e += 1
                n /= p
            ans.append((p, e))
    if ans == []:
        ans.append((n, 1))
    return ans

def prime_list(n):
    if n < 2:
        return []
    tmp = [True for i in range(n + 1)]
    tmp[:2] = [False, False]
    for i in range(n + 1):
        if tmp[i]:
            for j in range(2 * i, n + 1, i):
                tmp[j] = False
    ans = [num for num, flag in enumerate(tmp) if flag]
    return ans

def test():
    n = 101
    ans = prime_factorization(n)
    print(*ans, sep = '\n')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math

def main():
    n = int(input())
    ans = solve(n)
    print(ans)

def solve(n):
    if n == 1:
        return 0
    cnt = [[i] * (i + 1) for i in range(20)]
    cnt = [i for inner in cnt for i in inner]
    factor = prime_factorization(n)
    ans = 0
    for p, e in factor:
        ans += cnt[e]
    return ans

def prime_factorization(n):
    lim = math.floor(n ** (1 / 2))
    primelist = prime_list(lim)
    ans = []
    for p in primelist:
        if n % p == 0:
            e = 0
            while n % p == 0:
                e += 1
                n /= p
            ans.append((p, e))
    if ans == []:
        ans.append((n, 1))
    return ans

def prime_list(n):
    if n < 2:
        return []
    tmp = [True for i in range(n + 1)]
    tmp[:2] = [False, False]
    for i in range(n + 1):
        if tmp[i]:
            for j in range(2 * i, n + 1, i):
                tmp[j] = False
    ans = [num for num, flag in enumerate(tmp) if flag]
    return ans

def test():
    n = 101
    ans = prime_factorization(n)
    print(*ans, sep = '\n')

if __name__ == '__main__':
    main()

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:
            arr.append(i)
            temp //= i

    return arr


print(len(factorization(N)))

Submission status: Wrong Answer

Solution code:
N = int(input())
a = []
x = 2
while x ** 2 <= N:
    if N % x == 0:
        a.append(x)
        N /= x
    x += 1
else:
    if x % N == 0:
        a.append(N)
print(len(a))

Submission status: Wrong Answer

Solution code:
N = int(input())
a = []
x = 2
while x ** 2 <= N:
    if N % x == 0:
        a.append(x)
        N /= x
    x += 1
else:
    if x <= N:
        a.append(N)
print(len(a))

Submission status: Wrong Answer

Solution code:
N = int(input())
a = []
x = 2
while x ** 2 < N:
    if N % x == 0:
        a.append(x)
        N /= x
    x += 1
else:
    if x <= N:
        a.append(N)
print(len(a))

Submission status: Wrong Answer

Solution code:
N = int(input())
a = []
x = 2
while x <= N:
    if N % x == 0:
        a.append(x)
        N /= x
    x += 1
print(len(a))

Submission status: Wrong Answer

Solution code:
N = int(input())


handan = 0
for j in range(2,N//1000+1):
    if N%j == 0:
        handan=1
        break
if N == 1:
    print(0)
elif handan == 0:
    print(1)

else:
    z_1=[]
    while N!=1:
        
        for z in range(2,N+1):
            if N % z == 0 and z not in z_1:
                for i in range(2,z+1):
                    handan = 0
                    for j in range(2,i):
                        if i%j == 0:
                            handan=1
                            break
                    if handan == 0:
                        if z % i == 0:
                            z_1.append(z)
                            N //= z
                            break
                
                
    if z_1==[]:
        print(0)
    else:
        print(len(z_1))

Submission status: Wrong Answer

Solution code:
N = int(input())

a = []
n = N
if n % 2 == 0:
    a.append(2)
    while n%2 == 0:
        n /= 2
        
f = 3
while f**2 <= N:
    if n % f == 0:
        a.append(f)
        while n%f == 0:
            n /= f
    f += 2

answer = 0

for i in a:
    c = 1
    while N % i**c == 0:
        answer += 1
        N /=  i**c
        c += 1
print(answer)

Submission status: Wrong Answer

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

import math

n=int(input())
if(1==n):
    print(0)
    exit()
a=factorization(n)
ans=0
for i,j in a:
    ans+=math.ceil(j/2)
print(ans)