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 append_factor(f, p):
    if p not in f:
        f[p] = 0
    f[p] += 1

def factors(n):
    l = int(math.sqrt(n)) + 1
    ret = {}
    while n % 2 == 0:
        append_factor(ret, 2)
        n //= 2
    while n % 3 == 0:
        append_factor(ret, 3)
        n //= 3
    i = 6
    while i*i <= n:
        while n % (i - 1) == 0:
            append_factor(ret, i - 1)
            n //= (i - 1)
        while n % (i + 1) == 0:
            append_factor(ret, i + 1)
            n //= (i + 1)
        i += 6
    if n != 1:
        append_factor(ret, n)

    return ret

def minimum_sum(x):
    # find the minimum integer n where n(n+1)/2 <= x
    # n^2 < n(n+1) <= 2x < (n+1)(n+2) < (n+2)^2

    n = int(math.sqrt(x))
    while (n + 1)*(n + 2) <= 2*x:
        n += 1

    return n

def main():
    N = int(input())
    fs = factors(N)
    # print(fs)
    ans = 0
    for f in fs:
        ans += minimum_sum(fs[f])
    print(ans)

if __name__ == '__main__':
    main()


import math

def append_factor(f, p):
    if p not in f:
        f[p] = 0
    f[p] += 1

def factors(n):
    l = int(math.sqrt(n)) + 1
    ret = {}
    while n % 2 == 0:
        append_factor(ret, 2)
        n //= 2
    while n % 3 == 0:
        append_factor(ret, 3)
        n //= 3
    i = 6
    while i*i <= n + 1:
        while n % (i - 1) == 0:
            append_factor(ret, i - 1)
            n //= (i - 1)
        while n % (i + 1) == 0:
            append_factor(ret, i + 1)
            n //= (i + 1)
        i += 6
    if n != 1:
        append_factor(ret, n)

    return ret

def minimum_sum(x):
    # find the minimum integer n where n(n+1)/2 <= x
    # n^2 < n(n+1) <= 2x < (n+1)(n+2) < (n+2)^2

    n = int(math.sqrt(x))
    while (n + 1)*(n + 2) <= 2*x:
        n += 1

    return n

def main():
    N = int(input())
    fs = factors(N)
    print(fs)
    ans = 0
    for f in fs:
        ans += minimum_sum(fs[f])
    print(ans)

if __name__ == '__main__':
    main()


import math

def append_factors(n, f, p):
    num_factors = 0
    while n % p == 0:
        num_factors += 1
        n //= p
    if num_factors != 0:
        f[p] = num_factors
    return n

def factors(n):
    ret = {}
    n = append_factors(n, ret, 2)
    n = append_factors(n, ret, 3)
    i = 6
    while i*i <= n + 1:
        p1, p2 = i - 1, i + 1
        n = append_factors(n, ret, i - 1)
        n = append_factors(n, ret, i + 1)
        i += 6
    if n != 1:
        ret[n] = 1

    return ret

def minimum_sum(x):
    # find the minimum integer n where n(n+1)/2 <= x
    # n(n+1) <= 2x < (n+1)(n+2)

    n = int(math.sqrt(2 * x))
    while n*(n + 1) > 2*x:
        n -= 1

    return n

def main():
    N = int(input())
    fs = factors(N)
    # print(fs)
    ans = 0
    for f in fs:
        ans += minimum_sum(fs[f])
    print(ans)

if __name__ == '__main__':
    main()


Verdicts: Runtime Error

Wrong Answer

Accepted