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

Submission attempts (in order):
from collections import Counter
from itertools import combinations
import numpy as np



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 factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

def get_list(counter, index):
    ans = []
    for key, val in sorted(counter.items()):
        if val > index:
            ans += [key] * index
        else:
            ans += [key] * val
    return ans

def choice_min_data(counter, min_num):
    temp = sum(counter.values())
    temp_min_num = 10**12
    co_li = None
    for index in range(1, temp+1):
        flag = False
        to_comb_list = get_list(counter, index)
        for co in combinations(to_comb_list, index):
            check_val = np.prod(co)
            if temp_min_num > check_val > min_num:
                co_li = co
                temp_min_num = check_val
                flag = True
                break

        
        if temp_min_num is not None and flag == False:
            break

    if co_li is None:
        return None, -1
    else:
        # print(co_li, temp_min_num)
        return counter - Counter(co_li), temp_min_num

def main():
    
    
    
    
    
    N = int(input())

    if N <= 1:
        print(0)
        return

    counter = Counter(factorize(N))
    # print(counter)
    ans = 0
    min_num = 0
    while counter is not None:
        counter, min_num = choice_min_data(counter, min_num)
        if min_num == -1:
            break
        ans += 1
    
    print(ans)

if __name__ == "__main__":
    main()


from collections import Counter
from itertools import combinations
import numpy as np



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 get_list(counter, index):
    ans = []
    for key, val in sorted(counter.items()):
        if val >= index:
            ans.append(key)
    return ans

def choice_min_data(counter, min_num):
    temp = sum(counter.values())
    temp_min_num = 10**12
    co_index = None
    for index in range(1, temp+1):
        
        exp_list = get_list(counter, index)
        # print(exp_list)
        if not exp_list:
            break
        for ex in exp_list:
            ex_2 = ex ** index
            if temp_min_num > ex_2 > min_num:
                co_index = [ex, index]
                temp_min_num = ex_2
                
                break

        
        # if co_index is not None and flag == False:
        #     break

    if co_index is None:
        return None, -1
    else:
        # print(co_index, temp_min_num)
        counter[co_index[0]] -= co_index[1]
        return counter, temp_min_num

def main():
    
    
    
    
    
    N = int(input())

    if N <= 1:
        print(0)
        return

    counter = Counter(prime_factorize(N))
    # print(counter)
    ans = 0
    min_num = 0
    while counter is not None:
        counter, min_num = choice_min_data(counter, min_num)
        if min_num == -1:
            break
        ans += 1
    
    print(ans)

if __name__ == "__main__":
    main()


Verdicts: Wrong Answer

Accepted