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:
from math import sqrt, ceil
import fractions
A, B = map(int, input().split())


def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


ans = 1
for i in range(2, fractions.gcd(A, B)+1):
    if A % i == 0 and B % i == 0:
        prime = is_prime(i)

        if prime:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
  
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)

    # divisors.sort()
    return divisors
  
def isPrime(n):
  if n < 2:
    # 2未満は素数でない
    return False
  if n == 2:
    # 2は素数
    return True
  for p in range(2, n):
      if n % p == 0:
        # nまでの数で割り切れたら素数ではない
        return False
  # nまでの数で割り切れなかったら素数
  return True

A,B = list(map(int,input().split()))
 
aaa = []
 
aaa = make_divisors(gcd(A,B))
        
count = 0
 
for i in range(len(aaa)):
    if isPrime(aaa[i]) == True:
        count += 1
        
print(count+1)

Submission status: Time Limit Exceeded

Solution code:
import itertools

def get_divisors(x, y):
  divisors = []
  for i in xrange(1, min(x,y) + 1):
    if x % i == 0 and y % i == 0:
      divisors.append(i)
  return divisors

def main():
  x, y = map(int, raw_input().split())
  if x == 1 or y == 1:
      print(1)
      return

  divisors = get_divisors(x, y)
  results = [set() for _ in xrange(len(divisors))]
  for i, a in enumerate(divisors):
      for b in divisors:
          divs = get_divisors(a, b)
          if len(divs) == 1 and divs[0] == 1:
              results[i].add(b)
          if len(divs) == 2 and divs[0] == 1 and divs[1] == b:
              results[i].add(b)

  answer = len(results[0])
  for s in results:
      if len(s) < answer:
          answer = len(s)
  print(answer)


main()

Submission status: Time Limit Exceeded

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

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

if not 2 in cf_list:
  print(1)
  sys.exit()
ans = [2]
for i in range(1, len(cf_list)):
  flg = True
  for a in ans:
    if cf_list[i] % a == 0:
      flg = False
      break
  if flg:
    ans.append(cf_list[i])
print(len(ans)+1)

Submission status: Time Limit Exceeded

Solution code:
a,b = map(int,input().split())
min_count = min(a,b)
list_d = [1]
count = 0
flag = True
ans = [1]
for i in range(2,min_count+1):
    if a%i==0 and b%i==0:
        list_d.append(i)
a = list_d[1:]

for i in a:
    flag = True
    for j in list_d[1:list_d.index(i)]:
        if i%j == 0:
            flag = False
            break
    if flag:
        ans.append(i)

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def so(n):
    for i in range(3, int(np.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True
A, B = map(int, input().split())
M = np.min([A, B])
n = 1
if (A % 2 == 0) and (B % 2 == 0):
    n = 2
for i in range(3, M, 2):
    if so(i):
        if (A % i == 0) and (B % i == 0):
            n = n + 1
print(n)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
  
a, b = map(int, input().split())
max_d = gcd(a, b)
li = []
for i in range(2, max_d + 1):
  if a % i == 0 and b % i == 0:
    if len(li) == 0:
      li.append(i)
    else:
      ap = 0
      for l in li:
        if i % l == 0:
          ap = 1
          break
      if ap == 0:
        li.append(i)
    
print(len(li) + 1)

Submission status: Time Limit Exceeded

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

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


inputData = input().split()
A, B = [int(x) for x in inputData]
cd = cf(A, B)
ans = set(cd)
list_len_dyn = len(cd)
for i in range(1, len(cd) + 1):
    if i == list_len_dyn:
        break
    to_be_removed = []
    for j in range(i + 1, len(cd)):
        tmp = gcd(cd[i], cd[j])
        if tmp != 1:
            iranai = max(cd[i], cd[j])
            to_be_removed.append(iranai)
    for k in to_be_removed:
        cd.remove(k)
    list_len_dyn = len(cd)
print(len(cd))

Submission status: Time Limit Exceeded

Solution code:
def euc(a,b):
  if a<b:
    a,b=b,a
  while(a%b!=0):
    a,b=b,a%b
    
  return b

one,two = [int(x) for x in input().split()]

aa = euc(one,two)

c=[]
for i in range(1,aa+1):
  if aa%i==0:
  	c.append(i)
    
c1=[(x) for x in c]
c2=[(x) for x in c]

for i in c1:
  for j in c2:
    if i>=j:
      continue
      
    if euc(i,j)!=1 and i!=1 and j!=1:
      if j in c:
        c.remove(j)
      
      
print(len(c))

Submission status: Time Limit Exceeded

Solution code:
import math

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


A,B=map(int,input().split())
#numには入力値の大きいほうの数字が入る
num = (min(A,B))//2

# print("hai",is_prime(4))

primeNum=[]
j=result=0
for i in range(2,num):
    flag=False
    if is_prime(i)==True:
      # print(i)
      if A % i == 0 and B % i == 0:
        flag=True
      if flag==True:
        result+=1
      if min(A,B)+1<i:
        break

print(result+1)

Submission status: Time Limit Exceeded

Solution code:
A,B=map(int,input().split())
if B>A:
   m=B
   B=A
   A=m
while B!=0:
    A,B=B,A%B
large=A
ans=[]
for i in range(2,large+1): 
  if len(ans)>=1:
    if large%i==0: 
        count=0
        for k in ans:
            a=i%k
            if a!=0:
                count+=1
            else:
                count==0
                break
        if count==len(ans):
            ans.append(i)                
  else:
    if large%i==0:
      ans.append(i)

print(len(ans)+1)

Submission status: Time Limit Exceeded

Solution code:
# D - Disjoint Set of Common Divisors
A, B = map(int, input().split())

d = min(A, B)//2
tmp = 0
DP =[1]
if A % 2 == 0 and B % 2 == 0:
    DP.append(2)

for i in range(3,d+1,2):
    if A % i == 0 and B % i == 0:
        for j in range(1,len(DP)):
            if i % DP[j] == 0:
                tmp = 0
                break
            else:
                tmp = 1
        if tmp == 1:
            DP.append(i)

    else:
        pass

print(len(DP))

Submission status: Time Limit Exceeded

Solution code:
import fractions
import heapq

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

cd = []
for i in range(1, int(gcd**0.5)+1):
    if gcd % i == 0:
        heapq.heappush(cd, i)
        i2 = gcd//i
        if i != i2:
            heapq.heappush(cd, i2)

heapq.heappop(cd)

ans = set()
for i in range(len(cd)):
    n = heapq.heappop(cd)
    for j in ans:
        if n**(j-1) % j == 0:
            break
    else:
        ans.add(n)

print(len(ans)+1)

Submission status: Time Limit Exceeded

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

def is_prime(n):
    if n<2:
        return False
    elif n == 2:
        return True
    elif n%2 == 0:
        return False
    
    sqrtNum = int(math.sqrt(n))
    for i in range(3, sqrtNum + 1, 2):
        if n%(i) == 0:
            return False
    return True


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

lis_ab = cf(a,b)
for i in lis_ab:
    if is_prime(i):
        cnt = cnt+1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
A,B=map(int,input().split())
gcd_list=[]
so_list=[]
for num in range(1,gcd(A,B)+1):
    if A%num==0 and B%num==0:
        gcd_list.append(num)
num=len(gcd_list)
if num>4:
    gcd_list=gcd_list[:num//2]
for i in gcd_list:
    flag=0
    if len(so_list)==0:
        so_list.append(i)
    else:
        for num in so_list:
            if num==1:
                continue
            if i%num==0:
                flag=1
                break
        if flag==0:
            so_list.append(i)
print(len(so_list))

Submission status: Time Limit Exceeded

Solution code:
a, b = map(int, input().split())
g = []
def gcd(x,y):
   while(y):
       x,y=y,x%y
   return x
g.append(gcd(a,b))
g.append(1)
if not a%2 and not b%2:
    g.append(2)
for i in range(3,g[0],2):
    if not a%i and not b%i:
        c = True
        for k in range(2, len(g)):
            if gcd(g[k],i)!=1:
                c = False
                break
        if c:
            g.append(i)
c = True
for i in range(1, len(g)):
    if gcd(g[0],g[i])!=1:
        c = False
        break
if c and g[0] != 1:
    print(len(g))
else:
    print(len(g)-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    inputs = input().split()
    inputs = [int(i) for i in inputs]

    a = inputs[0]
    b = inputs[1]

    max_n = max([a, b])

    kouyaku = []

    for n in range(1, int(max_n / 2) + 1):
        if a % n == 0 and b % n == 0:
            kouyaku.append(n)

    so = [1]
    for i in kouyaku:
        if i == 1: continue

        f = True
        for j in kouyaku:
            if j == 1 or i < j: continue
            if i != j and i % j == 0:
                f = False
                break
        if f is True:
            so.append(i)

    print(len(so))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
A, B = map(int, input().split())


def primes(n):
    is_prime = [True] * (n + 1)
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return {i: True for i in range(n + 1) if is_prime[i]}

def common_divisors(a, b):
    while b:
        a, b = b, a % b
    divisors =  [d for d in range(2, a // 2 + 1) if a % d == 0] + [a]
    if not 1 in divisors:
        divisors.append(1) 
    return divisors


d = common_divisors(A, B)
p = set(primes(max(d)))
ans = 0
for x in d:
    if x in p:
        ans += 1
#print(p)
#print(d)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a,b = map(int, input().split())
cf = []
for i in range(1, min(a, b)+1):
	if a%i == 0 and b%i == 0:
		cf.append(i)

cf.sort()
kekka = [1] * len(cf)
for i in range(1, len(cf)-1):
	for j in range(i+1, len(cf)):
		if kekka[i] != 0 and kekka[j] != 0:
			if cf[i]%cf[j] == 0:
				kekka[i] = 0
			elif cf[j]%cf[i] == 0:
				kekka[j] = 0
print(sum(int(i) for i in kekka))

Submission status: Time Limit Exceeded

Solution code:
def prime(n):
    num=[i for i in range(n,1,-1)]
    prime=[]
    p = 2
    while p <=n**0.5 or num:
        p=num.pop()
        prime.append(p)
        num = [i for i in num if i%p != 0]
    return prime
def chk_prime(n):
    for i in range(2,-1*int(-n**0.5//1)):
        if n%i == 0:
            return False
    return True

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

    ans = 1
    if chk_prime(min(a,b)):
        if max(a,b)%min(a,b) == 0 and min(a,b) != 1:
            ans = 2
    else:
        prime_list=prime(int(min(a,b)/2))
        for i in prime_list:
            if a%i == 0 and b%i==0:
                ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
A,B=map(int,input().split())
def is_prime(n):
  if n==1:return False
  for k in range(2, int(math.sqrt(n)) + 1):
    if n%k==0:
      return False
  return True

def cf(a,b):
  cf=[]
  for i in range(1,min(a,b)+1):
    if a%i==0 and b%i==0:
      if is_prime(i):
        cf.append(i)
  return cf
print(len(cf(A,B))+1)

Submission status: Time Limit Exceeded

Solution code:
import math

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

def gcd(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def primelist(n):
    P = [2]
    flag = 0
    for i in range(3,n+1,2):
        for j in range(len(P)):
            if math.sqrt(i) < P[j]:
                break
            else:
                if i%P[j] == 0:
                    flag += 1
                    break
        if flag == 0:
            P.append(i)
        flag = 0
    P.append(1)
    return(P)

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr[-1][0]

N=gcd(A,B)

if N==1:
    print(1)
else:
    ms = factorization(N)
    pl = primelist(ms)
    ans=0
    for i in range(len(pl)):
        if N%pl[i]==0:
            ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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


A,B=map(int,input().split())
#numには入力値の大きいほうの数字が入る
num = (min(A,B))//2

# print("hai",is_prime(4))

primeNum=[]
j=result=0
for i in range(2,num):
    flag=False
    if is_prime(i)==True:
      # print(i)
      while A % i == 0 and B % i == 0:
        A = A // i
        B = B // i
        flag=True
      j+=1
      if flag==True:
        result+=1
      if min(A,B)+1<i:
        break

print(result+1)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

a, b = [int(x) for x in stdin.readline().split()]

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

c = 1
lim = a // 2
n = 0
i = 2
while a > 1 and i <= lim:
    n = 0
    while a % i == 0:
        a //= i
        n += 1
    if n > 0:
        c += 1
    i += 1
if a > 1:
    c += 1

print(c)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
a, b = (int(i) for i in input().split())
ans = 1
x = min(a, b)
if (a % 2 == 0) and (b % 2 == 0):
    ans += 1
if x > 2:

    ix = 1
    primeN = [2]
    for i in range(2,x//2):
        for j in range(len(primeN)):
            if i % primeN[j] == 0:
                break
            else:
                if j == len(primeN) - 1:
                    primeN.append(i)
                    if (a % i == 0) and (b % i == 0):
                        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a, b = map(int,input().split())
 
def cf(x1,x2):
  cf=[]
  for i in range(2,min(x1,x2)+1):
    if x1 % i == 0 and x2 % i == 0:
      cf.append(i)
  return cf
 
List = cf(a, b)
import fractions
 
def check(x1, x2):
  if fractions.gcd(x1, x2) == 1:
    return 1
  else:
    return 0
 
 
Answer = []
for i in range(len(List)):
  if i == 0:
    Answer.append(List[i])
  else:
    checker = 1
    for j in range(len(Answer)):
      if check(Answer[j], List[i]) == 0:
        checker = 0
        break
    if checker == 1:
      Answer.append(List[i])

print(len(Answer)+1)

Submission status: Time Limit Exceeded

Solution code:
#%%

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

#%%

from fractions import gcd


#%%
n = gcd(a, b)

#%%

def y(N):
    l = [1]
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            l.append(i)
            l.append(n / i)
    return l

vv = set(y(n))

def get_prime_and_1_list(N):
    l = [i for i in range(2, N + 1)]
    p = [1]
    while len(l) > 0 and l[0] <= int(N ** 0.5):
        p.append(l[0])
        t = l[0]
        l = [i for i in l if i % t != 0]
    p.extend(l)
    return p

p = set(get_prime_and_1_list(n))

print(len(vv & p))

Submission status: Time Limit Exceeded

Solution code:

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


def coprime(a, b):
    return gcd(a, b) == 1


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


a, b = map(int, input().split())
c = cf(a, b)
len_c = len(c)

d = [1]
for i in range(1, len(c)):
    coprime_flag = True
    for j in range(0, len(d)):
        if not coprime(c[i], d[j]):
            coprime_flag = False
            break
    if coprime_flag:
        d.append(c[i])
print(len(d))

Submission status: Time Limit Exceeded

Solution code:
import fractions
A, B = map(int,input().split())

def is_prime(n):
    for i in range(2, n):  
        if n % i == 0:
            return False
    return True
  
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
gcd = fractions.gcd(A, B)
divisors = make_divisors(gcd)
count = 0
for i in divisors:
  if i % 2==1 or i == 2:
    count += is_prime(i)
print(count)

Submission status: Time Limit Exceeded

Solution code:
def gcd(n,m):
    n1=min(n,m)
    n2=max(n,m)
    if n1==0:
        return n2
    else:
        return gcd(n1, n2%n1)

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

g = gcd(A,B)
count = 1
if g%2==0:
    count=2
    while g%2==0:
        g = g//2

divider = 3

while g > 1:
    if g%divider==0:
        count+=1
        while g%divider==0:
            g = g // divider
    divider += 2
print(count)

Submission status: Time Limit Exceeded

Solution code:
import math

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

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


def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

num = cf(a,b)
num_2 = [1,2]
num_2.extend(num)
if len(num_2) <= 2:
    print(1)
else:
    print(len(num_2))

Submission status: Time Limit Exceeded

Solution code:
A, B= map(int, input().split())
cf=[]

minnum = min(A, B)
maxnum = max(A, B)
numlist = [n+1 for n in range(minnum)]

for i in range(9):
    for num in numlist:
        if num%(i+2)==0:
            numlist.remove(num)

constlist = [2, 3, 5, 7]

for i in constlist:
    if A%i == 0 and B%i == 0:
        cf.append(i)

numlistcp = numlist[:]
for j in numlist:
    if maxnum%j > 0 or minnum%j>0:
        numlistcp.remove(j)
print(len(cf)+len(numlistcp))

Submission status: Time Limit Exceeded

Solution code:
import math
def get_prime(n):
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]






def main():
    A,B = map(int,input().split())
    m = min(A,B)
    prime_count = 0
    lim = m / 2
    if (m > 7) :
        prime_list = get_prime(int(lim))
    else :
        prime_list = [2,3,5,7]
    # print(prime_list)
    # lim = math.sqrt(m)
    # for i in range(1,m+1) :
    for i in prime_list :
        # print(i)
        # if (m % i == 0) :
        if (A % i == 0 and B % i == 0) :
            if (i in  prime_list) :
                # print(i)
                prime_count += 1
    
    # 1を含むので+1しておく
    # a = (prime_count+1) * (prime_count)
    # print(int(a/2))
    # 問題読み違えてた！！！！！！
    print(prime_count+1)
    



# メモ
# 案1
# まずは公約数を列挙する
# 素数かどうかを調べる
# 素数のうち、組み合わせを数える
# 間に合わない気がする
# 案2
# A,Bのちいさいほうの半分までの素数を列挙
# 小さい方の公約数を求める
# nC2を出す
main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

def DSoCD(a, b):
    cd_list = []
    result = []
    for i in range(1,min(a,b)+1):
        if a%i == 0 and b%i == 0:
            cd_list.append(i)
    for idx,n in enumerate(cd_list):
        t = list(filter(lambda x: n%x == 0, cd_list[0:idx+1]))
        if len(t) < 3:
            result.append(n)
    return len(result)

if __name__ == "__main__":
    [A, B] = list(map(int,input().split()))
    print(DSoCD(A,B))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
#        for line in sys.stdin:
#            lines.append(line)
        lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]

    a, b = [int(e) for e in lines[0].split(" ")]

    return (a, b)

def gcd(a, b):

    c = min(a, b)
    d = max(a, b)
    r = 0    
    while True:
        r = d % c
        if r == 0:
            break
        d = c
        c = r

    return c

def lcm(a, b):
    g = gcd(a, b)
    return (a * b) // g

def solve(a, b):

    result = []
    for i in range(2, min(a, b) + 1):
        if a % i == 0 and b % i == 0:
            if debug:
                log(i)

            result.append(i)

    result2 = result.copy()

    i = 0
    while i < len(result2):
        tmp = result2[i]
        new_result2 = result2[:i+1]
        for r in result2[i:]:
            if r % tmp == 0:
                pass
            else:
                new_result2.append(r)
        if debug:
            log("result2    =%s" % result2)
            log("new_result2=%s" % new_result2)

        if len(result2) == len(new_result2):
            break

        result2 = new_result2
        i = i + 1


    return len(result2) + 1


def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r)
    else:
        print("%s" % result)

if __name__ == '__main__':

    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    A,B=map(int, input().split())
    ans={1}
    i = 2
    while (A>=i and B>=i):
        if A % i == 0 and B % i == 0:
            ans.add(i)
            A //= i
            B //= i
        else:
            i += 1
    print(len(ans))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions
import math

A, B = (int(i) for i in input().split())

def is_prime(n):
    if n == 1: return True

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True
MAX = fractions.gcd(A, B)

cf=[]
for i in range(1,MAX+1):
    if A % i == 0 and B % i == 0:
        if is_prime(i):
            cf.append(i)

print(len(cf))