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:
N = int(input())

A246655 = [2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 81, 83, 89, 97, 101, 103, 107, 109, 113, 121, 125, 127, 128, 131, 137, 139, 149, 151, 157, 163, 167, 169, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 243, 251, 256, 257, 263, 269, 271, 277, 281, 283, 289, 293, 307, 311, 313, 317, 331, 337, 343, 347, 349, 353, 359, 361, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 512, 521, 523, 529, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 625, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 729, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 841, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 961, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1024, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1331, 1361, 1367, 1369, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1681, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1849, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2048, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2187, 2197, 2203, 2207, 2209, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2401, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2809, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3125, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3481, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3721, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4096, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4489, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4913, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5041, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5329, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6241, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6561, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6859, 6863, 6869, 6871, 6883, 6889, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7921, 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8192, 8209, 8219, 8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9409, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973]

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

Submission status: Wrong Answer

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

X = N
cnt = 0
for i in range(2, int(math.sqrt(N))):
    for j in range(1, 40):
        if X < i**j:
            break
        if (X % (i**j)) == 0:
            X = X / i**j
            cnt = cnt + 1
        else:
            break

flg = 0
if X > int(math.sqrt(N)):
    if not N < 2:
        if N == 2:
            cnt = cnt + 1
        else:
            for p in range(2, int(math.sqrt(X))):
                if X % p == 0:
                    flg = 1
                    break
            if flg == 0:
                cnt = cnt + 1
print(cnt)

Submission status: Wrong Answer

Solution code:

import sys

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())

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

A=factorization(N)

numlist=range(2,50)
sinsa=1
ans=0
for i in range(len(A)):
    beki=A[i][1]
    sosu=A[i][0]
    for j in range(1,beki+1):
        N=N/(sosu**j)
        ans+=1
        sinsa=sinsa+numlist[i]
        if sinsa>beki:
            sinsa=1
            break
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
#n = 2*10**8
n = 30001002
import math
prime = [0] * (n+1) # i番目の素数
is_prime = [True] * (n+1)
p = 0 # 何番目か　0-indexed
is_prime[0] = False
is_prime[1] = False
ll = 0
#print('a')
for i in range(2,n+1):
    #ll += 1
    #print(i)
    if is_prime[i] == True:
        prime[p] = i # p番目の素数はiとなる
        p += 1
        # print(ll)
        # if p == 1000*ll:
        #     print(p)
        for j in range(2*i, int(math.sqrt(n))+1,i):
            is_prime[j] = False # その素数の倍数のやつ

#print(sieve(n,11000000))
#print(prime)
import math
def is_prime(n):
    for i in range(2,int(math.sqrt(n)+1)):
        if n % i == 0:
            return False
    return n != 1 # 1の場合は除外

n = int(input())
if is_prime(n):
    print(1)
    exit()
cnt = 0
for i in range(p):
    if n == 1:
      break
    v = prime[i]
    nya = prime[i]
    while n % v == 0:
        cnt += 1
        n //= v
        v *= nya
print(cnt)

Submission status: Wrong Answer

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
 
def gen_list_n_removed(l, n):
    return [i for i in l if i != n]
 
def seachPrimeNum(N):
    max = int(math.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum
 
 
 
N = int(input())
 
num_list = set()
 
hoge = seachPrimeNum(2000000)
 
for i in range(1, 30):
    for j in hoge:
        res = j ** i
        if res > 10 ** 12:
            break
        num_list.add(j ** i)
 
num_list = sorted(num_list)
 
if is_prime(N):
    print(1)
    exit(0)
 
count = 0
while True:
    for i in num_list:
        if N % i == 0:
            N = N / i
            count += 1
            num_list = gen_list_n_removed(num_list, i)
            break
        if i == num_list[-1]:
            print(count)
            exit(0)

Submission status: Wrong Answer

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 is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1

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())
a = divisor(n)

s = n
cnt = 0

if is_prime(n) == True:
    print("1")
    exit(0)
if n == 1:
    print("0")
    exit(0)


for i in range(1,len(a)):
    b = factorization(a[i])

    if is_prime(a[i]) == True or len(b) == 1:
        if s % a[i] == 0:
            s = s/a[i]
            cnt += 1

    if s == 1:
        print(cnt)
        exit(0)

Submission status: Wrong Answer

Solution code:
N = int(input())
def is_prime(n):
    if(n<=1):
        ans=False
    elif(n==2):
        ans=True
    else:
        for i in range(2,n):
            if(n%i==0):
                ans=False
                break
            if(i**2>n):
                ans=True
                break
    return ans
z=2
recode={}
count=0
if is_prime(N):
    print(1)
else:
    while N!=1:
        if is_prime(N):
            count=count+1
            break
        if N%z==0:
            if z not in recode.keys():
                recode[z]=1
                N=int(N/z)
                z=2
                count+=1
                if is_prime(N):
                    count=count+1
                    break
            else:
                z+=1
        else:
            z+=1
    print(len(recode.keys()))

Submission status: Wrong Answer

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

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

ans=0
for p in p_list:
    N=n
    cnt=0
    z_list=[]

    while N!=1:
        for j in range(1,int(math.log2(n))+1):
            if N==1:
                break
            else:
                z=p**j
                if z in z_list:
                    N=1
                    break
                else:
                    if n%z==0 and z <=n:
                        z_list.append(z)
                        cnt+=1
                        N=N//z
    
    ans=max(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
dim = 7
prime = [1]*(10**dim+1)
from collections import Counter
p = Counter()
p_set = []
for i in range(2,10**dim+1):
    j = i
    if prime[i] != 0:
        p[i] += 1
        p_set.append(i)
        while(j <= 10**dim):
            prime[j] = 0
            j += i

N = int(input())
cnt = 0
for n in p_set:
    if n > N:
        break
    while(1):
        if N%(n**p[n])==0:
            N //= n**p[n]
            cnt += 1
            p[n] += 1
        else:
            break
if cnt == 0 and N > 1:
    cnt = 1
print(cnt)

Submission status: Wrong Answer

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
import math

def factorize(n):
  ret, a = [], n
  for i in range(2, int(n**0.5)+1):
    if a%i>0: continue
    c=0
    while a%i==0:
      a//=i
      c+=1
    else:
      ret.append((i,c))
  if a!=1: ret.append((a,1))
  return ret

#nの素数判定
def is_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


n = int(input())
N = factorize(n)
#p(N)

i = 2
ans=0
while n >= i:
  if is_prime(n):
    n /= n
    ans += 1
    #p("ans=",ans)
    continue
  if n % i ==0:
    for k,_ in N:
      a = math.log(i, k)
      #p("n,i,k,a,int(a)=",n,i,k,int(a),a)
      if int(a)==a:
        n /= k
        ans += 1
        #p("ans=",ans)
        continue

  i += 1

print(ans)

Submission status: Wrong Answer

Solution code:

N = int(input())

def furui(n):
    if n < 2:
        return []
    plist = [1 for i in range(n)]
    plist[0] = plist[1] = 0
    for i in range(2, n):
        if plist[i]:
            for j in range(i*2, n, i):
                plist[j] = 0
    ret = []
    for i in range(n):
        if plist[i] != 0:
            ret.append(i)
    return ret


primes = furui(1000000)
count = 0

if N == 1:
    print(0)
else:
    for p in primes:
        e = 1
        while N % (p ** e) == 0:
            z = p ** e
            N //= z
            count += 1
            # print(z, N)
            e += 1
    if count:
        print(count)
    else:
        print(1)  # prime

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
num = int(input())
num1 = num
ans  = []


for i in range(2, num+1):
    #print(i)
    if num1/2 < i:
        ans.append(1)
        break
    if num%i==0:
        num=int(num/i)
        ans.append(i)
    if num == 1:
        break

print(len(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
primeNum = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999]

pow = 1
time = 0
while True:
    for p in primeNum:
        z = p**pow
        if p <= N:
            if N % z == 0:
                N = int(N / (z))
                time+=1
                print(N)
        else:
            break
    pow+=1
    if pow >= N:
        break

print(time)

Submission status: Wrong Answer

Solution code:
"""
N = list(map(int,input().split()))
S = [str(input()) for _ in range(N)]
S = [list(map(int,list(input()))) for _ in range(h)] 
print(*S,sep="")
"""

import sys
sys.setrecursionlimit(10**6)
input = lambda: sys.stdin.readline().rstrip()
inf = float("inf") # 無限
# 参考URL
# https://qiita.com/LorseKudos/items/9eb560494862c8b4eb56
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
n = int(input())
divisor_list = make_divisors(n)
divisor_list.remove(1)
count = 0

# print(divisor_list)

for divisor in divisor_list[:]:
    # print("n:{} div:{}".format(n,divisor))
    if n%divisor==0:
        count += 1
        n //= divisor
    if n < divisor:
        break
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())

ans = 0

# if N % 2 == 0:
#     i = 1
#     while N % 2**i == 0:
#         N //= 2**i
#         ans += 1
#         i += 1

# if N % 3 == 0:
#     i = 1
#     while N % 3**i == 0:
#         N //= 3**i
#         ans += 1
#         i += 1

# if N % 5 == 0:
#     i = 1
#     while N % 5**i == 0:
#         N //= 5**i
#         ans += 1
#         i += 1

# if N % 7 == 0:
#     i = 1
#     while N % 7**i == 0:
#         N //= 7**i
#         ans += 1
#         i += 1

# if N % 11 == 0:
#     i = 1
#     while N % 11**i == 0:
#         N //= 11**i
#         ans += 1
#         i += 1

# if N % 13 == 0:
#     i = 1
#     while N % 13**i == 0:
#         N //= 13**i
#         ans += 1
#         i += 1

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 set(a)

prime_list = prime_factorize(N)

if prime_list:
    for prime_num in prime_list:
        if N % prime_num == 0:
            i = 1
            while N % prime_num**i == 0:
                N //= prime_num**i
                ans += 1
                i += 1
# print(N)
print(prime_list)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [(i + 1, i + 1) for i in range(1, n)]
    while True:
        p, _ = data[0]
        if limit <= p:
            return prime + data
        prime.append((p, p))
        data = [(e, e) for e, _ in data if e % p != 0]


n = inp()
if n == 1:
    print(0)
    exit()
limit = int(math.sqrt(n)) + 1
prime = get_sieve_of_eratosthenes(limit)
heapq.heapify(prime)
ans = 0
while len(prime):
    i, j = heapq.heappop(prime)
    if i > math.sqrt(n):
        break
    if n % i == 0:
        n //= i
        ans += 1
        heapq.heappush(prime, (i * j, j))
if ans == 0:
    print(1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import copy

N = int(input())

# 素因数分解
# 戻り値: リスト
def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass

pf = prime_factor(N)
if len(pf) == 0:
    print(0)
    exit()

d = {}
for i in pf:
    if i not in d:
        d[i] = 1
        continue
    d[i] += 1

exist_num = []
ans = 0
for k in d.keys():
    for c in range(1, 100):
        if d[k] >= c:
            exist_num.append(k ** c)
            ans += 1
            d[k] -= c

l = []
for k in d.keys():
    if d[k] > 0:
        for _ in range(d[k]):
            l.append(k)

for i in range(1, len(l)+1):
    combs = list(itertools.combinations(l, i))
    if len(combs) > 0:
        for comb in combs:
            d_tmp = d
            n = 1
            for j in comb:
                d_tmp[j] -= 1
                if d_tmp[j] == 0:
                    break
                n *= j
            if n not in exist_num and n != 1:
                ans += 1
                d = d_tmp
                exist_num.append(n)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from math import sqrt
from bisect import bisect_right


def _i(): return int(sys.stdin.readline().strip())


def main():
    n = _i()
    sqn = int(sqrt(n))
    p = [True] * (sqn+1)
    d = {}
    f = True
    for i in range(2, sqn+1):
        if not p[i]:
            continue
        if f and n % i == 0:
            f = False

        if n % i == 0:
            d[i] = 1
        for j in range(i+i, sqn+1, i):
            p[j] = False
    if f and n != 1:
        d[n] = 1

    arr = [(i * (i+1))//2 for i in range(1, 40)]
    for k in d.keys():
        c = 0
        t = k
        while n % t == 0:
            c += 1
            t *= k
        d[k] = bisect_right(arr, c)
    return sum(d.values())


if __name__ == "__main__":
    print(main())

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = 0
if n == 1:
    print(0)
else:
    i = 2
    while True:
        if n == 1:
            print(ans)
            exit()
        elif n % i == 0:
            n /= i
            i += 1
            ans += 1
        else:
            if n == (10 ** 9) + 7:
                i = n
            elif i > n:
                print(ans)
                exit()
            else:
                i += 1

Submission status: Wrong Answer

Solution code:
def factorization(y):
    arr = []
    temp = y
    for i in range(2, int(-(-y**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([y, 1])
    return arr
n=int(input())
if n==1:
  print(0)
  exit()

ans=0
l=factorization(n)
for i,j in l:
    if j<=2:
      ans+=1
    else:
      c=1
      t=1
      while j>0:
        ans+=1
        j-=c
        c+=t
        if j<t:
          break
        t+=1     
print(ans)

Submission status: Wrong Answer

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

N= int(input().rstrip('\n'))
M=N
lim = math.floor(math.sqrt(N))+10
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
      add2 = 3
      while N%(i**add2)==0:
        add += 1
        add2 += add+1
      res += add
if M == N and N>1:
  res += 1
print(res)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
max_n = math.sqrt(N)

if N == 1:
    print(0)
    exit()
count = 0
for i in range(2, int(max_n)+1):
    if N % i == 0:
        count += 1
        N /= i
print(1 if count == 0 else count)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
H = N
count = 0
coun = 0
flag = False
lis = list()
for i in range(2,int(math.sqrt(N))+1):
  if N % i == 0:
    flag = True
    break
if flag == True:
  for i in range(2,int(math.sqrt(N))+10000000):
    if N%i == 0:
      count = 0
      while N%i == 0:
        N = N//i
        count += 1
      lis.append(count)
  M = len(lis)
  for i in range(M):
    su = 1
    for j in range(lis[i]):
      if lis[i] - su >= 0:
        lis[i] -= su
        su += 1
        coun += 1
if flag == True or H == 1:
  print(coun)
else:
  print(1)

Submission status: Wrong Answer

Solution code:
N = int(input())

def make_divisors(n: int):
    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)
    return divisors

divisiors = sorted(make_divisors(N))
ans = 0

# print(divisiors)

for d in divisiors:
    if d == 1:
        continue
    if N % d == 0:
        N //= d
        # print(N, d)
        ans += 1

print(ans)

Submission status: Wrong Answer

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

n = int(input())
div = []

# n の約数を全部並べる
for i in range(1, int(math.sqrt(n))+1):
    if n%i == 0:
        div.append(i)
        div.append(n//i)

div = list(sorted(set(div)))
#print('div =', div)
ans = 0 

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

print(ans)

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

def countstep(a):
    i = 0
    while a>=i+1:
        i += 1
        a -= i
    return i

n = int(input())
a = factorization(n)

if a[0][0]==0:
    print(0)
else:
    count = 0
    for i in range(len(a)):
        count += countstep(a[i][1])
    print(count)

Submission status: Wrong Answer

Solution code:
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 = prime_factorize(N)
B = list(set(A))
lb = len(B)
C = [[] for _ in range(lb)]
D = [0 for _ in range(lb)]
for i in range(lb):
  C[i] = [a for a in A if a == B[i]]
  D[i] = len(C[i])
ans = []
for j in range(len(D)):
  for i in range(1,D[j]):
    if D[j] - i <= 0:
      break
    ans.append(D[j] - i)
print(sum(ans))

Submission status: Wrong Answer

Solution code:
import math

N=int(input())

ans=0
arr=[]

tmp=1

for i in range(int(math.sqrt(N))+5):
    tmp=1
    while N % (i+2) == 0:
        for j in range(tmp):
            if N % (i+2) == 0:
                N=int(N/(i+2))
                flg=True
            else:
                flg=False
        if flg:
            ans+=1
        #print("tmp:"+str(tmp))
        #print("N:"+str(N))
        #print("ans:"+str(ans))
        tmp+=1


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

print(ans)