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:
import fractions
from itertools import combinations
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
def compromise(x1, x2):
    f = fractions.gcd(x1, x2)
    return f == 1

a, b = map(int, input().split())
cfs = cf(a, b)
club = []
for i in range(len(cfs)):
    if i == 0:
        club.append(cfs[i])
    else:
        flag = True
        for c in club:
            if not compromise(cfs[i], c):
                flag = False
                break
        if flag:
            club.append(cfs[i])
print(len(club))

Submission status: Time Limit Exceeded

Solution code:
import fractions
a, b = map(int, input().split())
l = []
x = fractions.gcd(a, b)
i = 1
# while i * i <= x:
#     if x % i == 0:
#         l.append(i)
#         l.append(x//i)
#     i += 1
# table = list(set(l))
for i in range(1, int(x**0.5)+1):
    if x % i == 0:
        l.append(i)
        if i**2 == x:
            continue
        l.append(x//i)
table = l
ans = []
for i in range(len(table)):
    check = True
    for j in range(2, int(table[i]**0.5)+1):
        if table[i] % j == 0:
            check = False
    if check:
        ans.append(table[i])
print(len(ans))

Submission status: Time Limit Exceeded

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

CommonDivs =[]
for i in range(1, min(A, B)+1): 
    if A%i==B%i==0: 
        CommonDivs.append(i)
        
#print(CommonDivs)

from collections import deque
CommonDivs.reverse()
q = deque(CommonDivs)
ans = [q.pop()]
while len(q) > 0:
    a = q.pop()
    ans.append(a)
    for _ in range(len(q)):
        b = q.pop()
        if b % a != 0:
            q.appendleft(b)
            
print(len(ans))

Submission status: Time Limit Exceeded

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

L = range(2,fractions.gcd(A,B)+1)
# print(list(L))
prime = []

for i in L:
    if (A%i != 0) or (B%i != 0):
        continue

    primecheck = True
    for j in prime:
        if i%j == 0:
            primecheck = False

    if primecheck == True:
        prime.append(i)
prime.append(1)

# print(prime)
print(len(prime))

Submission status: Time Limit Exceeded

Solution code:
def solve(n):
    res = set()
    for i in range(2, n):
        while n % i == 0:
            res.add(i)
            n /= i
    res.add(1)
    return res


A, B = [int(_) for _ in input().split()]
print(len(solve(A) & solve(B)))

Submission status: Time Limit Exceeded

Solution code:
A,B=map(int,input().split())
def cf(x1,x2):
    cf=[]
    cf.append(1)
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf
def gcd(a, b):
  while b!=0:
    a, b = b, a % b
  return a 

mod=cf(A,B)
ans=0
ans_list=[]
ans_list.append(1)
if len(mod)==1 :
  ans=1
else:
  for i in range(1,len(mod)):
    t=0
    for v in range(len(ans_list)):
      t+=1
      if gcd(mod[i],ans_list[v])!=1 :
        break
      if t==len(ans_list):
        ans_list.append(mod[i])
ans=len(ans_list)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
A,B=map(int,input().split())
import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000000)
def gcd(a,b):#最大公約数を返す。Euclid
    if a<b:
        a,b=b,a
    if b==0:
        return a
    return gcd(b,a%b)
c=gcd(A,B)
#print(c)
if c==1:
    print(1)
else:
    sqrtc=int(c**(1/2))
    lf=[0 for i in range(c-1)]#2,3,,,,c
    #print(lf)
    for i in range(sqrtc):
        if lf[i]==0:
            for j in range(2,c//(i+2)+1):
                lf[(i+2)*j-2]=1
    #print(lf)
    ans=1
    for i in range(c-1):
        if lf[i]==0 and c%(i+2)==0:
            ans+=1

    #print(c-sum(lf)+1)
    print(ans)

Submission status: Time Limit Exceeded

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

def gcd(a, b):
	if b == 0:
		return(a)
	else :
		return gcd(b, a % b)
		
a = gcd(A, B)
ctr = 1
gusu = 0
lst = [2]

for i in range(3, a + 1):
	sosu = 1
	for j in range(2, int(math.sqrt(i) + 1)):
		if i % j == 0:
			sosu = 0
			break
	if sosu == 1:
		lst.append(i)

for i in lst:
	if not (gusu == 1 and i % 2 == 0):
		do = 0
		while a % i == 0:
			a /= i
			do = 1
			if a == 1:
				break
		if do:
			ctr += 1
		if do and i == 2:
			gusu = 1
		if a == 1:
			break
		
print(ctr)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	A,B = inputMap()
	ans = 0

	lin = cf(A,B)
	lin.sort()
	ansln =copy.deepcopy(lin)
	ansln.append(1)

	ans = 1
	for i, val in enumerate(lin):
		flg = True
		for j, vol in enumerate(lin):
			if val >= vol:
				continue

			#print("{} {}".format(val,vol))
			ck = cf(val,vol)
			#print(ck)
			if len(ck) == 0:
				pass
			else:
				#print("{} {}".format(val,vol))
				flg = False
				if vol in ansln:
					ansln.remove(vol)
				break

		if flg == True:
			#print("{} {}".format(val,vol))
			ans += 1

	#print(lin)
	print(len(ansln))

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


if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from fractions import gcd
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

# input = sys.stdin.readline


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 check(n, ans):
    for v in n:
        if v in ans and v != 1:
            return False

    return True


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

    ans = []

    nums = make_divisors(gcd(a, b))
    nums.sort()

    for n in nums:
        if check(make_divisors(n), ans):
            ans.append(n)

    print(len(ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
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

a, b = map(int, input().split())
count = 1
for i in range(1,min(a,b)+1):
    if a % i == 0 and b % i == 0:
        if is_prime(i) == True:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
#import sys

#input = sys.stdin.readline

import heapq

def main():
#    h,w,a,b = map(int, input().split())
    a,b=map(int,input().split())
    i=2
    k=1
    c=max(a,b)
    count=1
    if a%2==0 and b%2==0:
        count+=1
    if a%3==0 and b%3==0:
        count+=1
    while i < c:
        i = 6 * k +1
        if a % i == 0 and b % i == 0:
            count += 1
        k += 1
    k = 1
    i = 2
    while i < c:
        i = 6 * k -1
        if a % i == 0 and b % i == 0:
            count += 1
        k += 1
    print(count)
#    for i in range(h):
#            print(aaa)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
a,b=map(int,input().split())
import fractions
n=fractions.gcd(a,b)
import math

# 0以上整数x「未満」の素数をリストに格納して返す
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]
kosuu=0
for i in primes(n+1):
    if n%i==0:
        kosuu+=1
print(kosuu+1)

Submission status: Time Limit Exceeded

Solution code:
def gcd(x,y):
	while y!=0:
		x,y=y,x%y
	return x

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

k = []
r = gcd(a,b)
for i in range(1,r+1):
	if a % i == 0 and b % i == 0:
		if i % 2 != 0 or i == 2:
			k.append(i)

l = []
l.append(k[0])
ans = 1

for i in range(1,len(k)):
	flag = True
	for j in range(len(l)):
		if gcd(k[i],l[j]) != 1:
			flag = False
			break
	if flag:
		l.append(k[i])
		ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

primes = 0

i = 1

def is_prime(n):
    """
    Assumes that n is a positive natural number
    """
    # We know 1 is not a prime number
    if n == 1:
        return True

    i = 2
    # This will loop from 2 to int(sqrt(x))
    while i*i <= n:
        # Check if i divides x without leaving a remainder
        if n % i == 0:
            # This means that n has a factor in between 2 and sqrt(n)
            # So it is not a prime number
            return False
        i += 1
    # If we did not find any factor in the above loop,
    # then n is a prime number
    return True


while i <= min(a,b):
    if a%i == 0 and b%i == 0:
        if is_prime(i):
           primes += 1
    i += 1

print(primes)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
A,B=map(int,input().split())
gcd_ab=gcd(A,B)
ans=1
for i in range(2,gcd_ab+1):
  if gcd_ab == 1:
    break
  elif (gcd_ab/i)%1 == 0:
    ans+=1
    while (gcd_ab/i)%1 == 0:
      gcd_ab = gcd_ab/i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a, b = map(int, input().split())
nums = [x for x in reversed(range(2, min(a, b) + 1)) if a % x == b % x == 0]
res = 1
while nums:
    x = nums.pop()
    res += 1
    nums = [y for y in nums if y % x != 0]
print(res)

Submission status: Time Limit Exceeded

Solution code:
#l=list(map(int, input().split()))
a,b=map(int, input().split())
#l=list(map(int, input().split()))
#n = int(input())

def cf(x1,x2):
    cf =[]
    cf.append(1)
    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(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

ans = 1
temp = cf(a,b)
for i in temp:
    if is_prime(i):
        ans += 1

print (ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions

data = [i for i in range(2, 10**12)]
for d in data:
	data = [x for x in data if (x == d or x % d != 0)]
A, B =list(map(int, input().split()))
D = fractions.gcd(A,B)
x = 1
for d in data:
  if D%d == 0:
    x = x+1
  else:
    pass
print(x)

Submission status: Time Limit Exceeded

Solution code:
def so(n):
  con=0
  for i in range(1,n+1):
    if n%i==0:
      con+=1
    if con>2:
      return -1
  if con==2:
    return 1
  else:
    return -2
x,y = map(int,input().split())
p=[]
q=[]

for i in range(1,x+1):
  if x%i==0:
    p.append(i)
for i in range(1,y+1):
  if y%i==0:
    q.append(i)
s=set(p)
t=set(q)
s1 = s & t
#print(s1)
ans=0

for i in s1:
  if i==1 or i==2 or i==3:
    ans+=1
  elif so(i)==1:
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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

# 全ての公約数を求める
cd_set = set()
cd_max = 0
for i in range(1, min(A, B) + 1):
    if (A % i == 0) and (B % i == 0):
        cd_set.add(i)
        if i > cd_max:
            cd_max = i

# 公約数のうち、1と素数の個数を求める
for i in range(2, int(math.sqrt(cd_max)) + 1):
    for j in range(2, cd_max + 1):
        if (j % i == 0) and (j != i) and (j in cd_set):
            cd_set.remove(j)

print(len(cd_set))

Submission status: Time Limit Exceeded

Solution code:
import copy

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

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


inputData = input().split()
A, B = [int(x) for x in inputData]


cd = [1]

cd.extend(cf(A, B))
ans = set(cd)
# print(cd)
for i in range(0, len(cd) + 1):
    for j in range(i + 1, len(cd)):
        tmp = gcd(cd[i], cd[j])
        # print(str(cd[i]) + ', ' + str(cd[j]) + ' , ' + str(tmp))
        if tmp != 1:
            # print(str(cd[i]) + ', ' + str(cd[j]) + ' , ' + str(tmp))
            ans.discard(max(cd[i], cd[j]))
print(len(ans))

Submission status: Time Limit Exceeded

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

from fractions import gcd

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 get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    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 solve():
    A, B = list(map(int, sys.stdin.readline().split()))
    cd = gcd(A, B)

    if cd == 1:
        print(1)
        return

    ans = 1 # 1
    primes = get_sieve_of_eratosthenes(cd)
    for prime in primes:
        if cd%prime == 0:
            ans += 1

    print(ans)
    return


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, deque
from functools import reduce
import math

input = sys.stdin.readline


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    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())
    k = [1]
    if min(A, B) == 1:
        print(1)
    else:
        prime_list = get_sieve_of_eratosthenes(min(A, B))

        for p in prime_list:
            if A % p == 0 and B % p == 0:
                k.append(p)
        print(len(k))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions
import math

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

def comprime(a, b):
    return fractions.gcd(a, b) == 1

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

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

y = cf(A,B)

so = [1]
cnt = 1
for i in range(1,len(y)-1):
    for j in range(len(so)):
        if comprime(y[i], so[j]) == False:
            break
    else:
        cnt += 1
        so.append(y[i])

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = set(table)
    return table


def common_divisor(x, y):
    xd = divisor(x)
    yd = divisor(y)
    return xd & yd


a, b = map(int, input().split())
cd = sorted(list(common_divisor(a, b)))

cnt = 1
div = {1}
for i in cd[1:]:
    i_d = divisor(i)
    if len(div & i_d) == 1:
        cnt += 1
    div |= i_d

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import fractions
a,b=map(int,input().split())
gcd_ab=fractions.gcd(a, b)
i=2
d={}
ans=1
while(gcd_ab!=1):
    if(gcd_ab%i == 0):
        val=d.get(i, 0)
        val+=1
        d[i]=val
        gcd_ab//=i
    else:
        i+=1
ans+=len(list(d.keys()))
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)
numlist = cf[1:]
for index, numA in enumerate(numlist):
    for numB in numlist[index + 1:]:
        if numB%numA == 0:
            numlist.remove(numB)
print(len(numlist)+1)

Submission status: Time Limit Exceeded

Solution code:
def check(a,b):
    if b == 0 :
        return a
    return check(b,a%b)
def check2(x,y):
    for i in range(2,min(x,y)+1):
        if x % i == 0 and y % i == 0 :
            return i
A,B = map(int,input().split())
memo = [1]
ans = 1
while True :
    if check(A,B)== 1 :
        break
    p = check2(A,B)
    if p not in memo:
        memo.append(p)
        ans += 1
    A = (A//p)
    B = (B//p)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import functools
a,b=map(int,input().split())

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

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

frac=cf(a,b)
n=len(frac)
ans=0
for i in range(n):
  if is_prime(frac[i]):
    ans+=1
print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, deque
from functools import reduce
import math

input = sys.stdin.readline


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError("n is int-type.")
    if n < 2:
        raise ValueError("n is more than 2")
    data = [i for i in range(2, n + 1)]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data


def main():
    A, B = map(int, input().split())
    k = [1]
    if min(A, B) == 1:
        print(1)
    else:
        prime_list = get_sieve_of_eratosthenes(min(A, B))

        for p in prime_list:
            if A % p == 0 and B % p == 0:
                k.append(p)
        print(len(k))


if __name__ == '__main__':
    main()

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

k = cf(a, b)

ans = 0
if len(k) == 0:
  ans = 1
elif len(k) == 1:
  ans = 2
else:
  ans = 2
  for i in range(1, len(k)):
    tmp = k[i]
    for j in range(0, i):
      if (tmp % k[j]) == 0:
        break
    else:
      ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(2**31-1)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def gcd(a,b):
    if a % b == 0:
        return b
    else:
        return gcd(b,a%b)
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    A,B = LMIIS()
    g = gcd(A,B)
    cds = set([1])
    d = 2
    while g != 1:
        if g % d == 0:
            g //= d
            cds.add(d)
        else:
            d += 1
    print(len(cds))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

  return 1
  
a, b = map(int, input().split())
ans = 0
for i in range(1, min(a, b) + 1):
  if a % i == 0 and b % i == 0:
    ans += is_prime(i)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
AB = input().split(' ')
A = int(AB[0])
B = int(AB[1])
 
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)
    cf.insert(0,1)
    return cf
 
def check_cf(x1,x2):
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            return False
    return True
candidate = cf(A,B)
decided_list = [candidate[0]]
 
for i in range(1,len(candidate)):
    flag = True
    for s in range(2,candidate[i]):
        if candidate[i]%s == 0:
            flag = False
            break
    if flag:
        decided_list.append(candidate[i])
print(len(decided_list))

Submission status: Time Limit Exceeded

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

while A != 0 and B != 0:
  if A < B:
    B = C
  else:
    A = C
  C = abs(A-B)

i = 2
ans = 1
while C > 1:
  if C%i == 0:
    ans += 1
    while C%i == 0:
      C //= i
  i += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

G = fractions.gcd(A, B)

res = 1

i = 2
while G > 1:
    if G % i == 0:
        res += 1
        while G % i == 0:
            G /= i
    else:
        if i == 2:
            i += 1
        else:
            i += 2

print(res)

Submission status: Time Limit Exceeded

Solution code:
A, B = map(int, input().split())
num = list()
num.append(1)
ans = 1

for i in range(2, A):
    if A%i == 0 and B%i == 0:
        for j in num:
            if i % j == 0 and j!=1:
                break
        else:
            num.append(i)
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def d(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

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

ad = set(d(a))
bd = set(d(b))

cd = ad & bd

cnt = 0

for i in cd:
    if len(d(i)) == 2:
        cnt += 1

print(cnt+1)

Submission status: Time Limit Exceeded

Solution code:
import fractions

a, b = map(int, input().split())
l = []
x = fractions.gcd(a, b)
i = 1
while i * i <= x:
    if x % i == 0:
        l.append(i)
        l.append(x//i)
    i += 1
table = list(set(l))
ans = []
for i in range(len(table)):
    check = True
    for j in range(2, int(table[i]**0.5)+1):
        if table[i] % j == 0:
            check = False
    if check:
        ans.append(table[i])
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
a,b = map(int,input().split())
s = set()
for x in range(2, min(a,b)+1):
    if not a%x and not b%x:
        flag = 0
        for z in s:
            if not x%z:
                flag +=1
                break
        if not flag:
            s.add(x)
print(len(s)+1)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a,b):
	if a==0:
		return(b)
	return(gcd(b%a,a))
a,b=map(int,input().split())
g=gcd(a,b)

divide=2
ans=1
while(g!=1 and g>=divide):
	if g%divide==0:
		ans+=1
		while(g%divide==0):
			g//=divide
	divide+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a,b = map(int,input().split())
yakusuu = []
ans = 1
for i in range (2,min(a,b)+1):
         if a % i == 0 and b% i == 0:
                  yakusuu.append(i)
for j in range(len(yakusuu)):
         for k in range(2,yakusuu[j]):
                  if yakusuu[j] % k == 0:
                           break
         else:
                  ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a,b = map(int,input().split())
ans = 1
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(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

x = cf(a,b)
for i in (x):
    if is_prime(i)==True:
        ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=list(map(int,input().split()))
n.sort()
ans=1
k=n[0]
for i in range(n[0]-1):
    if n[0]%(i+2)==0 and n[1]%(i+2)==0:
        ans+=1
        while n[0]%(i+2)==0:
            n[0]=n[0]//(i+2)
print(ans)

Submission status: Time Limit Exceeded

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

cands = set()

for i in range(2, min(a, b) + 1):
    if a % i != 0 or b % i != 0:
        continue
    if not any([i % x == 0 for x in cands]):
        cands.add(i)

print(len(cands) + 1)

Submission status: Time Limit Exceeded

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

yakusu_list = []
for i in range(2, min(A,B)+1):
  if A%i==0 and B%i==0:
    yakusu_list.append(i)
i=0
while i<len(yakusu_list):
  koho = yakusu_list[i]
  for k in yakusu_list[i+1:]:
    if k%koho==0:
      yakusu_list.remove(k)
  i += 1
yakusu_list.append(1)

print(len(yakusu_list))

Submission status: Time Limit Exceeded

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

glst = []
tmp = gcd(A, B)
for i in range(1, (tmp // 2) + 1):
    if tmp % i == 0:
        glst.append(i)
glst.append(tmp)
cnt = 0
for i in range(1, len(glst) + 1):
    cntF = True
    for j in range(i + 1, len(glst) + 1):
        if gcd(glst[-i], glst[-j]) != 1:
            cntF = False
            break

    if cntF:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
from itertools import combinations


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

    return True


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

a_li = [1]
b_li = [1]
div = 2

while a != 1 or b != 1:
    if is_prime(div):
        cnt = 0
        while a % div == 0:
            a //= div
            cnt += 1
        a_li.append(cnt)

        cnt = 0
        while b % div == 0:
            b //= div
            cnt += 1
        b_li.append(cnt)

    if div == 2:
        div += 1
    else:
        div += 2

ans = 0
for ae, be in zip(a_li, b_li):
    if ae and be:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(2**31-1)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def gcd(a,b):
    if a % b == 0:
        return b
    else:
        return gcd(b,a%b)
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    A,B = LMIIS()
    g = gcd(A,B)
    cds = [1]
    d = 2
    while g != 1:
        if g % d == 0:
            g //= d
            if cds[-1] != d:
                cds.append(d)
        else:
            d += 1
    print(len(cds))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

import sys
# input = sys.stdin.readline
sys.setrecursionlimit(100000)
MOD = 10 ** 9 + 7

#N = int(input())
#A = [int(x) for x in input().split()]
#V = [[0] * 100 for _ in range(100)]
def gcd(x, y):
    while (y):
        x, y = y, x % y
    return x


def divisor_list(n):
    # ret = set()
    ret = dict()
    ret[1] = 1
    i=2
    while n!=1:
        while n % i == 0:
            ret[i] = ret.get(i,0) + 1
            n /= i
        i+=1
    return ret

A,B = [int(x) for x in input().split()]
dA = divisor_list(A)
dB = divisor_list(B)

cm = set(dA.keys()).intersection(set(dB.keys()))

print(len(cm))

Submission status: Time Limit Exceeded

Solution code:
import fractions

a,b = map(int,input().split())
n = fractions.gcd(a,b)
if n ==1:
    print(1)
else:
    thre = n
    l = [1]
    for i in range(n):
        if thre%(i+2)==0:
            l.append(i+2)
            while thre%(i+2)==0:
              thre = thre//(i+2)
        if i>thre:
            break
    print(len(l))

Submission status: Time Limit Exceeded

Solution code:
def div(n, m):
  if n > m:
    n = m
  d = []
  for i in range(2, n+1):
    if n % i == 0 and m % i == 0:
      for j in d:
        if i % j == 0:
          break
      else:
        d.append(i)
  return d

a, b = map(int, input().split())
lc = div(a,b)
print(len(lc) + 1)

Submission status: Time Limit Exceeded

Solution code:
import math
import queue
import bisect
import heapq

mod = 1e9+7

def swap(a,b):
    return (b,a)

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

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

def prime_num(a):
    pn = [2]
    for i in range(3,a):
        prime = True
        for j in pn:
            if i%j==0:
                prime = False
        if prime:
            pn.append(i)
    return pn

def main():
    a,b = map(int,input().split())
    div_a = divisors(a)
    div_a.sort()
    div_b = divisors(b)
    div_b.sort()
    g = []
    for i in div_a:
        if i!=2 and i%2==0:
            continue
        if i in div_b:
            g.append(i)
    pn = prime_num(max(g)+1)
    ans = 1
    for i in g:
        if i in pn:
            ans += 1
    print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

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

def is_prime(q):
    q = abs(q)
    if q == 1: return True
    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())
lst = cf(A,B)

res = len([i for i in lst if is_prime(i)])

print(res)