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):
#!/usr/bin/env python3
import sys
from random import randint
from math import gcd


def solve(N: int):
    
    
    
    
    n = N
    ds = make_divisors(n)
    print(ds)
    used = []
    while(True):
        count = len(used)
        for d in ds:
            if d in used:
                continue
            p, k = primePower(d)
            print(p)
            if p == 0:
                continue
            n /= d
            used.append(d)
            break

        if count == len(used):
            print(count)
            return
    return


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)

    
    return divisors


def findWitness(n, k=5): # miller-rabin
    s, d = 0, n-1
    while d % 2 == 0:
        s, d = s+1, d/2
    for i in range(k):
        a = randint(2, n-1)
        x = pow(a, d, n)
        if x == 1 or x == n-1: continue
        for r in range(1, s):
            x = (x * x) % n
            if x == 1: return a
            if x == n-1: break
        else: return a
    return 0


def primePower(n):
    def checkP(n, p):
        k = 0
        while n > 1 and n % p == 0:
            n, k = n / p, k + 1
        if n == 1: return p, k
        else: return 0, 0

    if n % 2 == 0: return checkP(n, 2)
    q = n
    while True:
        a = findWitness(q)
        if a == 0: return checkP(n, q)
        d = gcd(pow(a,q,n)-a, q)
        if d == 1 or d == q: return 0, 0
        q = d


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


#!/usr/bin/env python3
import sys
from random import randint
from math import gcd


def solve(N: int):
    
    
    
    
    n = N
    ds = make_divisors(n)
    used = []
    for d in ds:
        count = len(used)
        if d in used:
            continue
        
        for i in range(20**6):
            if not is_prime(i):
                continue
            
            for j in range(50):
                if n == i ** j:
                    used.append(d)
                    n /= d
                    break
            if count < len(used):
                break
    print(len(used))

    # while(True):
    #     count = len(used)
    
    #         if d in used:
    #             continue
    
    #         print(p)
    #         if p == 0:
    #             continue
    #         n /= d
    #         used.append(d)
    #         break

    #     if count == len(used):
    #         print(count)
    #         return
    return


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)

    
    return divisors


def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


#!/usr/bin/env python3
import sys


def solve(N: int):
    
    
    
    

    def f(x):
        cnt = 0
        for i in range(1, x + 1):
            x -= i
            if x < 0:
                break
            cnt += 1
        return cnt

    print(sum([f(p[1]) for p in factorize(N)]))
    return


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


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


Verdicts: Time Limit Exceeded

Wrong Answer

Accepted