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

n = int(input())

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

a = collections.Counter(prime_factorize(n))

res = 0

for i in a.items():
    if i[1] > 3:
        res += math.floor(i[1]/2)
    elif i[1] == 3:
        res += 2
    else:
        res += 1

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

factN = factorization(N)
counter = 0

for i in range(len(factN)):
  t = factN[i][1]
  e = 0
  while True:
    t -= e
    if t < 0:
      counter += e
      break
    e += 1

print(counter - len(factN))

Submission status: Wrong Answer

Solution code:
n = int(input())

d = dict()


ans = 0

for i in range(2, int(n ** 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:
def prime_factorize(n):
    a = []
    if n%2== 0:
        a.append(2)
        n//=2
    f = 3
    while f*f<=n:
        if n%f==0:
            a.append(f)
            n//=f
        f+=1
    if n!=1:
        a.append(n)
    return a

print(len(prime_factorize(int(input()))))

Submission status: Wrong Answer

Solution code:

if __name__ == '__main__':
    a = int(input())
    count = 0
    now =a
    for i in range (2,a):
        if now == 1 or now <i:
            break
        else:
            if now % i == 0:
                now = now/i
                count+=1

    print(count)

Submission status: Wrong Answer

Solution code:
def prime(p):
    memo = []
    for i in range(2,(int(p**0.5)+1)):
        if p%i==0:
            p //= i
            memo.append(i)
            #print(memo)
    if p != 1:
        memo.append(p)
    return memo
 
n=int(input())
 
memo = prime(n)

memo = set(memo)

if len(memo) == 0:
  print(0)
else:
  ans = len(memo)
  print(ans)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())  # 10**12
sqrt_N = int(math.sqrt(N))
if N == 1:
    print(0)
    exit()

sosuu = [2]
A = sqrt_N + 2
for i in range(3, A, 2): # 2 以外の素数は奇数なので
    is_prime = True
    sqrt_i = math.sqrt(i)
    for L2 in sosuu:
        if i % L2 == 0:  # すべての既存素数で割り切れなかったら素数
            is_prime = False
            break
        if L2 > sqrt_i:
            break
    if is_prime:
        sosuu.append(i)

# print(sosuu)
ans = 0
for i in sosuu:
    n = 1
    while 1:
        i_n = i ** n
        d,m = divmod(N, i_n)
        # print(d,m)
        if m == 0:
            N = d
            n += 1
            ans += 1
        else:
            break
if ans == 0:
    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)))):
    count=0
    if a%b==0:
        while a%b==0:
            count+=1
            a=a/b
    L.append(count)

if len(L)==0 and K==0:
    print(1)
    PP=1
sum=0
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:
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())
s=factorization(n)
sum=0
for i in range(len(s)):
  if s[i][1]==1:
    sum+=1
  else:
    sum+=(s[i][1]+1)//2
if n==1:
  print(0)
else:
  print(sum)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())

def getDivisor(n):
    divisor = []
    tmp = n
    for i in range(2, int(n**0.5)+1):
        cnt = 1
        d = [1,]
        while tmp%i == 0:
            d.append(i**cnt)
            tmp //= i
            cnt += 1
        if cnt > 1:
            divisor.append(d)
    if tmp != 1:
        divisor.append([1,tmp])
    if divisor == []:
        divisor.append([1,n])
        
    #print(divisor)
       
    divisor_mat = np.matrix(1) 
    for d in divisor:
        d = np.matrix(d)
        mat = []
        for dcol in divisor_mat:
            mat.append(dcol.T * d)
        divisor_mat = np.concatenate(mat)
    divisor_mat = np.array(divisor_mat.flatten())
    divisor_mat = np.array(divisor_mat[0].tolist())
    divisor_mat.sort()
    return divisor_mat
  
divisors = getDivisor(n)
if n==1:
  print(0)
else:
  ans = 0
  for d in divisors[1:]:
    if n%d == 0:
      ans += 1
      n /= d
  print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main():  #startline-------------------------------------------
    n = int(input())
    if n == 1:
        print(0)
        exit()
    ans = 0
    for i in range(2, math.floor(np.sqrt(n))+1):
        if n % i == 0:
            n //= i
            ans += 1
    if ans == 0:
        print(1)
    else:
        print(ans)
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""
import math

def main():
    N = int(input())
    # Nが1のときは答えは0
    if N == 1:
        print(0)
        return
    else:
        N_remein = N
        # Nを素因数分解する。
        p_list = []
        p_factor_list = []
        for p in range(2, math.ceil(math.sqrt(N))+1):
            if N_remein%p == 0:
                counter = 0
                #p_pow_counter = 1
                while True:
                    #p_pow_counter *= p
                    if N_remein%p == 0:
                        N_remein = N_remein//p
                        counter+=1
                    else:
                        p_list.append(p)
                        p_factor_list.append(counter)
                        break
        # Nが素数の場合は、答えは1。
        if not p_factor_list:
            print(1)
            return
        else:
            #print(p_list)
            #print(p_factor_list)
            answer = 0
            # 各素因数の指数に対して、、
            # 1,2,3,...と正整数を順番に引いていき、
            # 引けた回数を合計する。
            for factor in p_factor_list:
                counter = 1
                counter_sum = 0
                while True:
                    counter_sum += counter
                    if counter_sum <= factor:
                        counter += 1
                    else:
                        answer += counter-1
                        break
            print(answer)
            return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())

a = set()
N = n
i = 2
while i * i <= N:
    if (N % i) != 0:
        i += 1
        continue
    now = i
    count = 1
    while N >= now:
        if N % now == 0:
            a.add(now)
            N //= now
        count += 1
        now = i ** count
    i += 1
if N != 1:
    a.add(N)
print(len(a))

Submission status: Wrong Answer

Solution code:
n=int(input())

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)
    return ass

a=sorted(divisor(n))

ans=0
for i in range(1,len(a)):
    if n%a[i]==0:
        n=n//a[i]
        ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
orgn=n
counter=0
for i in range(2,int(n**0.5)):
    if n % i == 0:
        counter += 1
        n //= i
        wari=i**2
        while n % wari == 0:
            counter +=1
            n //= wari
            wari *= i
        while n % i ==0:
            n //= i

if n == orgn:
    if n == 1:
        print(0)
    else:
        print(1)
else:
    print(counter)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

count = 0

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

def sosu(n):
  if n != 1:
    for i in range(2, int(math.sqrt(n)) + 1, 1):
      if n % i != 0:
        pass
      else:
  	    break
    else:
      return 1
  	
  return 0

for i in soinsu:
  num = 1
  if sosu(i[0]):
    while 1:
      if i[1] - num >= 0:
        num += 1
        count += 1
        i[1] -= 1
      else:
  	    break
  	  
print(count)

Submission status: Wrong Answer

Solution code:
def task(n):
    if n == 1:
        print(0)
        return

    primes = {}
    i = 2
    while i < 1000001 and i <= n:
        if n % i == 0:
            n = n // i
            if not i in primes:
                primes[i] = 0
            primes[i] += 1
        else:
            i += 1

    # print(primes)
    ans = 0
    for prime in primes:
        e = 1
        count = primes[prime]
        while count >= e:
            count -= e
            e += 1
            ans += 1

    if ans == 0:
        ans = 1

    print(ans)


n = int(input())
task(n)

Submission status: Wrong Answer

Solution code:
import numpy as np
n=int(input())
def f(n):
  num=int(np.sqrt(2*n))
  while True:
    if num*(num+1)//2 > n:
      return num-1
    num+=1
p=[]
p_tf=[1 for i in range(int(np.sqrt(n))+1)]
p_tf=np.array(p_tf)
for i in range(2,int(np.sqrt(n))+1):
  if p_tf[i] and n%i==0:
    p.append(i)
    p_tf[i::i]-=1
if len(p)==0:
  p=[n]
n2=n
ans=0
for i in p:
  j=1
  while True:
    if n2%i==0:
      n2//=i
      j+=1
    else:
      j-=1
      break
  ans+=f(j)
print(ans)

Submission status: Wrong Answer

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

i=2
ans=0
count1=0
count2=1
while math.sqrt(N)>=i:
    if nn%i==0:
        nn//=i
        count1+=1
        if count1//count2>0:
            ans+=1
            count2+=1
            count1=0
    else:
        i+=1
        count1=0
        count2=1

if ans==0 and N>=2:
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
#デフォルト
import itertools
from collections import defaultdict
import collections
from decimal import *
import math
import sys
sys.setrecursionlimit(200000)
mod = 1000000007

n = int(input())

def 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

if (Prime(n)):
    print("1")
else:
    ans = 0
    for i in range(2, 10 ** 4):
        if Prime(i):
            for j in range(1,10 ** 2):
                if n % (i ** j) == 0:
                    ans += 1
                    n = n // (i ** j)
                if n == 1:
                    break
        if n == 1:
            break

    print(ans)