Problem: Given are positive integers A and B.  Let us choose some number of positive common divisors of A and B.  Here, any two of the chosen divisors must be coprime.  At most, how many divisors can we choose?  Definition of common divisor  An integer d is said to be a common divisor of integers x and y when d divides both x and y.  Definition of being coprime  Integers x and y are said to be coprime when x and y have no positive common divisors other than 1.  Definition of dividing  An integer x is said to divide another integer y when there exists an integer \alpha such that y = \alpha x.

Submission attempts (in order):
import math  
  
A, B = map(int, input().split())

# LL = 10
# dp = [[-1 for x in range(LL)] for _ in range(LL)]
# dp2 = [[0 for x in range(LL)] for _ in range(LL)]

def gcd(a, b):
    # print(a, b)
    if b == 0:
        # print("retval:", a)
        return a
    else:
        
        return gcd(b, a%b)


def is_disjoint(a, b):
    if a < b:
        tmp = b
        b = a
        a = tmp
    d = a % b
    if d != 0 and b % d == 1:
        return True
    else:
        return False

def get_common_divisors(a, b):

    dvs = set()

    n = 0
    d = 0
    if (a>b):
        d = a - b
        n = a
    else:
        d = b-a
        n = b

    i = 1
    while i <= math.sqrt(d): 
        if (d % i == 0 and a%i == 0 and b%i == 0):
            if (d // i == i) : 
                dvs.add(i)
            else: 
                dvs.add(i)
                dvs.add(d//i)
        i = i + 1
    
    return dvs

def get_divisors(n) : 

    dvs = set()
    i = 1
    while i <= math.sqrt(n): 
        if (n % i == 0) : 
            if (n // i == i) : 
                dvs.add(i)
            else : 
                dvs.add(i)
                dvs.add(n//i)
        i = i + 1
    
    return dvs


gcdv = gcd(A,B)
print(gcdv)
DVL = list(get_divisors(gcdv))

DVL.sort(reverse=True)
DVLL = len(DVL)

ans = 0
for i in range(0, DVLL-1):
    for j in range(i+1, DVLL):
        # print(DVL[i], DVL[j])
        if gcd(DVL[i], DVL[j]) != 1:
            break
        else:
            ans += 1
print(ans)


import math  
  
A, B = map(int, input().split())

# LL = 10
# dp = [[-1 for x in range(LL)] for _ in range(LL)]
# dp2 = [[0 for x in range(LL)] for _ in range(LL)]

def gcd(a, b):
    if b == 0:
        return a
    else:
        if dp[a][b] == -1:
            gcd(b, a%b)
        else:
            return dp[a][b]

def is_disjoint(a, b):
    if a < b:
        tmp = b
        b = a
        a = tmp
    d = a % b
    if d != 0 and b % d == 1:
        return True
    else:
        return False

def get_common_divisors(a, b):

    dvs = set()

    n = 0
    d = 0
    if (a>b):
        d = a - b
        n = a
    else:
        d = b-a
        n = b

    i = 1
    while i <= math.sqrt(d): 
        if (d % i == 0 and a%i == 0 and b%i == 0):
            if (d // i == i) : 
                dvs.add(i)
            else: 
                dvs.add(i)
                dvs.add(d//i)
        i = i + 1
    
    return dvs

def get_divisors(n) : 

    dvs = set()
    i = 1
    while i <= math.sqrt(n): 
        if (n % i == 0) : 
            if (n // i == i) : 
                dvs.add(i)
            else : 
                dvs.add(i)
                dvs.add(n//i)
        i = i + 1
    
    return dvs



As = get_divisors(A)
print(As)
Bs = get_divisors(B)
print(Bs)
CDL = list(As & Bs)
print(CDL)

CDLL = len(CDL)
print(CDLL)

num = 0
min_num = 1e15

for i in range(0, CDLL):
    num = 0
    for j in range(i, CDLL):
        if is_disjoint(CDL[i], CDL[j]):
            # dp[CDL[i]][CDL[j]] = 1
            # dp[CDL[j]][CDL[i]] = 1
            num += 1
    if min_num > num:
        min_num = num

print(min_num + 1)


# for l in range(len(CDL)+1):
#     dp2[1][l] = 1

# for l in range(2, len(CDL)+1):
#     for p in range(l, len(CDL)+1):




A, B = map(int, input().split())

import math

def is_prime(x):
    for i in range(2, int(math.sqrt(x))+1):
        if x % i == 0:
            return False

    return True


def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1

    return lower_divisors + upper_divisors[::-1]


def gcd(a, b):

    if a == 0:
        return b
    else:
        return gcd(b%a, a)


da = make_divisors(A)
common_divisors = []

for d in da:
    if B % d == 0:
        common_divisors.append(d)

ans = [1 if is_prime(x) else 0 for x in common_divisors]
print(sum(ans))


Verdicts: Wrong Answer

Wrong Answer

Accepted