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):
def prime_list(lst, limit):
    for num in range(3, limit, 2):
        if num ** 2 > limit:
            break
        # is_prime(num, lst)
        flag = True
        for p_num in lst:
            if (p_num * p_num > num):
                break
            else:
                if (num % p_num == 0):
                    flag = False
                    break
        if flag:
            lst.append(num)


def main():
    n = int(input())
    lst = [2]
    prime_list(lst, n)
    # print(lst)

    lst2 = []
    for i in lst:
        mul_sum = i
        
        tmp = i
        while mul_sum < n:
            tmp *= i
            lst2.append(tmp)
            mul_sum *= tmp

    # print(lst2)
    lst.extend(lst2)
    lst.sort()
    lst.append(n)

    if n == 1:
        print(0)
        exit()

    cnt = 0
    for i in lst:
        n, m = divmod(n, i)

        if m == 0:
            cnt += 1
        else:
            n = n * i + m
            break
        if i < n:
            break
    else:
        if n != 0:
            cnt += 1

    print(cnt)


if __name__ == '__main__':
    main()


from collections import defaultdict
import decimal
import sys
input = sys.stdin.readline


def prime_factor_count(n):
    def count(n, i):
        cnt = 0
        while n % i == 0:
            cnt += 1
            n //= i
        return n, cnt

    d = {}
    if n == 1:
        return d

    n, cnt = count(n, 2)
    d[2] = cnt
    print(d, n)

    lst = [2]
    for num in range(3, int(n ** 0.5) + 1, 2):
        if n == 1:
            break
        for p_num in lst:
            if num % p_num == 0:
                break
            elif p_num * p_num > num:
                lst.append(num)
                n, cnt = count(n, num)
                d[num] = cnt
                break
    else:
        if n != 1:
            d[n] = 1
    return d



def main():
    n = int(input())
    d = prime_factor_count(n)

    cnt = 0
    tmp_n = 0
    for k, v in d.items():
        exp_cnt = 1
        while 1:
            if exp_cnt > v:
                break
            else:
                if tmp_n % (tmp_exp := k ** exp_cnt) == 0:
                    tmp_n //= tmp_exp
                    cnt += 1
                    v -= exp_cnt
                    exp_cnt += 1
    else:
        if n == tmp_n:
            cnt += 1
    print(cnt)


if __name__ == '__main__':
    main()


import sys
input = sys.stdin.readline


def prime_factor_count(n):
    def count(n, p):
        cnt = 0
        while n % p == 0:
            n //= p
            cnt += 1
        np_cnt = 1
        while (cnt := cnt - np_cnt) >= 0:
            np_cnt += 1
        return n, np_cnt - 1

    n, cnt = count(n, 2)

    if n == 1:
        return cnt

    for i in range(3, int(n ** 0.5) * 1, 2):
        n, tmp_cnt = count(n, i)
        cnt += tmp_cnt
        if n == 1:
            break
    else:
        cnt += 1

    return cnt


def main():
    n = int(input())
    ans = prime_factor_count(n)
    print(ans)


if __name__ == '__main__':
    main()


Verdicts: Wrong Answer

Wrong Answer

Accepted