Problem p02900 (python)

Fixed submission:
# ABC142D - Disjoint Set of Common Divisors
def divisors(n: int) -> set:
    div = set()
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            div.add(i), div.add(n // i)
    return div


def main():
    A, B = map(int, input().split())
    divs = sorted(divisors(A) & divisors(B))
    divs.pop(0)
    groups = set()
    for i in divs:
        if all(i % x for x in groups):
            groups.add(i)
    ans = len(groups) + 1
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
# ABC142D - Disjoint Set of Common Divisors
# from fractions import gcd
from math import gcd


# cf. AtCoder ARC067C, Euler 012
def prime_factorization(x: int) -> dict:
    """
    Prime factorization of a number (trial division)
    
    Args: x (int): a number to be resolved
    Return: ret (dict): {prime factor: power}
    
    e.g., n = 2^a * 3^b -> {2: a, 3: b}
    """
    max_prime = 0
    ret = {}

    # Divide x by 2 as much as possible
    cnt = 0
    while x % 2 == 0:
        x //= 2
        cnt += 1
    if cnt > 0:
        max_prime = 2
        ret[max_prime] = cnt

    # x must be odd -> skip even numbers
    cnt = 0
    for i in range(3, int(x ** 0.5) + 1, 2):
        cnt = 0
        while x % i == 0:
            x //= i
            max_prime = i
            cnt += 1
        if cnt > 0:
            ret[max_prime] = cnt

    # To handle the case when x is prime greater than 2
    if x > 2:
        max_prime = x
        ret[max_prime] = 1
    return ret


def main():
    A, B = map(int, input().split())
    g = gcd(A, B)
    ans = len(prime_factorization(g).keys()) + 1
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
# ABC142D - Disjoint Set of Common Divisors
from fractions import gcd


def divisors(n: int) -> set:
    div = set()
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            div.add(i), div.add(n // i)
    return div


def get_primes(n: int) -> set:
    # return a list of primes <= n
    n += 1
    sieve = [1] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i :: 2 * i] = [0] * ((n - i * i - 1) // (2 * i) + 1)
    return {2} | {i for i in range(3, n, 2) if sieve[i]}


def main():
    A, B = map(int, input().split())
    g = gcd(A, B)
    ans = len(divisors(g) & get_primes(g)) + 1
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
# ABC142D - Disjoint Set of Common Divisors
# from fractions import gcd
from math import gcd


def divisors(n: int) -> set:
    div = set()
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            div.add(i), div.add(n // i)
    return div


def get_primes(n: int) -> set:
    # return a list of primes <= n
    n += 1
    sieve = [1] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i :: 2 * i] = [0] * ((n - i * i - 1) // (2 * i) + 1)
    return {2} | {i for i in range(3, n, 2) if sieve[i]}


def main():
    A, B = map(int, input().split())
    g = gcd(A, B)
    ans = len(divisors(g) & get_primes(g)) + 1
    print(ans)


if __name__ == "__main__":
    main()