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:

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


def q4():
    N = int(input())
    arr = prime_factorize(N)

    ans_count = 0
    count = 1
    min_val = min(arr)
    while arr:
        if arr.count(min_val) < count:
            arr = list(filter(lambda a: a != min_val, arr))
            count = 1
            if not arr:
                break
            min_val = min(arr)
            continue
        arr = arr[count:]
        ans_count += 1
        count += 1
    print(ans_count)


q4()

Submission status: Runtime Error

Solution code:
def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n //= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(n)
  return table

n = int(input())
a = divisors(n)
cnt = 0
for i in range(1, len(a)):
    b = prime_decomposition(a[i])
    if len(list(set(b))) == 1:
        if n % a[i] == 0:
            n //= a[i]
            cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
input_count = 0

import sympy

def func(n, history):
    try:
        l = sympy.divisors(n)
    except:
        return history
    for i in l[1:]:
        if n == i:
            history.append(i)
            return history
        if i in history:
            continue
        history.append(i)
        func(n//i, history)
        break
    return history

N = int(input())
if N == 0:
    print(0)
else:
    h = func(N, [])
    print(len(set(h)))

Submission status: Runtime Error

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

#約数出す
def divisor(x):
    div=[]
    for i in range(1,int(x**(1/2))+1):
        if x%i==0:
            div.append(i)
            if i!=x//i:
                div.append(x//i)
    return sorted(div)

#累乗数判定
def is_perfect_power(x):
    size=int(math.log2(x)+1)
    for b in range(2,size):
        a=int(math.pow(x,1/b))
        if a**b==x or (a+1**b==x): return a
    return 0
    

A=divisor(N)
z=[]
for i in range(len(A)):
    if len(divisor(A[i]))==2:
        z.append(A[i])
    else:
        x=is_perfect_power(A[i])
        if x!=0:
            if len(divisor(x))==2:
                z.append(A[i])
z=sorted(z)
cnt=0
for i in range(N):
    if N>=z[i]:
        if N%z[i]==0:
            N=N//z[i]
            cnt+=1
    else:
        break
print(cnt)

Submission status: Runtime Error

Solution code:
from sympy import prime
n = int(input())
ans = 0
m = 2
while isprime(n) != True: 
  ans += 1
  n, mod = (mod,m)
  m += 1
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())


#整数N以下の素数を#素因数分解
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 = prime_factorize(N)
b = set(a)

dic = {}
for i in b:
    n = 0
    while True:
        n += 1
        a.pop(0)
        if a == []:
            break
        if a[0] != i:
            break
    dic[i] = n


an = 0
for k, v in dic.items():
    num = int((-1+(1+8*v)**(1/2))/2)
    an += num

print(an)

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(cnt)
    if temp!=1:
        arr.append(1)
    if arr==[]:
        arr.append(1)
    return arr

def calc(n):
    val = 1
    count = 0
    for i in range(2,100000):
        count += 1
        val = val + i
        if val > n:
            return count

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

print(arr)

ans = 0 
for val in arr:
    ans += calc(val)
 
print(ans)

Submission status: Runtime Error

Solution code:
n = input()
z=0
for i in range(n-1):
    if n % (i+2) == 0:
        n = n / (i+2)
        z = z +1
print(z)

Submission status: Runtime Error

Solution code:
import sys, math

sys.setrecursionlimit(10 ** 9)

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

def f(n):
    arr = list()
    temp = n
    for i in range(2, int(math.sqrt(n)) + 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 len(arr) == 0:
        arr.append([n, 1])

    return arr


t = f(N)
res = 0
A = [0, 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]
for b, a in t:
    res += int(A[a])
print(res // 1)

Submission status: Runtime Error

Solution code:
#include <algorithm>
#include <iostream>
#include <queue>
#include <cmath>
#include <string>
#include <iterator>
#include <map>
#include <set>
#include <iomanip>
#include <vector>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using Graph = vector<vector<int>>;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
#define INF 100000000
#define MAX 200001
#define MOD 1000000007
ll fac[MAX], finv[MAX], inv[MAX];
const int MX = 1000005;

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()
{
    ll N;
    cin >> N;
    vector<int> ans;
    for (auto p : prime_factor(N))
    {
        while (p.second--)
            ans.push_back(p.first);
    }
    int count=1;
    int res=0;
    int flag=1;
    for(int i=1;i<ans.size();i++){
        if(ans[i-1]==ans[i]){
            count++;
            flag=1;
        }
        else{
            if(i==1) res++;
            int c=1;
            int idx=1;
            while(true){
                if(c<=count){
                    c+=idx+1;
                    idx++;
                    continue;
                }
                res+=(idx-1);
                break;
            }
            count=1;
            flag=0;
        }
    }
    if(flag==0 | flag==1){
        int c = 1;
        int idx = 1;
        while (true)
        {
            if (c <= count)
            {
                c += idx + 1;
                idx++;
                continue;
            }
            res += (idx - 1);
            break;
        }
        count = 1;
        flag = 0;
    }
    if(N==1) res=0;
    cout<<res<<endl;
}

Submission status: Runtime Error

Solution code:
n = input()
z=0
for i in range(n-1):
    if n % (i+2) == 0:
        n = n / (i+2)
        z = z +1

Submission status: Runtime Error

Solution code:
import math
N = int(input())
temp = N
arr = []
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])
sum = 0
for i in range(len(arr)):
  p = arr[i][1]
  q = 1
  while p > 0:
    p -= q
    if p >= 0:
      sum += 1
      q += 1
print(sum)

Submission status: Runtime Error

Solution code:
from sympy import primerange

N = int(input())

m = 10**5
A246655 = []
for p in primerange(1, m):
    pe = p
    while pe < m:
        A246655.append(pe)
        pe *= p
A246655 = sorted(A246655)

c=0
for i in range(len(A246655)):
    if N%A246655[i]==0:
        N = N//A246655[i]
        c+=1
print(c)

Submission status: Runtime Error

Solution code:
import math
import collections
 
N = int(input())
prime_number = False
ans = 0
 
def trial_division(n):
    #素因数を格納するリスト
    factor = []
    #2から√n以下の数字で割っていく
    tmp = int(math.sqrt(n)) + 1
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    #リストが空ならそれは素数
    if not factor:
      global prime_number
      prime_number = True
      return
    else:
        factor.append(n)
        return factor
 
list_num = trial_division(N)
 
if prime_number:
  ans = 1
else:
  if 1 in list_num:
    prime_list = list_num[:-1]
    counter = collections.Counter(prime_list)
    for key,val in counter.items():
      temp = val
      for i in range(1,val+1):
        if temp-i > 0:
          temp -= i
          ans += 1
        elif temp-i == 0:
          temp -= i
          ans += 1
          break
        else
          break
    
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
count = 0
for i in range(2, int(N ** 0.5 + 1)):
    div, rem = divmod(N, i)
    if not rem:
        count += 1
        N = div
print(count + (N > i))

Submission status: Runtime Error

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

#define endl '\n'
#define ll long long
#define rint register int

#define re register
#define pb(x) push_back(x);
#define ce(x) cout << x << '\n';

using db = long double;
using pll = pair < ll, ll >;
#define scan(a, n) 		for(int i = 0; i < n; i++)cin >> a[i];

#define rep(i,x,n,inc) for(i=x ; i<n ; i+=inc)
#define repr(i,x,n,inc) for( i=x ; i>n ; i+=inc)
#define all(a)      (a).begin(),(a).end()
#define unique_sort(x) sort(all(x)), x.resize(distance(x.begin(), unique(all(x))))

#define mp(a,b) make_pair(a,b)
#define ff first
#define ss second
#define hell 1000000007
#define infl LLONG_MAX

#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Fill(s,v) memset(s,v,sizeof(s))
#define cout_p(x, p) cout << fixed << setprecision((p)) << x << endl     //print with precision


bool isPrime(ll n)
{
	// Corner cases
	if (n <= 1)  return false;
	if (n <= 3)  return true;

	// This is checked so that we can skip
	// middle five numbers in below loop
	// if (n % 2 == 0 || n % 3 == 0) return false;

	for (ll i = 2; i * i <= n; i = i + 1)
		if (n % i == 0 )
			return true;

	return false;
}

int32_t main() {
	ios::sync_with_stdio(0); 		cin.tie(0); cout.tie(0);

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	ll t, i, x, j, y, 	z = 0, k, n;
	// db a, b;
	cin >> n ;
	i = 2;
	while (i * i < n) {
		if (n % i == 0) {
			k = 0, j = 0;
			while (n % i == 0) {
				n /= i;
				j++;
				if (j > k)	k = j, z++, j = 0;
			}
		}
		i++;
	}



	// ce(n)
	if (n > 1)	z += isPrime(n);
	ce(z)
}

Submission status: Runtime Error

Solution code:
import math
import collections

N = int(input())
prime_number = False
ans = 0

def trial_division(n):
    #素因数を格納するリスト
    factor = []
    #2から√n以下の数字で割っていく
    tmp = int(math.sqrt(n)) + 1
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    #リストが空ならそれは素数
    if not factor:
      global prime_number
      prime_number = True
      return
    else:
        factor.append(n)
        return factor

list_num = trial_division(N)

if prime_number:
  ans = 1
else:
  if 1 in list_num:
    prime_list = list_num[:-1]
    counter = collections.Counter(prime_list)
    for key,val in counter.items():
      temp = val
      for i in range(1,val+1):
        if temp-i > 0:
          temp -= i
          ans += 1
        elif temp-i == 0:
          temp -= i
          ans += 1
          break
        elsea
          break
    
print(ans)

Submission status: Runtime Error

Solution code:
from sympy import divisors
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n //= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(n)
  return table

n = int(input())
a = make_divisors(n)
cnt = 0
for i in range(1, len(a)):
    b = prime_decomposition(a[i])
    if len(list(set(b))) == 1:
        if n % a[i] == 0:
            n //= a[i]
            cnt += 1
print(cnt)

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, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 8]

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

n = int(input())

faccs = [0 for i in range(int(n**0.5))]

while n % 2 == 0: 
    faccs[2] += 1
    n = n / 2

for i in range(3,int(math.sqrt(n))+1,2): 

    while n % i== 0: 
        faccs[i] += 1 
        n = n / i 

if n > 2: 
    faccs[int(n)] += 1 

count = 0

for i in faccs:
    if i > 0:
        temp = 1
        while (i-temp)>=0:
            i -= temp
            temp +=1
            count += 1
print(count)

Submission status: Runtime Error

Solution code:
//Hey u r far away to know this
#include <bits/stdc++.h>
using namespace std;
#define     ff      	    	first
#define     pb 	         	push_back
#define     ss          		second
#define     ll      	    	long long
#define     MAX  	       	5000
#define     mpi         		map<int, int>
#define     mpll        		map<ll, ll>
#define     pll         		pair<ll, ll>
#define     plld        		pair<ll, double>
#define     SKILLER     		ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define     vi          		std::vector<int>
#define     vll         		std::vector<ll>
#define     vs          		std::vector<string>
#define     vvi         		std::vector<std::vector<int>>
#define     vvll        		std::vector<std::vector<ll>>
#define     all(v)      		v.begin(), v.end()
#define     allr(v)      		v.rbegin(), v.rend()
#define     loop(i, a, b) 	for(int i = a; i < b; i++)
#define 	  debug(x) 		cout << x <<" " <<"\n";
#define 	  debug1(x, y) 	cout << x << " " << y  << "\n";
#define 	  debug2(x, y, z) 	cout << x << " " << y << " " << z<<"\n";
#define 	  int 			ll
const   int N = 1e6+5, Mod = 1e9 + 7;
int32_t main(){
    	SKILLER;
   
        int n; cin >> n;
        map<int, int> mp;
        int x = n;
        int i = 2;
        for(int i = 2; i*i <= x; i++){
        	while(x%i == 0){
        		mp[i]++;
        		x = x/i;
        	}
        }
        if(x > 1)
        	mp[x]++;
        int ans = 0;
        for(auto x:mp){
        	int a = x.ss;
        	a = sqrt(1 + 4 * 2 *a);
        	a = a - 1;
        	a /= 2;
        	ans += a;
        }
        cout << ans;
    	return 0;
}

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import math

N= int(input().rstrip('\n'))
M=N
lim = math.floor(math.sqrt(N))+1
res = 0
pri=[2]
for i in range(2,lim+1):
  if all(i % x != 0 for x in pri) or i==2:
    if N % i ==0:
      pri.append(i)
      add = 1
      pl = 1
      n = N//i
      while n%i==0:
        pl += 1
        n = n//i
        if pl=((add+1)*(add+2)/2):
          add += 1
      res += add
      N = N//(i**pl)
if M == N:
  res += 1
print(res)

Submission status: Runtime Error

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

n=int(input())
cnt=0
e=[]# used_list
f=0
pn=[2,3,5,7,11,13,17,19,23,29,31,37,41]
z=[2,3,4,5,7,8,9,16,25,27,32]
if n==1:
  cnt=0

else:
  while not is_prime(n):
    if n%z[f]==0:
      n=n//z[f]
      cnt+=1
      if n==1:break
    f+=1

print(cnt)