Problem:


Score : 400 points

Problem Statement

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.

Constraints

All values in input are integers.

1 \leq A, B \leq 10^{12}

Input

Input is given from Standard Input in the following format:

A B

Output

Print the maximum number of divisors that can be chosen to satisfy the condition.

Sample Input 1

12 18

Sample Output 1

3

12 and 18 have the following positive common divisors: 1, 2, 3, and 6.

1 and 2 are coprime, 2 and 3 are coprime, and 3 and 1 are coprime, so we can choose 1, 2, and 3, which achieve the maximum result.

Sample Input 2

420 660

Sample Output 2

4

Sample Input 3

1 2019

Sample Output 3

1

1 and 2019 have no positive common divisors other than 1.



Sample input:
12 18


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
def main():
    x,y = map(int,input().split())
    tmp = []
    for i in range(2,max(2,min(int(x // 2)+1, int(y //2 )+1))):
        if x % i ==0 and y % i == 0:
            tmp.append(i)
            while True:
                if x % i == 0:
                    x = x//i
                else:
                    break
            while True:
                if y % i == 0:
                    y = y//i
                else:
                    break


    print(len(tmp) + 1)
    # print(tmp)
    # for i,a in enumerate(tmp):
    #     if a < 4:
    #         tmp[i] = 1
    #         continue
    #     j = 2
    #     for j in range(2,int(a**0.5)+1):
    #         if a % j == 0:
    #             tmp[i] = 0
    #             break
    #     if tmp[i] != 0:
    #         tmp[i] = 1
    # print(sum(tmp))
    # print(tmp)

    # cnt = 0
    # # print(tmp)
    # flg = 0
    # for i,a in enumerate(tmp):
    #     # print('out' + str(i) + ' ' + str(a))
    #     if a == 1:
    #         continue
    #     leng = len(tmp)
    #     for j in range(i+1,leng):
    #         # print(j)
    #         # print(tmp)
    #         # print(leng)
    #         if flg == 1:
    #             j -=1
    #         flg = 0
    #         if j >= leng:
    #             break
    #         # print(str(j) + ' ' + str(leng) + ' ' + str(tmp[j]))
    #         if tmp[j] % a == 0:
    #             tmp.pop(j)
    #             leng -=1
    #             j -= 1
    #             # print(tmp)
    #             # print(j)
    #             flg = 1
    #
    #                 # print(j)
    #                 # print(a)
    #

    # print(len(tmp))
    # print(tmp)
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    x,y = map(int,input().split())
    tmp = []
    for i in range(2,max(2,min(int(x // 2), int(y // 2 )))):
        if x % i ==0 and y % i == 0:
            tmp.append(i)
            while True:
                if x % i == 0:
                    x = x//i
                else:
                    break
            while True:
                if y % i == 0:
                    y = y//i
                else:
                    break


    print(len(tmp) + 1)
    # print(tmp)
    # for i,a in enumerate(tmp):
    #     if a < 4:
    #         tmp[i] = 1
    #         continue
    #     j = 2
    #     for j in range(2,int(a**0.5)+1):
    #         if a % j == 0:
    #             tmp[i] = 0
    #             break
    #     if tmp[i] != 0:
    #         tmp[i] = 1
    # print(sum(tmp))
    # print(tmp)

    # cnt = 0
    # # print(tmp)
    # flg = 0
    # for i,a in enumerate(tmp):
    #     # print('out' + str(i) + ' ' + str(a))
    #     if a == 1:
    #         continue
    #     leng = len(tmp)
    #     for j in range(i+1,leng):
    #         # print(j)
    #         # print(tmp)
    #         # print(leng)
    #         if flg == 1:
    #             j -=1
    #         flg = 0
    #         if j >= leng:
    #             break
    #         # print(str(j) + ' ' + str(leng) + ' ' + str(tmp[j]))
    #         if tmp[j] % a == 0:
    #             tmp.pop(j)
    #             leng -=1
    #             j -= 1
    #             # print(tmp)
    #             # print(j)
    #             flg = 1
    #
    #                 # print(j)
    #                 # print(a)
    #

    # print(len(tmp))
    # print(tmp)
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    x,y = map(int,input().split())
    tmp = []
    for i in range(1,max(2,min(int(x // 2), int(y // 2 )))):
        if x % i ==0 and y % i == 0:
            # if x % (i*i) != 0 and y % (i*i) != 0:
            tmp.append(i)
    for i,a in enumerate(tmp):
        if a < 4:
            tmp[i] = 1
            continue
        j = 2
        for j in range(2,int(a**0.5)+1):
            if a % j == 0:
                tmp[i] = 0
                break
        if tmp[i] != 0:
            tmp[i] = 1
    print(sum(tmp))
    # print(tmp)

    # cnt = 0
    # # print(tmp)
    # flg = 0
    # for i,a in enumerate(tmp):
    #     # print('out' + str(i) + ' ' + str(a))
    #     if a == 1:
    #         continue
    #     leng = len(tmp)
    #     for j in range(i+1,leng):
    #         # print(j)
    #         # print(tmp)
    #         # print(leng)
    #         if flg == 1:
    #             j -=1
    #         flg = 0
    #         if j >= leng:
    #             break
    #         # print(str(j) + ' ' + str(leng) + ' ' + str(tmp[j]))
    #         if tmp[j] % a == 0:
    #             tmp.pop(j)
    #             leng -=1
    #             j -= 1
    #             # print(tmp)
    #             # print(j)
    #             flg = 1
    #
    #                 # print(j)
    #                 # print(a)
    #

    # print(len(tmp))
    # print(tmp)
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    x,y = map(int,input().split())
    tmp = []
    for i in range(1,max(2,min(int(x // 2), int(y // 2 )))):
        if x % i ==0 and y % i == 0:
            tmp.append(i)
    cnt = 0
    # print(tmp)
    flg = 0
    for i,a in enumerate(tmp):
        # print('out' + str(i) + ' ' + str(a))
        if a == 1:
            continue
        leng = len(tmp)
        for j in range(i+1,leng):
            # print(j)
            # print(tmp)
            # print(leng)
            if flg == 1:
                j -=1
            flg = 0
            if j >= leng:
                break
            # print(str(j) + ' ' + str(leng) + ' ' + str(tmp[j]))
            if tmp[j] % a == 0:
                tmp.pop(j)
                leng -=1
                j -= 1
                # print(tmp)
                # print(j)
                flg = 1

                    # print(j)
                    # print(a)


    print(len(tmp))
    # print(tmp)
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# ABC-142-D
A, B = map(int, input().split())
ans = 1

#最大公約数
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

def get_prime_number(x):
    if x == 1:
        return []
    max = int(x ** 0.5)
    search_list = [i for i in range(2,x+1)]
    prime_num = []
    while search_list[0] <= max:
        prime_num.append(search_list[0])
        tmp = search_list[0]
        search_list = [i for i in search_list if i % tmp != 0]
    prime_num.extend(search_list)
    return prime_num

#xの素因数を全て出す
def get_prime_factor(x):
    search_list = get_prime_number(x)
    prime_factor_list = []
    for i in search_list:
        if x % i == 0:
            prime_factor_list.append(i)
    return prime_factor_list

gcd_AB = gcd(A, B)
prime = get_prime_factor(gcd_AB)
ans += len(prime)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ABC-142-D
A, B = map(int, input().split())
ans = 1

#x以下の素数を全て出す
def get_prime_number(x):
    if x == 1:
        return []
    max = int(x ** 0.5)
    search_list = [i for i in range(2,x+1)]
    prime_num = []
    while search_list[0] <= max:
        prime_num.append(search_list[0])
        tmp = search_list[0]
        search_list = [i for i in search_list if i % tmp != 0]
    prime_num.extend(search_list)
    return prime_num

#xの素因数を全て出す
def get_prime_factor(x):
    search_list = get_prime_number(x)
    prime_factor_list = []
    for i in search_list:
        if x % i == 0:
            prime_factor_list.append(i)
    return prime_factor_list

A_prime_factor = get_prime_factor(A)
B_prime_factor = get_prime_factor(B)

for item in A_prime_factor:
    if item in B_prime_factor:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def prime(num):
    m = int(math.sqrt(num)) + 1
    for i in range(2, m):
        if num % i == 0:
            return False
    return True

def main():
    gcd = fractions.gcd
    A, B = LI()
    m = gcd(A, B)
    cnt = 1
    for i in range(2, m + 1):
        if not prime(i):
            continue
        if m % i == 0:
            cnt += 1
    print(cnt)
main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from math import sqrt
a,b = map(int, input().split())

sa = set([1])
i = 2
while a>1:
    while a%i==0:
        sa.add(i)
        a //= i
    i += 1

sb = set([1])
i = 2
while b>1:
    while b%i==0:
        sb.add(i)
        b //= i
    i += 1

print(len(sa & sb))

Submission status: Time Limit Exceeded

Solution code:
def judge_prime(n: int) -> bool:
    for i in range(2, n):
        if (n % i == 0):
            return False
    return True


def prime_factorization(value: int) -> list:
    primes = []
    for i in range(2, value):
        while value % i == 0:
            primes.append(i)
            value //= i
        if value == 1:
            break
    return primes


def common_multiple(a: int, b: int) -> list:
    value = 1
    result = []

    while value <= a and value <= b:
        if (a % value == 0 and b % value == 0):
            result.append(value)
        value += 1

    return result


def main():
    A_B = str(input())
    A = int(A_B.split(" ")[0])
    B = int(A_B.split(" ")[1])

    count = 0
    for common in common_multiple(A, B):
        if judge_prime(common):
            count += 1
    print(count)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions

  
def isprime(x):
    count = 1
    for i in range(2,int(x**0.5)+1):
        if x % i == 0:
            count += 1
      
    return count

a,b = map(int,input().split())
g = fractions.gcd(a,b)



ans=0
for i in range(1,int(g**0.5)+1):
    if g % i == 0:
        if isprime(i) == 1:
            ans += 1
        if i != g//i:
            if isprime(g//i) == 1:
                ans += 1
       

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions

  
def isprime(x):
    count = 1
    for i in range(2,int(x**0.5)+1):
        if x % i == 0:
            count += 1
      
    return count

a,b = map(int,input().split())
g = fractions.gcd(a,b)



ans=1
for i in range(2,g+1):
    if g % i == 0:
      
        if isprime(i) == 1:
            ans+=1
       

print(ans)

Submission status: Time Limit Exceeded

Solution code:
A,B=(int(x) for x in input().split())
A=min(A,B)
B=max(A,B)
l=[]
C=0
for i in range(1,A+1):
  if A%i==0 and B%i==0:
    l.append(i)
for j in range(len(l)):
  c=0
  for k in range(2,l[j]):
    if l[j]%k==0:
      c+=1
      break;
  if c==0:
    C+=1
       
print(C)

Submission status: Time Limit Exceeded

Solution code:
A,B=(int(x) for x in input().split())
A=min(A,B)
B=max(A,B)
l=[]
C=0
for i in range(1,A+1):
  if A%i==0 and B%i==0:
    l.append(i)
for j in range(len(l)):
  c=0
  for k in range(2,l[j]):
    if l[j]%k==0:
      c+=1
  if c==0:
    C+=1
       
print(C)

Submission status: Time Limit Exceeded

Solution code:
a, b = map(int, input().split())
a_factorization = set()
b_factorization = set()

while a != 1:
    for i in range(2, a+1):
        if a % i == 0:
            a //= i
            a_factorization.add(i)

while b != 1:
    for i in range(2, b+1):
        if b % i == 0:
            b //= i
            b_factorization.add(i)

a_factorization &= b_factorization
ans = len(a_factorization) + 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(m, n):
    a, b = m, n
    r = a % b
    while r != 0:
        a, b = b, r
        r = a % b
    return b

def divisors(x):
    D = []
    for i in range(1, int(x**0.5) + 1):
        if x % i == 0:
            D.append(i)
            if i != x**0.5:
                D.append(x // i)
    return D


a, b = map(int, input().split())

CD = divisors(gcd(a, b))

ans = 1
for cd in CD:
    if len(divisors(cd)) == 2:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(m, n):
    a, b = m, n
    r = a % b
    while r != 0:
        a, b = b, r
        r = a % b
    return b

def divisors(x):
    D = []
    for i in range(1, int(x**0.5) + 1):
        if x % i == 0:
            D.append(i)
            if i != x**0.5:
                D.append(x // i)
    D.sort()
    return D


a, b = map(int, input().split())

CD = divisors(gcd(a, b))

ans = 1
for cd in CD:
    if len(divisors(cd)) == 2:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
A, B = map(int, input().split())
while B != 0:
  A, B = B, A % B
i, j = 2, 1
while i <= A and A != 1:
  if A % i == 0:
    j += 1
    while A % i == 0:
      A //= i
  i += 1
print(j)

Submission status: Time Limit Exceeded

Solution code:
A, B = map(int, input().split())
while B != 0:
  A, B = B, A % B
i, j = 2, 1
g = A
while i <= g and A != 1:
  if A % i == 0:
    j += 1
    while A % i == 0:
      A //= i
  i += 1
print(j)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

def common_divisors(num1, num2):
    n = gcd(num1, num2)
    out = []

    for i in range(1, n+1):
        if num1 % i == 0 and num2 % i == 0:
            out.append(i)

    return out

def is_prime(num):
   for i in range(2,num//2+1):
       if (num % i) == 0:
           return False
   else:
      return True


num1, num2 = map(int, input().split())
cd = common_divisors(num1, num2)

count = 0
for i in cd:
    if is_prime(i):
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import fractions
a,b=map(int,input().split())
c=list()
cnt=1
if fractions.gcd(a,b)==1:
  print(1)
elif fractions.gcd(a,b)==2:
  print(2)
else:
  for i in range(2,fractions.gcd(a,b)+1):
    if a%i==0 and b%i==0:
      if i==2:
        cnt+=1
      else:
        c.append(i)
  for j in c:
      ok=True
      for k in range(2,j):
        if j%k==0:
            ok=False
      if ok:
        cnt+=1
  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

a,b=map(int,input().split())

def pf(x):
  x2=x
  l=[1]
  if x%2==0:
    l.append(2)
    while x%2==0:
      x=x//2
  for i in range(3,x2,2):
    if x%i==0:
      l.append(i)
    while x%i==0:
      x=x//i
    if x==1:
      break
  if x==x2:
    if x!=1:
      l.append(x)
  return(l)

count=0
n=gcd(a,b)

l=pf(n)

len=len(l)
for i in range(len):
  if  a%l[i]==0:
        count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import math

a,b=map(int,input().split())

def pf(x):
  x2=x
  y=int(x/2)
  l=[1]
  sq_x=math.sqrt(x)
  if x%2==0:
    l.append(2)
    while x%2==0:
      x=x//2
  for i in range(3,y,2):
    if x%i==0:
      l.append(i)
    while x%i==0:
      x=x//i
    if x==1:
      break
  if x==x2:
    if x!=1:
      l.append(x)
  return(l)

count=0
if b>a:
  a,b=b,a

l=pf(b)
len=len(l)
for i in range(len):
  if  a%l[i]==0:
        count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import math

a,b=map(int,input().split())

def pf(x):
  x2=x
  y=int(x/2)
  l=[1]
  sq_x=math.sqrt(x)
  if x%2==0:
    l.append(2)
    while x%2==0:
      x=x//2
  for i in range(3,y,2):
    if x%i==0:
      l.append(i)
    while x%i==0:
      x=x//i
    if x==1:
      break
  if x==x2:
    if x!=1:
      l.append(x)
  return(l)

count=0
if b>a:
  a,b=b,a

l=pf(b)

for i in range(len(l)):
  if l[i]!=0:
    if  a%l[i]==0:
        count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import fractions

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

max_ABdivis = fractions.gcd(A, B)


# divis_A = []
# divis_B = []


def divs(X, li):
    for i in range(1, int(X ** 0.5) + 1):

        if not X % i:
            li.append(i)

            if i != X // i:
                li.append(X // i)
    return li


li = []

# commonDivis = set(divs(A, divis_A)) & set(divs(B, divis_B))
commonDivis = divs(max_ABdivis, li)

for i in reversed(range(1, len(commonDivis) + 1)):
    comb = list(itertools.combinations(commonDivis, i))
    for comb_k in comb:
        if len(comb_k) >= 2:
            pickup2fromComb_k = list(itertools.combinations(comb_k, 2))
            liForPickup2 = [
                [[] for _ in range(2)] for _ in range(len(pickup2fromComb_k))
            ]
            cntTemp = 0
            for j in range(len(pickup2fromComb_k)):
                commonTemp = set(
                    divs(pickup2fromComb_k[j][0], liForPickup2[j][0])
                ) & set(divs(pickup2fromComb_k[j][1], liForPickup2[j][1]))

                if commonTemp != {1}:
                    break

                cntTemp += 1

            if cntTemp == len(pickup2fromComb_k):
                print(len(comb_k))
                break
        else:
            print(1)
            break
    else:
        continue
    break

Submission status: Time Limit Exceeded

Solution code:
#方針...ユークリッドの互除法を用いて2整数が互いに素かどうかを判定する関数を設計
#       O(route n)で2整数の公約数をリストとして出力する関数を設計
import math

def judge_disjoint(a,b):

    while (a!=0 and b!=0):
        if b<a:
            a,b = b,a
        b = b%a
    if (a==1 or b==1):
        return True
    else:
        return False

def common_divisor(a,b):
    ls_a=[]
    ls_b=[]
    A = int(math.sqrt(a))
    B = int(math.sqrt(b))
    for i in range(1,A+1):
        if (a%i==0):
            ls_a.append(i)
            ls_a.append(a//i)
    for i in range(1,B+1):
        if (b%i==0):
            ls_b.append(i)
            ls_b.append(b//i)
    ls = list(set(ls_a) & set(ls_b))
    return ls

A,B = list(map(int,input().split()))
ls = common_divisor(A,B)
ls.sort()
#print(ls)
N = len(ls)

def solve(ls):
    ls2=[1]
    ls.pop(0)

    if (len(ls)!=0):
        ls2.append(ls[0])
        for i in range(1,len(ls)):
            flag = True
            for j in range(i):
                if (ls[i]%ls[j]==0):
                    flag = False
            if flag:
                ls2.append(ls[i])
    return ls2


ans = len(solve(ls))


print(ans)

Submission status: Time Limit Exceeded

Solution code:
#方針...ユークリッドの互除法を用いて2整数が互いに素かどうかを判定する関数を設計
#       O(route n)で2整数の公約数をリストとして出力する関数を設計
#       あとはbit探索
import math

def judge_disjoint(a,b):

    while (a!=0 and b!=0):
        if b<a:
            a,b = b,a
        b = b%a
    if (a==1 or b==1):
        return True
    else:
        return False

def common_divisor(a,b):
    ls_a=[]
    ls_b=[]
    A = int(math.sqrt(a))
    B = int(math.sqrt(b))
    for i in range(1,A+1):
        if (a%i==0):
            ls_a.append(i)
            ls_a.append(a//i)
    for i in range(1,B+1):
        if (b%i==0):
            ls_b.append(i)
            ls_b.append(b//i)
    ls = list(set(ls_a) & set(ls_b))
    return ls

A,B = list(map(int,input().split()))
ls = common_divisor(A,B)
N = len(ls)
ans = 0

for bit in range(2**N):
    candidates=[]
    flag=True
    for i in range(N):
        if(1<<i & bit):
            candidates.append(ls[i])
    for i in range(len(candidates)-1):
        for j in range(i+1,len(candidates)):
            if (not judge_disjoint(candidates[i],candidates[j])):
                flag = False
    if(flag):
        ans = max(ans,len(candidates))
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b):
    if a > b:
        a, b = (b, a)
    while b:
        a, b = b, a % b
    return a


def cf(x1, x2):
    ret = [1]
    gcd_num = gcd(x1, x2)

    i = 2
    while i <= gcd_num:
        if gcd_num % i == 0:
            ret.append(i)
        i += 1

    return ret


def is_prime_number(num):
    if num == 1:
        return False

    i = 2
    while i*i <= num:
        if num % i == 0:
            return False
        i += 1
    return True


def main():
    a, b = map(int, input().split())
    common_divisor_list = cf(a, b)
    # print(common_divisor_list)

    count = 0
    for num in common_divisor_list:
        if is_prime_number(num):
            count += 1

    print(count + 1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def cf(x1, x2):
    ret = []
    for i in range(2, min(x1, x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            ret.append(i)
    return ret


def is_prime_number(num):
    if num == 1:
        return False

    i = 2
    while i*i <= num:
        if num % i == 0:
            return False
        i += 1
    return True


def main():
    a, b = map(int, input().split())
    common_divisor_list = cf(a, b)

    count = 0
    for num in common_divisor_list:
        if is_prime_number(num):
            count += 1

    print(count + 1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math


def cf(x1, x2):
    ret = []
    for i in range(1, min(x1, x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            ret.append(i)
    return ret


def is_prime_number(num):
    if num == 1:
        return False

    i = 2
    while i*i <= num:
        if num % i == 0:
            return False
        i += 1
    return True


def check(num):
    if num == 1:
        return True
    else:
        return is_prime_number(num)


def main():
    a, b = map(int, input().split())
    common_divisor_list = cf(a, b)

    count_set = set()

    for i in range(len(common_divisor_list) - 1):
        for j in range(i+1, len(common_divisor_list)):
            if check(common_divisor_list[i]) and check(common_divisor_list[j]):
                # print(common_divisor_list[i], common_divisor_list[j])
                count_set.add(common_divisor_list[i])
                count_set.add(common_divisor_list[j])

    if len(common_divisor_list) == 1:
        count_set.add(1)

    print(len(count_set))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

divis_A = []
divis_B = []


def divs(X, li):
    for i in range(1, int(X ** 0.5) + 1):

        if not X % i:
            li.append(i)

            if i != X // i:
                li.append(X // i)
    return li


commonDivis = set(divs(A, divis_A)) & set(divs(B, divis_B))

cnt = 0

for i in reversed(range(1, len(commonDivis) + 1)):
    comb = list(itertools.combinations(commonDivis, i))
    for comb_k in comb:
        if len(comb_k) >= 2:
            pickup2fromComb_k = list(itertools.combinations(comb_k, 2))
            liForPickup2 = [
                [[] for _ in range(2)] for _ in range(len(pickup2fromComb_k))
            ]
            cntTemp = 0
            for j in range(len(pickup2fromComb_k)):
                commonTemp = set(
                    divs(pickup2fromComb_k[j][0], liForPickup2[j][0])
                ) & set(divs(pickup2fromComb_k[j][1], liForPickup2[j][1]))

                if commonTemp != {1}:
                    break

                cntTemp += 1

            if cntTemp == len(pickup2fromComb_k):
                print(len(comb_k))
                break
        else:
            print(1)
            break
    else:
        continue
    break

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

divis_A = []
divis_B = []


def divs(X, li):
    for i in range(1, int(X ** 0.5) + 1):

        if not X % i:
            li.append(i)

            if i != X // i:
                li.append(X // i)
    return li


commonDivis = set(divs(A, divis_A)) & set(divs(B, divis_B))

cnt = 0

for i in reversed(range(1, len(commonDivis) + 1)):
    comb = list(itertools.combinations(commonDivis, i))
    for comb_k in comb:
        if len(comb_k) >= 2:
            pickup2fromComb_k = list(itertools.combinations(comb_k, 2))
            liForPickup2 = [
                [[] for _ in range(2)] for _ in range(len(pickup2fromComb_k))
            ]
            cntTemp = 0
            for j in range(len(pickup2fromComb_k)):
                commonTemp = set(
                    divs(pickup2fromComb_k[j][0], liForPickup2[j][0])
                ) & set(divs(pickup2fromComb_k[j][1], liForPickup2[j][1]))

                if commonTemp != {1}:
                    break

                cntTemp += 1

            if cntTemp == len(pickup2fromComb_k):
                print(len(comb_k))
                break
        else:
            print(1)
    else:
        continue
    break

Submission status: Time Limit Exceeded

Solution code:
A,B = map(int,input().split())
import fractions
gcd = fractions.gcd(A,B)
import math
n = math.floor(gcd)
a = [i for i in range(2,n+1)]
soinsu = [1]
while len(a) > 0:
    x = a.pop(0)
    if gcd % x == 0:
        soinsu.append(x)
    y = n//x
    for j in range(1,y+1):
        z = j*x
        if z in a:
            a.remove(z)
ans = len(soinsu)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

# from math import gcd
import fractions

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

if A >= B:
    A, B = B, A

# 小さい方の約数リストを計算
divA = []
for i in range(1, A // 2 + 1):
    if A % i == 0:
        divA.append(i)
divA.append(A)
div = [n for n in divA if B % n == 0]
Ndiv = len(div)

# print(div)
# for n in div:
#     for m in div:
#         if n < m and fractions.gcd(n, m) == 1:
#             print(n, m)

# 深さ優先探索
def dfs(i, S, d):
    selected = div[i]
    S.add(selected)
    depth = d
    for j in range(i + 1, Ndiv):
        if fractions.gcd(div[i], div[j]) == 1:
            flag = True
            for k in S:
                if fractions.gcd(k, div[j]) != 1:
                    flag = False
                    break
            if flag:
                dj = dfs(j, S, d + 1)
                depth = max(depth, dj)
    return depth

ans = dfs(0, set({}), 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from math import sqrt

A, B = map(int, input().split())
C = gcd(A, B)
ans = 1
i = 2
while C > 1:
    if C % i == 0:
        ans += 1
        C //= i
        while C % i == 0:
            C //= i
    i += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions


def main():
    A, B = map(int, input().split())
    n = fractions.gcd(A, B)
    print(num_prime_factor(n))

def num_prime_factor(n):
    
    if n == 1:
        return 1
    
    ret = 1
    cursor = 2
    if n % cursor == 0:
        ret += 1
        n = n // cursor
        while n % cursor == 0:
            n = n // cursor
    
    cursor = 3
    while cursor**2 < n:
        if n % cursor == 0:
            ret += 1
            n = n // cursor
            while n % cursor == 0:
                n = n // cursor
            cursor += 2

    if n != 1:
        ret += 1
        
    return ret

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

a, b = map(int, input().split())

if a > b:
    a, b = b, a

# a_sq = int(math.sqrt(a)) + 1

com_div = []
# for i in range(1, a_sq + 1):
for i in range(1, a):
    if a % i == 0 and b % i == 0:
        com_div.append(i)
if len(com_div) == 1:
    print(1)
    exit()
    
ans = [1]
for i in range(1, len(com_div)):
    flg = 0
    for j in range(1, i):
        if com_div[i] % com_div[j] == 0:
            flg = 1
            break
    if flg == 0:
        ans.append(com_div[i])
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
a,b=map(int,input().split())

def cf(x1,x2):
    cf=[]
    for i in range(1,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            if i%2==0 and i!=2:
                    continue
            cf.append(i)
    return cf

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

L=cf(a,b)
L2=[]
for i in L:
     if is_prime(i):
           L2.append(i)

print(len(L2)+1)

Submission status: Time Limit Exceeded

Solution code:
a,b=map(int,input().split())

def cf(x1,x2):
    cf=[]
    for i in range(1,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            if i%2==0 and i!=2:
                    continue
            cf.append(i)
    return cf

L=cf(a,b)
for i in range(1,len(L)-1):
      for j in range(i+1,len(L)):
            if L[j]%L[i]==0:
                  L.pop(j)
print(len(L))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from fractions import gcd
from itertools import combinations

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

def get_common_divisors(A, B):
    g = gcd(A, B)
    common_divisors = []
    common_divisors.append(g)

    for i in range(1, g):
        if (A % i == 0) and (B % i == 0):
            common_divisors.append(i)

    return common_divisors

common_divisors = get_common_divisors(A, B)
common_divisors.sort()

#print(common_divisors)

viable_divisors = np.ones(len(common_divisors))
# the only viable factors will be primes
# since every non-prime numbe will have a prime factor in the set
# which is divisible by itself. therefore the pair is not coprime
# therefore it suffices to check whether each divisor is prime

for i in range(len(common_divisors)):
    for j in range(1, i):
        if common_divisors[i] % common_divisors[j] == 0:
            viable_divisors[i] = 0

num_coprimes = sum(viable_divisors)

#print(viable_divisors)
print(int(num_coprimes))

Submission status: Time Limit Exceeded

Solution code:
import math
def gcd(a,b):
    if b>a:
        a,b=b,a
    while b:
        a,b=b, a%b
    return a

a,b=map(int,input().split())
x=gcd(a,b)
s=set()
while x>1:
    for i in range(2, min(x+1,int(math.sqrt(x))+2) ):
        while x%i==0:
            x=x//i
            s.add(i)
print(len(s)+1)

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt, ceil

ab = input().split(' ')
a = int(ab[0])
b = int(ab[1])

tmp = b
if a<b:
	tmp = a
	a = b
	b = tmp

while b != 0:
	tmp = b
	b = a%b
	a = tmp

count = 1
if a == 1:
	print(count)
else:
    if a%2 == 0:
        count += 1
        while a%2 == 0:
            a //= 2

    for i in range(3, a+1, 2):
        if a%i == 0:
            count += 1
            while a%i == 0:
                a //= i
            if a == 1:
                break
    print(count)