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 prime_factorization(m: int) -> dict:
    """
    素因数分解
    """
    if m == 1:
        return {1: 1}

    pf = {}
    if m % 2 == 0:
        while m % 2 == 0:
            m //= 2
            pf[2] = pf.get(2, 0) + 1
    p = 3
    while p * p <= m:
        if m % p == 0:
            m //= p
            pf[p] = pf.get(p, 0) + 1
        else:
            p += 2
    if m != 1:
        pf[m] = pf.get(m, 0) + 1
        
    return pf

def get_all_cd(m: int) -> list:    
    """
    全ての約数を探す
    """ 
    def find_cd(m, i, pf_lst, cd_lst):
        """
        割れるかどうかの確認
        """
        if m % i != 0:
            return
        else:
            m //= i
            if m in cd_lst:
                return
            else:
                cd_lst.append(m)
                for i in pf_lst:
                    find_cd(m, i, pf_lst, cd_lst)

    pf = prime_factorization(m)
    cd_lst = [m]
    for i in pf.keys():        
        find_cd(m, i, pf.keys(), cd_lst)    

    return sorted(cd_lst)

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

s_lst = set(get_all_cd(A)) & set(get_all_cd(B))
ans_lst = [1]
for i in s_lst:
    if i == 1:
        continue
    p = get_all_cd(i)
    if len(p) == 2:
        ans_lst.append(p[1])
        
print(len(ans_lst))

Submission status: Time Limit Exceeded

Solution code:
import sys

gcd_memo = {}

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

def gcd(x, y):
    if x > y:
        x,y = y,x
    if (x,y) in gcd_memo:
        return (gcd_memo[(x,y)])
        
    z = y % x
    if z == 0:
        return x

    ret = gcd(x, z)
    gcd_memo[(x,y)] = ret
    return ret

my_gcd = gcd(A, B)

if my_gcd == 1:
    print(1)
    sys.exit(0)

ans_list = [1]
if my_gcd % 2 == 0:
    ans_list.append(2)
    while my_gcd % 2 == 0:
        my_gcd //= 2

for i in range(3, my_gcd+1, 2):
    hit_flag = False
    while my_gcd % i == 0:
        my_gcd //= i
        hit_flag = True
    if hit_flag:
        ans_list.append(i)
    if my_gcd <= i:
        break
print(len(ans_list))

Submission status: Time Limit Exceeded

Solution code:
import sys

gcd_memo = {}

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

def gcd(x, y):
    if x > y:
        x,y = y,x
    if (x,y) in gcd_memo:
        return (gcd_memo[(x,y)])
        
    z = y % x
    if z == 0:
        return x

    ret = gcd(x, z)
    gcd_memo[(x,y)] = ret
    return ret

my_gcd = gcd(A, B)

if my_gcd == 1:
    print(1)
    sys.exit(0)

ans_list = [1]
if my_gcd % 2 == 0:
    ans_list.append(2)
    while my_gcd % 2 == 0:
        my_gcd //= 2

for i in range(3, my_gcd+1, 2):
    hit_flag = False
    while my_gcd % i == 0:
        my_gcd //= i
        hit_flag = True
    if hit_flag:
        ans_list.append(i)
    if my_gcd == i:
        break
print(len(ans_list))

Submission status: Time Limit Exceeded

Solution code:
gcd_memo = {}

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

def gcd(x, y):
    if x > y:
        x,y = y,x
    if (x,y) in gcd_memo:
        return (gcd_memo[(x,y)])
        
    z = y % x
    if z == 0:
        return x

    ret = gcd(x, z)
    gcd_memo[(x,y)] = ret
    return ret

my_gcd = gcd(A, B)

num_list = [i for i in range(3, my_gcd + 1, 2) if A % i ==0 and B % i == 0]
num_list.insert(0,1)
if A % 2 == 0 and B % 2 == 0:
    num_list.insert(1,2)

ans_list = []

i = 0
while i < len(num_list):
    j = i+1
    while j < len(num_list):
        if gcd(num_list[j], num_list[i]) != 1:
            num_list.pop(j)
            continue
        j += 1
    i += 1
print(len(num_list))

Submission status: Time Limit Exceeded

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

def gcd(x, y):
    if x > y:
        x,y = y,x
    z = y % x
    if z == 0:
        return x
    return gcd(x, z)

my_gcd = gcd(A, B)

num_list = [i for i in range(3, my_gcd + 1, 2) if A % i ==0 and B % i == 0]
num_list.insert(0,1)
if A % 2 == 0 and B % 2 == 0:
    num_list.insert(1,2)
    
ans_list = []

i = 0
while i < len(num_list):
    j = i+1
    while j < len(num_list):
        if gcd(num_list[j], num_list[i]) != 1:
            num_list.pop(j)
            continue
        j += 1
    i += 1
print(len(num_list))

Submission status: Time Limit Exceeded

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

def gcd(x, y):
    if x > y:
        x,y = y,x
    z = y % x
    if z == 0:
        return x
    return gcd(x, z)

my_gcd = gcd(A, B)

num_list = [i for i in range(1, my_gcd + 1) if A % i ==0 and B % i == 0]
ans_list = []

i = 0
while i < len(num_list):
    j = i+1
    while j < len(num_list):
        if gcd(num_list[j], num_list[i]) != 1:
            num_list.pop(j)
            continue
        j += 1
    i += 1
print(len(num_list))

Submission status: Time Limit Exceeded

Solution code:
A,B=map(int,input().split())
def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1] and n%i==0]
    return is_prime, table
_, A_cf = sieve(A)
_, B_cf = sieve(B)
A_cf = set(A_cf)
B_cf = set(B_cf)
print(len(A_cf&B_cf)+1)

Submission status: Time Limit Exceeded

Solution code:
a,b=map(int,input().split())
import math
x=min([a,b])
x=math.sqrt(x)
n=2
ans=1
while n <= x:
	j=True
	i=2
	while i < n:
		if n%i==0:
			j=False
		i=i+1
	if j and a%n==0 and b%n==0:
		ans=ans+1
	n=n+1        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
def get_divisor(num):
	return [i for i in range(1,num+1) if num % i == 0]

def get_common(num1, num2):
	list_a = get_divisor(num1)
	list_b = get_divisor(num2)
	return [i for i in list_a if i in list_b]

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


A,B = list(map(int,input().split()))[:2]
common = get_common(A,B)
c_prime = [p for p in common if prime_ch(p)]
print((len(c_prime)+1))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

m = gcd(A, B)
pf = []
for i in range(2, m+1):
    if m % i == 0:
        pf.append(i)
    while m % i == 0:
        m //= i
if m != 1:
    pf.append(m)

print(len(pf) + 1)

Submission status: Time Limit Exceeded

Solution code:

a,b = map(int,input().split())
def gcd(x,y):
    if y == 0:
        return x
    else:
        return gcd(y,x%y)
def waru(max_gcd,x):
    if max_gcd%x != 0:
        return max_gcd
    else:
        return waru(max_gcd/i,x)

count = 0
max_gcd = gcd(a,b)

for i in range(2,max_gcd+1):
    if i > max_gcd:
        break
    if max_gcd%i == 0:
        count += 1
        max_gcd = waru(max_gcd,i)
print(count+1)

Submission status: Time Limit Exceeded

Solution code:

a,b = map(int,input().split())
def gcd(x,y):
    if y == 0:
        return x
    else:
        return gcd(y,x%y)
def waru(max_gcd,x):
    if max_gcd%x != 0:
        return max_gcd
    else:
        return waru(max_gcd/i,x)

count = 0
max_gcd = gcd(a,b)

for i in range(2,max_gcd+1):
    if max_gcd%i == 0:
        count += 1
        max_gcd = waru(max_gcd,i)
print(count+1)

Submission status: Time Limit Exceeded

Solution code:
import math
a,b = map(int ,input().split())
count = 0
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)
#print(list)                                                                  \
                                                                               
def is_prime(n):
    if n == 1: return False

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

    return True

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

print(count+1)

Submission status: Time Limit Exceeded

Solution code:
import math
a,b = map(int ,input().split())
count = 0
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)
#print(list)                                                                  \
                                                                               
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

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

print(count+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from fractions import gcd
a, b = map(int, input().split())
n = int(max(a, b)**(1/2)) + 1
prime_num_cnt = [0]*(n + 1)
prime_num = []
for i in range(2, n+1):
    if prime_num_cnt[i] == 0:
        prime_num.append(i)
        tmp = i
        for j in range(1, n):
            if tmp*j > n:
                break
            prime_num_cnt[tmp*j] = 1


g = gcd(max(a, b), min(a, b))
cnt = Counter()
m = 2
while m <= g:
    while g % m == 0:
        g //= m
        cnt[m] += 1
    m += 1

print(len(cnt) + 1)

Submission status: Time Limit Exceeded

Solution code:
import math
A, B = (int(x) for x in input().split())
ls = []
disj = []

for i in  range(1,int(min(A,B)/2)+2):
    if A%i==B%i==0:
        ls.append(i)

def isDisj(n, disj):
    for i in disj:
        if i != 1:
            if n % i == 0:
                return False
    return True

disj.append(ls[0])
        
for i in range(len(ls)):
    if ls[i] != 1:
        if isDisj(ls[i], disj) == True:
            disj.append(ls[i])

print(len(disj))

Submission status: Time Limit Exceeded

Solution code:
import math
A, B = (int(x) for x in input().split())
ls = []
disj = []

for i in  range(1,int(min(A,B)/2)+2):
    if A%i==B%i==0:
        ls.append(i)

def isDisjoint(n):
    if n == 1:
        return True
    if n == 2:
        return True
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True
    
for i in ls:
    if isDisjoint(i) == True:
        disj.append(i)
        
print(len(disj))

Submission status: Time Limit Exceeded

Solution code:
def func():
    a,b = (int(i) for i in input().split())
    if(a>b):
        a,b = b,a
    ans = 1
    
    if(a%2==0 and b%2==0):
        ans += 1
       
    for j in range(3,a+1,2):
        if(a%j==0 and b%j==0):
            a = a // j
            b = b // j
            ans += 1
            
    return ans


print(func())

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
A,B=map(int,input().split())
s=[]

for i in range(1,max(A,B)+1):#因数分解
    if A%i==0 and B%i==0:
        s.append(i)
        #print(i)
        for j in range(1,len(s)-1):
            if s[-1]%s[j]==0:
                #print(s[-1],s[j])
                s.pop(-1)
                break
s=list(set(s))
#print(s)
print(len(s))

Submission status: Time Limit Exceeded

Solution code:
import math
a, b = map(int, input().split())
divisors = [1]
for i in range(2, min(a, b)):
    while a % i == 0 and b % i == 0:
        a = a // i
        b = b // i
        if i not in divisors:
            divisors.append(i)
print(len(divisors))

Submission status: Time Limit Exceeded

Solution code:

import math


def primeFactorisation(x):
    res = set([1])
    while x % 2 == 0:
        res.add(2)
        x = x//2
    for i in range(3, int(math.sqrt(x)) + 1, 2):
        while (x % i == 0):
            res.add(i)
            x = x // i
    if (x > 2):
        res.add(x)
    return res


if __name__ == "__main__":
    a, b = map(int, input().split())
    divisors = set([x for x in range(1, max(a, b)) if (a % x == 0 and b % x == 0)])
    coPrimedivisors = set([1])
    for x in divisors:
        coPrimedivisors = coPrimedivisors.union(set(primeFactorisation(x)))
    print(len(coPrimedivisors))

Submission status: Time Limit Exceeded

Solution code:
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a

#targetまでの素数の数
import math
def sieve_of_eratosthenes2(target):
    dest = math.ceil(math.sqrt(target))
    target_list = [i for i in range(2, target//2+1) if target%i==0]
    prime_num = 0
 
    while True:
        num_min = target_list[0]
        if num_min > dest:
            prime_num += len(target_list)
            break
        prime_num += 1        
        target_list = [i for i in target_list if i%num_min!=0]
        if target_list==[]:
            break
 
    return prime_num

import random
def is_prime(q, k=50):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q % 2 == 0:
        return False

    d = (q - 1) >> 1
    while d & 1 == 0:
        d >>= 1
    for i in range(k):
        a = random.randint(1, q - 1)
        t = d
        y = pow(a, t, q)
        while t != q - 1 and y != 1 and y != q - 1:
            y = pow(y, 2, q)
            t <<= 1
        if y != q - 1 and t & 1 == 0:
            return False
    return True

a, b = map(int, input().split())
gcd = xgcd(a, b)
if gcd == 1:
    print(1)
elif is_prime(gcd):
    print(2)
else:
    ans = sieve_of_eratosthenes2(gcd)    
    print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a

#targetまでの素数の数
import math
def sieve_of_eratosthenes2(target):
    dest = int(math.sqrt(target))
    target_list = [i for i in range(2, target+1) if target%i==0]
    prime_num = 0
 
    while True:
        num_min = min(target_list)
        if num_min > dest:
            prime_num += len(target_list)
            break
        prime_num += 1        
        target_list = [i for i in target_list if i%num_min!=0]
        if target_list==[]:
            break
 
    return prime_num   

a, b = map(int, input().split())
gcd = xgcd(a, b)
if gcd == 1:
    print(1)
else:
    ans = sieve_of_eratosthenes2(gcd)    
    print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a

#targetまでの素数の数
import math
def sieve_of_eratosthenes2(target):
    dest = int(math.sqrt(target))
    target_list = [i for i in range(2, target+1) if target%i==0]
    prime_list = []
 
    while True:
        num_min = min(target_list)
        if num_min > dest:
            prime_list.extend(target_list)
            break
        prime_list.append(num_min)        
        target_list = [i for i in target_list if i%num_min!=0]
        if target_list==[]:
            break
 
    return prime_list


a, b = map(int, input().split())
gcd = xgcd(a, b)
if gcd == 1:
    print(1)
else:
    lis = sieve_of_eratosthenes2(gcd)
    ans = len(lis) + 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a

#targetまでの素数の数
import math
def sieve_of_eratosthenes(target):
    dest = int(math.sqrt(target))
    target_list = [i for i in range(2, target+1)]
    prime_list = []
 
    while True:
        num_min = min(target_list)
        if num_min > dest:
            prime_list.extend(target_list)
            break
        prime_list.append(num_min)        
        target_list = [i for i in target_list if i%num_min!=0]
 
    return prime_list
   

a, b = map(int, input().split())
gcd = xgcd(a, b)
if gcd == 1:
    print(1)
else:
    lis = sieve_of_eratosthenes(gcd)
    ans = sum([1 for i in lis if gcd%i==0]) + 1
    print(ans)

Submission status: Time Limit Exceeded

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

def gcd(x,y):
  if y > x:
    x, y = y, x
  while x % y != 0:
    x, y = y, x % y
  return y

#print(gcd(660, 420))

def soinsu(n):
  count = 0
  i = 2
  while n != 1:
    if n % i == 0:
      count += 1
    while n % i == 0:
      n = n // i
    i += 1
  return count

#print(soinsu(9))

if __name__ == "__main__":
  gcd = gcd(A, B)
  ans = soinsu(gcd) + 1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

a,b=(int(x) for x in input().split())

c=[]
c=de(a,b)

#print(c)
d=[]
d.append(c[0])
if len(c) != 1:
	d.append(c[1])
	#print(len(c))
	for i in range(2,len(c)):
		#print(i)
		for j in range(1,i):
			#print("-----",i,j,c[i],c[j])
			if c[i] % c[j] == 0:
				break
			if i == j+1:
				d.append(c[i])
			
print(len(d))
#for e in d:
#  print(e, end =" ")
#print(d)

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

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

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

#commonDivisor
cd = []
cd.extend(cf(a,b))

length = len(cd)
ans = 1

for i in range(length):
    if (is_prime(cd[i])):
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def yakusu(x):
    ans=[1]
    check=2
    while(x!=1):
        if(x%check==0):
            ans+=[check]
            while(x%check==0):
                x=x//check
        check+=1  
    return ans
def main():
    a,b = map(int,input().split())	
    ans=0
    y1=yakusu(a)
    for i in y1:
        if b%i==0:
            ans+=1
    print(ans)

main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import fractions
from math import sqrt

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

G = fractions.gcd(A, B)
N = int(sqrt(G))+1
g = G
ans = 1

for i in range(G):
    if (g < i):
        break
    if(g % (i+2) == 0):
        ans += 1
        while(g % (i+2) == 0):
            g /= i+2

print(ans)

Submission status: Time Limit Exceeded

Solution code:

import fractions

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

G = fractions.gcd(A, B)
g = G
ans = 1


for i in range(G-1):
    if (g < i):
        break
    if(g % (i+2) == 0):
        ans += 1
        j = 1
        while(g % (i+2) == 0):
            g /= i+2
            j += 1

print(ans)

Submission status: Time Limit Exceeded

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

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

n = gcd(a,b)
m = n
x = 2
ans = 1

while m!=1:
    if m%x !=0:
        if x==2:
            x += 1
        else:
            x += 2
        continue
    ans += 1
    while m%x == 0:
        m /= x
    if x==2:
        x += 1
    else:
        x += 2

print(ans)

Submission status: Time Limit Exceeded

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

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

n = gcd(a,b)
m = n
x = 2
ans = 1

while m!=1:
    if m%x !=0:
        x += 1
        continue
    ans += 1
    while m%x == 0:
        m /= x
    x += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# A, Bの公約数
# 互いに素(素数でないとダメ)
A, B = map(int, input().split())

# 約数取得(素数判定)
def divide(num):
    ret = []
    for i in range(1, num + 1):

        if i != 2 and i % 2 == 0:
            continue

        if num % i == 0:
            addFlg = True
            for j in range(1, len(ret)):
                if i % ret[j] == 0:
                    addFlg = False
                    break
            if addFlg:
                ret.append(i)
    return ret

alist = divide(A)
blist = divide(B)

aset = set(alist)
bset = set(blist)
ans = aset & bset

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
# A, Bの公約数
# 互いに素(素数でないとダメ)
A, B = map(int, input().split())

# 約数取得(素数判定)
def divide(num):
    ret = []
    for i in range(1, num + 1):
        if num % i == 0:
            addFlg = True
            for j in range(1, len(ret)):
                if i % ret[j] == 0:
                    addFlg = False
                    break
            if addFlg:
                ret.append(i)
    return ret

alist = divide(A)
blist = divide(B)

aset = set(alist)
bset = set(blist)
ans = aset & bset

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
# A, Bの公約数
# 互いに素
A, B = map(int, input().split())

# 約数取得
def divide(num):
    ret = []
    for i in range(1, num + 1):
        if num % i == 0:
            ret.append(i)
    return ret

# 公約数取得
def matchDiv(a, b):
    ret = []
    for i in range(len(a)):
        for j in range(len(b)):
            if a[i] == b[j]:
                ret.append(a[i])
                break
    return ret

# 互いに素を取得
def so(soList, zanList):
    zl = zanList
    # 再帰的に素を探す
    for z in range(len(zanList)):
        sFlg = True
        sl = soList
        for s in soList:
            sDiv = divide(s)
            zDiv = divide(zanList[z])
            m = matchDiv(sDiv, zDiv)

            # 公約数には、１が入るので
            if len(m) != 1:
                sFlg = False

        # 素か判定
        if sFlg:
            # 素であればListに追加する
            sl.append(zanList[z])
            if len(zanList) > z + 1:
                return so(sl, zanList[z + 1:])
            else:
                return len(sl)

    return len(soList)

Adiv = divide(A)
Bdiv = divide(B)
match = matchDiv(Adiv, Bdiv)

cnt = 0
for n in range(len(match)):

    zanList = match[n + 1:]
    soList = [match[n]]

    cnt = max(cnt, so(soList, zanList))

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# def max_comn_div(n, m):
#     """give max common divisor"""
#     if n > m:
#         a, b = n, m
#     else:
#         a, b = m, n
#     while b != 0:
#         a, b = b, a % b
#     return a


# a = int(input())
# b = int(input())
# print(max_comn_div(a, b))

# def euc(a, b):
#      if a % b == 0:
#          return b
#      else:
#          return euc(b, a % b)


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


def div(n):
    """give divisors"""
    divisors = [1]
    i = 2
    while n > 1:
        if n % i == 0:
            divisors.append(i)
            while n % i == 0:
                n = n/i
        i += 1
    return divisors


a, b = map(int, input().split())
c = div(euc(a, b))
print(len(c))

Submission status: Time Limit Exceeded

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


def div(n):
    """give divisors"""
    divisors = [1]
    i = 2
    while n > 1:
        if n % i == 0:
            divisors.append(i)
            while n % i == 0:
                n = n/i
        i += 1
    return(divisors)


def comn_div(n, m):
    """give common divisors"""
    # 二つの約数を取って来てset&set
    cdiv_nm = set(div(n)) & set(div(m))
    return(list(cdiv_nm))
# 自然数以外が入ったら弾きたい気もする


cdiv_ab = comn_div(a, b)
disjoint = []
for i in range(len(cdiv_ab)):
    state = True
    # 自分より若い数字が約数の場合は除外
    for j in range(i):
        if comn_div(cdiv_ab[i], cdiv_ab[j]) != [1]:
            state = False
    if state:
        disjoint.append(i)
# print(cdiv_ab)
# print(disjoint)
print(len(disjoint))

Submission status: Time Limit Exceeded

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


# 公約数をリストとして得る
def comn_div(n, m):
    """give common divisor"""
    div_n = []
    div_m = []
    for i in range(1, n+1):
        if n % i == 0:
            div_n.append(i)
    for j in range(1, m+1):
        if m % j == 0:
            div_m.append(j)
    cdiv_nm = set(div_n) & set(div_m)
    return(list(cdiv_nm))
# 自然数以外が入ったら弾きたい


cdiv_ab = comn_div(a, b)
disjoint = []
for i in range(len(cdiv_ab)):
    state = True
    # 自分より若い数字が約数の場合は除外
    for j in range(i):
        if comn_div(cdiv_ab[i], cdiv_ab[j]) != [1]:
            state = False
    if state:
        disjoint.append(i)
# print(cdiv_ab)
# print(disjoint)
print(len(disjoint))

Submission status: Time Limit Exceeded

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

n = max(A,B)
ans = 1
for p in range(2,n+1):
    if A%p==0 and B%p==0:
        ans += 1
        while A%p==0 and B%p==0:
            A = A//p
            B = B//p
    if A==1 or B==1:
        break
print(ans)

Submission status: Time Limit Exceeded

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

def CommonDiv(x,y):
    res =[]
    for s in range(max(x,y)):
        d=s+1
        if x%d==0 and y%d == 0:
            res += [d]
    return res

def Divisor(k):
    res = []
    for n in range(k):
        if k%(n+1)==0:
            res += [n+1]
    return res


def isPrime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    for p in range(2, n):
        if n % p == 0:
            return False
    return True

resp = 0
for n in CommonDiv(a, b):
    if n==1 or isPrime(n):
        resp += 1
print(resp)

Submission status: Time Limit Exceeded

Solution code:
#coding: UTF-8
import fractions
a,b=map(int,input().split())
def main(a,b):
    yakusuu=[]
    m=fractions.gcd(a,b)
    for i in range(m//2):
        if (m/(i+1)).is_integer():
            yakusuu.append(i+1)
    yakusuu.append(m)
    n=len(yakusuu)
    ans=n
    for i in reversed(range(n)):
        if yakusuu[i]>1:
            for j in range(i//2):
                if (yakusuu[i]/yakusuu[j+1]).is_integer():
                    yakusuu[i]=0
                    ans-=1
                    break
                #else:
                    #break
    print(ans)
main(a,b)

Submission status: Time Limit Exceeded

Solution code:
def main():
  import fractions
  import math

  a,b = map(int,input().split())
  g = fractions.gcd(a,b)
  
  d = [1]
  num = 2

  while num <= g:
    #print("num",num)
    if g%num == 0:
      d.append(num)
    while g%num == 0 and g>1:
      g = g//num
      #print(g)
    num += 1
  
  print(len(d))

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import fractions
  import math

  a,b = map(int,input().split())
  
  d = [1]
  num = 2

  while num <= min(a,b):
    #print("num",num)
    if a%num == 0 and b%num == 0:
      d.append(num)
    while a%num == 0 and a>1:
      a = a//num
      #print(a)
    while b%num == 0 and b>1:
      b = b//num
      #print(b)
    num += 1
  
  print(len(d))

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
A = list(map(int,input().split()))
x = 2
s = set()

# def do(A,x,s):
#     flag = True
#     if A[0]%x == 0:
#         A[0] //= x
#         while A[0]%x == 0: A[0] //= x
#     else: flag = False

#     if A[1]%x == 0:
#         A[1] //= x
#         while A[1]%x == 0: 
#             A[1] //= x
#     else: flag = False
#     if flag:
#         s.add(x)

def do(A,x,s):
    if not A[0]%x and not A[1]%x:
        A[0] //= x
        A[1] //= x
        while not A[0]%x: A[0] //= x
        while not A[1]%x: A[1] //= x
        s.add(x)

do(A,x,s)
x += 1
do(A,x,s)

while x <= min(A):
    x += 2
    do(A,x,s)

# while x <= min(A):
#     x += 4
#     for _ in range(3):
#         x += 2
#         if x > min(A):
#             break
#         do(A,x,s)

print(len(s)+1)

Submission status: Time Limit Exceeded

Solution code:
a,b = map(int,input().split())
x = 2
s = set()

flag = True
if a%x == 0:
    a //= x
    while a%x == 0: a //= x
else: flag = False

if b%x == 0:
    b //= x
    while b%x == 0: 
        b //= x
else: flag = False
if flag:
    s.add(x)
x += 1

while x <= min(a,b):
    flag = True
    if a%x == 0:
        a //= x
        while a%x == 0: a //= x
    else: flag = False

    if b%x == 0:
        b //= x
        while b%x == 0: 
            b //= x
    else: flag = False
    if flag:
        s.add(x)
    x += 2

print(len(s)+1)

Submission status: Time Limit Exceeded

Solution code:
a, b = map(int, input().split())
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
 
def cd(num):
    k = []
    if num%2 == 0:
        k.append(2) 
    for i in range(1,num+1,2):
        if num%i == 0:
            if is_prime(i):
                k.append(i) 
    return k
 
def is_prime(num):
    for i in range(2, num):
        if num % i == 0:
            return False
    return True
 
 
gc = gcd(a,b)
c = cd(gc)
 
print(len(c))

Submission status: Time Limit Exceeded

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

#output
import math

A1 = []
for k in range(2, int(math.sqrt(A))+1):
    l = 1
    for i in range(2, math.floor(math.sqrt(k))+1):
        l *= k % i
    if l != 0 and A % k == 0:
        A1.append(k)
    else:
        pass
B1 = []
for k in range(2, int(math.sqrt(B))+1):
    l = 1
    for i in range(2, math.floor(math.sqrt(k))+1):
        l *= k % i
    if l != 0 and B % k == 0:
        B1.append(k)
    else:
        pass
        
C = set(A1) & set(B1)

print(len(C)+1)

Submission status: Time Limit Exceeded

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

#output
import math

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

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

ans = 0
for c in common_diviser:
    if is_prime(c):
        ans += 1

print(ans+1)

Submission status: Time Limit Exceeded

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

#output
import math
from functools import reduce

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

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

ans = []
for c in common_diviser:
    if is_prime(c):
        ans.append(c)

print(len(ans)+1)