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 gcd
from fractions import gcd  # gcd: 2つの正の数を渡すと最大公約数を返す  # Atcoder ではこっち
from collections import defaultdict

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

# 正の公約数
cf=[] # 1が公約数なのは当然
min_num = min(a, b)+1
for i in range(2, min_num):
    if a % i == 0 and b % i == 0:
        cf.append(i)

# print(cf)

# 素数チェック
def is_prime(n):
    """
    Assumes that n is a positive natural number
    https://www.rookieslab.com/posts/fastest-way-to-check-if-a-number-is-prime-or-not
    """
    # We know 1 is not a prime number
    if n == 1:
        return False

    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

# disjoint_dict = defaultdict(lambda: True)

disjoint_dict = {i: True for i in cf}

# for i in range(0, len(cf)-1):

for i, cf_i in enumerate(cf):

    if is_prime(cf_i):  # 素数である
        continue
    if disjoint_dict[cf_i] == False:  # 既に互いに素ではないパターンが発見されている
        continue

    # for j in range(i, len(cf)):
    cf_for_j = cf[i:]
    for cf_j in cf_for_j:
        if disjoint_dict[cf_j] == False:
            continue

        if gcd(cf_i, cf_j) != 1:
            disjoint_dict[cf_j] = False

# print(disjoint_dict)
print(sum(disjoint_dict.values())+1)  # 1は必ず全ての数字に対して互いに素なので +1 する

Submission status: Time Limit Exceeded

Solution code:
import copy
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 gcd( x, y ):
    while y != 0:
        x, y = y, x%y
    return x

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

A , B = map(int , input().split())
gcd_value = gcd(A , B)
cd = []

for i in range(1,gcd_value + 1):
    if A % i == 0 and B % i == 0:
        cd.append(i)
'''
cnt = copy.deepcopy(cd)
i = 0
j = 1

while i < len(cnt) - 1:
#for i in range(len(cnt) - 1):
    j = i + 1
    while j < len(cnt):
    #for j in range(i + 1 , len(cnt)):
        if not coprime(cnt[i] , cnt[j]):
            if cnt[j] in cnt:
                cnt.remove(cnt[j])
                continue
        j += 1
    i += 1
print(len(cnt))
'''
#print(cnt)
count = 1
for value in cd:
    if is_prime(value):
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import math

a, b = map(int, input().split())
n = min(a, b)
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]
l = primes(n//2)
count = 1
for p in l:
    if a % p == 0 and b % p == 0:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import math
a, b = list(map(int, input().split(' ')))
def gcd(l, s):
    return s if l % s == 0 else gcd(s, l % s)
g = gcd(a, b)
primes = []
if g % 2 == 0:
    primes.append(2)
def prime(n):
    for i in range(len(primes)):
        if n % primes[i] == 0:
            return False
    return True
def make():
    for i in range(3, g + 1, 2):
        if g%i == 0 and prime(i):
            primes.append(i)

make()

print(len([i for i in primes if g % i == 0]) + 1)

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
m,n = map(int,input().split())
# div = [0]
div = [1]
flg = 0

if m % 2 == 0 and n % 2 == 0:
    div.append(2)

# while i < 0:
    # if m 
for i in range(3,m):
    if m % i == 0 and n % i == 0 and i % 2 == 1:
        # ans += 1
        # m = m / i
        # n = n / i
        for j in range(1,len(div)):
            if i % div[j] == 0:
                flg = 1
                break
        if flg == 0:
            div.append(i)
        else:
            flg = 1
    

    # print(student[i]-1)
    # toukou[student[i]-1] = i+1
# print(" ".join(map(str,div)))
print(len(div))

Submission status: Time Limit Exceeded

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

while B:
    A,B = B, A%B
g = A
g_ = g

count = 0
l = []
i = 2
while i <= g_:
    while g%i == 0:
        g = g/i
        l.append(i)
    l = list(set(l))
    i = i+1

print(1+len(l))

Submission status: Time Limit Exceeded

Solution code:
import sys
A, B = map(int, sys.stdin.readline().split())

a, b = [], []
for i in range(A, 0, -1):
    if A%i ==0:
        a.append(A//i)
    
for i in range(B, 0, -1):
    if B%i ==0:
        b.append(B//i)

a,b = set(a), set(b)
L = a&b
#print(L)
cnt =0
for l in L:
    tmp = 0
    for i in range(l-1, 1, -1):
        if l%i==0:
            tmp +=1
            break
    if tmp ==0:
        cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import math

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

if a>b:
  a,b = b,a
  
n=fractions.gcd(a,b)

d = [1]
num = 2

while n>1:
  if n%num == 0:
    d.append(num)
  while n%num == 0:
    n = n//num
  num+=1
  
print(len(d))

Submission status: Time Limit Exceeded

Solution code:
import math

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

def soinsu(test):
    list_sosu = []
    x = 0
    while x==0:
        for i in range(2,test+1):
            if test % i == 0:
                test = int(test/i)
                if test == 1:
                    x = 1
                list_sosu.append(i)
                break
    return set(list_sosu)

if A == 1 or B == 1:
    print(1)
    
else:
    print(len(soinsu(A)&soinsu(B))+1)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

while A%B != 0:
  tmp = B
  B = A % B
  A = tmp

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
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:
      cf.append(i)
  return cf

def using_sqrt(limit):
    n = 0
    for k in range(2, limit+1):
        factor = 0
        
        # 2以外の偶数は素数ではないので無視する
        if k % 2 == 0 and k != 2:
            continue
        
        # 繰り返しの上限を対象の平方根にする
        for divisor in range(2, math.floor(math.sqrt(k))+1):
            if k % divisor == 0:
                factor += 1
                
        if factor == 0:
            n += 1
            
    return n

l = cf(A, B)

cnt = 0
for i in range(len(l)):
  if using_sqrt(l[i]) <= 2:
    cnt += 1
  else:
    break

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math
A, B = (int(i) for i in input().split())
C=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

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

D=cf(A,B)

for i in range(len(D)):
	if td(D[i])==True:
		C+=1
print(C+1)

Submission status: Time Limit Exceeded

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


if a < b:
    a, b = b, a
while a % b != 0:
    a, b = b, a % b
gcd = b

i = 2
result = set()
while True:
    if gcd % i == 0:
        gcd = gcd / i
        result.add(i)
    else:
        i += 1
        
    if i > gcd:
        break
        
print(len(result) + 1)

Submission status: Time Limit Exceeded

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

#numには入力値の大きいほうの数字が入る
num = (max(A,B))
primeNum=[]
for i in range(2,num):
  flag=False  
  for j in range(2,i):
    if i%j==0:
      flag=True
      break
  if flag==False:
    primeNum.append(i)

#primeNumにはmax(A,B)までの素数が入っている。素因数分解に使用する。
resultNum=[0]*len(primeNum)
result=1


j=0
result=0
for i in primeNum:
  flag=False
  while A % i == 0 and B % i == 0:
    A = A // i
    B = B // i
    resultNum[j]+=1
    flag=True
  j+=1
  
  if flag==True:
    result+=1
# print(resultNum)
print(result+1)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from math import sqrt

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

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

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

print(c)

Submission status: Time Limit Exceeded

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

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

x = gcd(A, B)
res = 1
if x != 1:
    i = 2
    while i <= x:
        if x % i == 0:
            res += 1
            x /= i
            while x % i == 0:
                x /= i
        i += 1

print(res)

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
import random

def is_prime(q,k=50):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 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())
cd = cf(a,b)
count = 0

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

print(count + 1)

Submission status: Time Limit Exceeded

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

com_div = [i for i in range(2, min(A, B)) if (A % i == 0 and B % i == 0)]
l = list()

while True:
    flag = 1
    if len(com_div) == 0:
        break
    last = com_div.pop(-1)
    for c in com_div:
        if last % c == 0:
            flag = 0
            break
    if flag:
        l.append(last)

print(len(l) + 1, end='')

Submission status: Time Limit Exceeded

Solution code:
import math

a, b = map(int, input().split())
n = min(a, b)
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]
l = primes(n)
count = 1
for p in l:
    if a % p == 0 and b % p == 0:
        count += 1
print(count)

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())
ans = 1
while True :
    if check(A,B)== 1 :
        break
    p = check2(A,B)
    while True :
        if A % p == 0 and B % p == 0 :
            A = (A//p)
            B = (B//p)
        else :
            break
    ans += 1
print(ans)

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
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

a, b = map(int, input().split())
cfs = cf(a, b)
primes = []
for c in cfs:
    primes += prime_factorize(c)
print(len(set(primes))+1)

Submission status: Time Limit Exceeded

Solution code:
a,b = map(int,input().split())
cl = []
for i in range(1, min(a, b)+1): 
    if a%i==b%i==0: 
        cl.append(i)
def isprime(n):
    """Returns True if n is prime."""
    if n == 2:
        return True
    if n == 3:
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False

    i = 5
    w = 2

    while i * i <= n:
        if n % i == 0:
            return False

        i += w
        w = 6 - w

    return True
ans = 0
for w in cl:
    if isprime(w):
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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

com_div = []
for n in range(1, min(a, b) + 1):
    if a % n == 0 and b % n == 0:
        com_div.append(n)

ans = []
for n in com_div:
    if n == 1:
        ans.append(n)
        continue
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            break
    else:
        ans.append(n)

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
'''
Created on 2019/09/28

@author: oiwaiman
'''

import math
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_ab = cf(A, B)
counter = 0
for i in list_ab:
    for j in range(2, int(math.sqrt(i))+1):
        if i % j == 0:
            break
    else:
            counter += 1

print(counter+1)

Submission status: Time Limit Exceeded

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

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)

print(len(cf))

Submission status: Time Limit Exceeded

Solution code:
a,b=map(int,input().split())
import fractions
n=fractions.gcd(a,b)
c=int(n**0.5)+2
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
pri=0
for p in range(2, n):
    if n % p == 0:
        pri+=1
if pri==0:
    j=n+1
else:
    j=c

for i in primes(j):
    if n%i==0:
        kosuu+=1
print(kosuu+1)

Submission status: Time Limit Exceeded

Solution code:
a, b = map(int, input().split())
divisor = []
upper = min(a, b)//2+1
for i in range(2, upper):
    divable = False
    if a % i == 0 and b % i == 0:
        for j in range(len(divisor)):
            if i % divisor[j] == 0:
                divable = True
                break
        if not divable:
            divisor.append(i)
print(len(divisor)+1)

Submission status: Time Limit Exceeded

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

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

m = l[:]
for i in range(1, len(l)):
    for j in range(i):
        if l[i] % l[j] == 0:
            m.remove(l[i])
            break

print(len(m) + 1)

Submission status: Time Limit Exceeded

Solution code:
import collections
import math

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

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

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    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 yakusuu(A):
    Y=[]
    for i in range(1,A+1):
        if N%i==0:
            Y.append(i)
    return(Y)


N=gcd(A,B)

if N==1:
    print(1)
else:
    c = collections.Counter(prime_factorize(N))
    ms = list(c.keys())[-1]
    pl = primelist(N)
    ya = yakusuu(N)
    
    #print(N,ms,pl,ya)
    
    count=0
    for i in range(len(pl)):
        if pl[i] in ya:
            count+=1
    print(count)

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):
    if n == 1:
        return True

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

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

while i <= gcd_recursive(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:
# -*- coding: utf-8 -*-
def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1

def divisor(n, m):
    i = 1
    cnt = 1
    while i <= n or i <= m:
        if n%i == 0 and m%i == 0 and is_prime(i):
            cnt += 1
        i += 1
    return cnt

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

print(divisor(A,B))

Submission status: Time Limit Exceeded

Solution code:
import itertools, fractions
A, B = map(int, input().split())
cd_list = []
if A >= B:
    cd_list = [n for n in range(1, B+1) if A%n==0 and B%n==0]
else:
    cd_list = [n for n in range(1, A+1) if A%n==0 and B%n==0]
prime_list = [1]
for i in range(1, len(cd_list)):
    if all([1 if fractions.gcd(cd_list[i], n)==1 else 0 for n in cd_list[:i]]):
        prime_list.append(cd_list[i])
print(len(prime_list))

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:]

if 2 in numlist:
    numlist = [x for x in numlist if x%2==1]
    numlist.insert(0,2)
else:
    numlist = [x for x in numlist if x%2==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:
import fractions
import heapq

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

cd = []
max_cd = fractions.gcd(A, B)

if max_cd == 1:
    cd.append(1)
else:
    for i in range(1, max_cd + 1):
        if not max_cd % i == 0:
            continue

        a = max_cd // i

        if i > a:
            break

        heapq.heappush(cd, i)
        heapq.heappush(cd, a)

l = []

for i in range(0, len(cd)):
    c = heapq.heappop(cd)
    if not l:
        l.append(c)
    else:
        join = True
        for j in range(0, len(l)):
            k = l[j]
            if fractions.gcd(c, k) != 1:
                join = False
                break
        if join:
            l.append(c)

print(len(l))

Submission status: Time Limit Exceeded

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

import math
from fractions import gcd

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

# 最大公約数
g = gcd(A, B)

if g == 1:
    print(1)
    exit()

ggg = set()
for i in range(1, g+1):
    if A%i == 0 and B%i == 0:
        ggg.add(i)

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]

prime = get_sieve_of_eratosthenes(g)
#print(prime)

print( len(ggg & set(prime)) +1 )

Submission status: Time Limit Exceeded

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

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

d = c
for i in c:
    e = d
    if i == 1:
        continue
    d = [j for j in d if j%i!=0]
    if d != e:
        d.append(i)
print(len(d))

Submission status: Time Limit Exceeded

Solution code:
import random
def is_prime(q,k=50):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 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())
 
c = 1
for i in range(1,min(a,b)+1):
	if a % i == 0 and b % i == 0:
		if is_prime(i):
			c+=1			
		
print(c)

Submission status: Time Limit Exceeded

Solution code:
import math
import random


class Prime:
    seed_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

    def is_prime(self, n):
        """
        prime test (hybrid)

        see also: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """
        is_prime_common = self.is_prime_common(n)
        if is_prime_common is not None:
            return is_prime_common

        if n < 2000000:
            return self.is_prime_brute_force(n)
        else:
            return self.is_prime_miller_rabin(n)

    def is_prime_common(self, n):
        if n == 1: return False
        if n in Prime.seed_primes: return True
        if any(map(lambda x: n % x == 0, self.seed_primes)): return False

    def is_prime_brute_force(self, n):
        """
        brute force prime test
        use with is_prime_common if you want to skip seed_primes

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

    def is_prime_miller_rabin(self, n):
        """
        miller rabin prime test
        use with is_prime_common if you want to skip seed_primes

        see also
            algorithm: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
            implementation: https://qiita.com/srtk86/items/609737d50c9ef5f5dc59
            improvement: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """

        d = n - 1
        while d & 1 == 0:
            d >>= 1

        # use one of these lines / upper is more efficient.
        witnesses = self.get_witnesses(n)
        # witnesses = [random.randint(1, n - 1) for _ in range(100)]

        for w in witnesses:
            y = pow(w, d, n)

            while d != n - 1 and y != 1 and y != n - 1:
                y = (y * y) % n
                d <<= 1

            if y != n - 1 and d & 1 == 0:
                return False

        return True

    def get_witnesses(self, num):
        def _get_range(num):
            if num < 2047:
                return 1
            if num < 1373653:
                return 2
            if num < 25326001:
                return 3
            if num < 3215031751:
                return 4
            if num < 2152302898747:
                return 5
            if num < 3474749660383:
                return 6
            if num < 341550071728321:
                return 7
            if num < 3825123056546413051:
                return 9
            return 12

        return self.seed_primes[:_get_range(num)]

    def gcd(self, a, b):
        if a < b:
            return self.gcd(b, a)
        if b == 0:
            return a
        while b:
            a, b = b, a % b
        return a

    @staticmethod
    def f(x, n, seed):
        """
        pseudo prime generator
        :param x:
        :param n:
        :param seed:
        :return: pseudo prime
        """
        p = Prime.seed_primes[seed % len(Prime.seed_primes)]
        return (p * x + seed) % n

    def find_factor(self, n, seed=1):
        """
        find one of factor of n
        this function is based to Pollard's rho algorithm

        see also
            algorithm: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
            implementation: https://qiita.com/gushwell/items/561afde2e00bf3380c98

        :param n:
        :param seed:
        :return: factor
        """
        if self.is_prime(n):
            return n

        x, y, d = 2, 2, 1
        count = 0
        while d == 1:
            count += 1
            x = self.f(x, n, seed)
            y = self.f(self.f(y, n, seed), n, seed)
            d = self.gcd(abs(x - y), n)

        if d == n:
            return self.find_factor(n, seed+1)
        return self.find_factor(d)

    def find_factors(self, n):
        primes = {}
        if self.is_prime(n):
            primes[n] = 1
            return primes

        while n > 1:
            factor = self.find_factor(n)

            primes.setdefault(factor, 0)
            primes[factor] += 1

            n //= factor

        return primes


prime = Prime()

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

prime_a = prime.find_factors(a).keys()
prime_b = prime.find_factors(b).keys()
print(1+len(set(prime_a)&set(prime_b)))

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,2):
        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())
    g = gcd(a,b)
    g_l = divisors(g)
    pn = prime_num(max(g_l)+1)
    ans = 1
    for i in g_l:
        if i in pn:
            ans += 1
    print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
a,b = map(int, input().split())
a,b = min(a,b),max(a,b)
c = range(2,a//2)
d = 0
for i in c:
  c = [c[j] for j in range(len(c)) if c[j] % i != 0 or c[j] == i]
for i in c:
  if a % i == 0 and b % i == 0:
    d += 1
print(d+1)

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:
            flag = True
            for c in cf:
                if i%c == 0:
                    #print(i,c,'flag is off')
                    flag = False
                    break
            if flag:
                cf.append(i)
    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(candidate)
print(len(candidate)+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())

def main():
    A, B = mis()
    from fractions import gcd
    n = gcd(A,B)
    def get_common_divs(n1, n2):
        common_divs = set()
        i = 1
        while i*2 <= min(n1,n2):
            if n1%i == n2%i == 0:
                common_divs.add(i)
            i += 1
        return common_divs
    
    common_divs = get_common_divs(A,B)

    ans = {1}
    for d in common_divs:
        if all(gcd(a,d)==1 for a in ans):
            ans.add(d)

    ans = len(ans)
    print(ans)


main()

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!=0):
	if g%divide==0:
		ans+=1
		while(g%divide==0 and g!=0):
			g//=divide
	divide+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
a,b = map(int, input().split())
ans = 1
count = 2
num=gcd(a,b)

if a==1 or b==1:
    print(1)
else:
    while num!=1:
        if num%count==0:
            ans+=1
            while num%count==0:
                num= num/count
            count+=1
        else:
            count+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

A,B=map(int,input().split())
min=min(A,B)
rng=math.ceil(min/2)
divisor=[1]
for i in range(2,min+1):
    if A%i==0 and B%i==0:
        for x in divisor:
            if i%x==0 and x!=1:
                break
        else:
            divisor+=[i]

print(len(divisor))

Submission status: Time Limit Exceeded

Solution code:
import copy

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

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

A , B = map(int , input().split())
gcd_value = gcd(A , B)
cd = []

for i in range(1,gcd_value + 1):
    if A % i == 0 and B % i == 0:
        cd.append(i)
cnt = copy.deepcopy(cd)
i = 0
j = 1
while i < len(cnt) - 1:
#for i in range(len(cnt) - 1):
    j = i + 1
    while j < len(cnt):
    #for j in range(i + 1 , len(cnt)):
        if not coprime(cnt[i] , cnt[j]):
            if cnt[j] in cnt:
                cnt.remove(cnt[j])
                continue
        j += 1
    i += 1
#print(cnt)
print(len(cnt))