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

Solution code:
import math
#試し割法
def trial_division(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 = trial_division(int(input()))

key = []
val = []

dupli = set()
for i in range(len(N)):
    if (not N[i] in dupli):
        key.append(N[i])
        dupli.add(N[i])

for i in range(len(key)):
    val.append(N.count(key[i]))


numList = [0, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6]

sum = 0
for i in range(len(key)):
    sum += numList[val[i]]
    # count = 1
    # length = val[i]
    # if (length < 3):
    #     sum += 1
    # else:
    #     while(length > 0):
    #         sum += 1
    #         length -= count
    #         if (length == count):
    #             break
    #         count += 1

print(sum)

Submission status: Runtime Error

Solution code:
import math

is_prime = [True for i in range(10 ** 6 + 1)]
primes = []
def SieveOfEratosthenes(n):
    p = 2
    while (p * p <= n):
        # If prime[p] is not
        # changed, then it is a prime
        if (is_prime[p] == True):
            # Update all multiples of p
            for i in range(p * p, n + 1, p):
                is_prime[i] = False
        p += 1
    for i in range(2, n + 1):
        if is_prime[i]:
            primes.append(i)
def prime(n):

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

def power_of_prime(n):
    for i in primes:
        if n % i == 0:
            c = 0
            while n % i == 0:
                n//= i
                c += 1
            if n == 1:
                return 1
            else:
                return 0


n=int(input())
k=0

SieveOfEratosthenes(int((math.sqrt(n)))+1)
t=prime(n)
if t==1:
    print(1)
else:
    for i in range(2,int(math.sqrt(n))+1):
        if n>1 and n%i==0 and power_of_prime(i)==1:
            k+=1
            n=n//i

    print(k)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

using lli = long long int;

template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

template <class T>ostream &operator<<(ostream &o,const pair<T, T>&p)
{o<<"("<<p.first<<", "<<p.second<<")";return o;}

#define rep(i, n) for(lli i = 0; i < (lli)(n); i++)

const lli MOD = 1000000007LL;

lli modpow(lli a, lli n){
    lli res = 1;

    for(lli ai = a; n; n>>=1){
        if(1&n) res = (res*ai)%MOD;
        ai=(ai*ai)%MOD;
    }
    return res;
}

lli inv(lli n){
    return modpow(n, MOD-2);
}

lli modperm(lli n, lli k){
    lli res = 1;
    rep(i, k){
        res = (res*(n-i))%MOD;
    }
    return res;
}

lli modcomb(lli n, lli k){
    return (modperm(n, k)*inv(modperm(k, k)))%MOD;
}

lli posmod(lli n){
    lli res = n;
    res %= MOD;
    if(res < 0) res += MOD;
    return res;
}
map< int64_t, int > prime_factor(int64_t n) {
  map< int64_t, int > ret;
  for(int64_t i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}

int main(void){
    lli res = 0;
    lli n;
    cin >> n;
    auto ptable = prime_factor(n);
    for(auto i : ptable){
        int b = i.second;
        int t = 1;
        while(b > 0){
            if(t > b){
                b = 0;
                break;
            }
            b-=t;
            t++;
            res++;
        }
    }
    cout << res << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
def conv_v(x):
  if x <= 2 : return 1
  if x <= 5 : return 2
  if x <= 9 : return 3
  if x <= 14 : return 4
  if x <= 20 : return 5
  if x <= 27 : return 6
  if x <= 35 : return 7

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

import collections
N = int(input())
c = collections.Counter(prime_factorize(N))
answer = 0
for i in range(len(c.value)):
  answer += conv_v(c.value[i])
print(answer)

Submission status: Runtime Error

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
ans = 0

if(N>1):
    Q = factorization(N)
    "print(Q)"
    A = [ b for [a,b] in Q]
    for a in A:
        i = 1
        while(a >= i):
            a -= i
            i += 1
            ans += 1
    print(ans)

else:
    print(0)