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 div(N):
    ans = []
    for i in range(1, int(N ** 0.5) + 1):
        if N % i == 0:
            ans.append(i)
            if N // i != i:
                ans.append(N // i)
    ans.sort()
    return ans


import fractions

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

g=fractions.gcd(A,B)

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

d_list=div(g)

if len(d_list)==2:
    print(2)
    exit()

i=1

while d_list[i]<g:
    j=2
    temp=d_list[i]
    while temp*j<=d_list[-1]:
        if temp*j in d_list:
            d_list.remove(temp*j)
        j+=1
    i+=1
    if i==len(d_list):
        break


print(len(d_list))

Submission status: Time Limit Exceeded

Solution code:
import random


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

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

def is_prime(q,k=4):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし(但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        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

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


prime_list = [1] + [i for i in range(1, gcd(A, B) + 1) if is_prime(i)]
print(len([i for i in prime_list if A % i == 0 and B % i == 0]))

Submission status: Time Limit Exceeded

Solution code:
a, b = map(int, input().split())
i = 1
common = []
while True:
    if a % i == 0 and b % i == 0:
        a //= i
        b //= i
        common.append(i)
    if min(a, b) < i:
        break
    i += 1

count = 1
for i in range(1, len(common)):
    for j in range(1, i):
        if common[i] % common[j] == 0:
            break
    else:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import math
from fractions import gcd

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())
max_d = gcd(a, b)
ans = 0
for i in range(1, max_d + 1):
  if a % i == 0 and b % i == 0:
    ans += is_prime(i)
    
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

	return gcd(b, a%b)


G = gcd(A,B)

sosu = [1]
#d = math.ceil(G**(1/2))
flg = [i for i in range(1, G+1)]


for i in range(2,G+1):
	if flg[i-1] == 0:
		continue
	if G % i == 0:
		sosu.append(i)
		ind = i
		while ind <= G:
			flg[ind-1] = 0
			ind += i


print(len(sosu))

Submission status: Time Limit Exceeded

Solution code:
import itertools
from fractions import gcd

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

cfList = cf(a, b)
ans = [cfList[0]]

for l in cfList[1:]:
    l2 = l
    flg = True
    for i in ans:
        if gcd(i,l2) != 1:
            flg = False
            break
    if flg:
        ans.append(l2)


print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import fractions
import math

AB = list(map(int, input().split()))
A = AB[0]
B = AB[1]

GCM = fractions.gcd(A, B)

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

    divisors.sort()
    return divisors

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

divisors = make_divisors(GCM)

cnt = 0
for divisor in divisors:
    if isPrime(divisor):
        cnt += 1
    if divisor > int(divisors[-1]/2):
        break

print(cnt+1)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import itertools

def answer():
    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

    a, b = map(int, input().split())
    g = gcd(a, b)
    divisors = make_divisors(g)
    set_divisors = set(divisors)

    for div1, div2 in itertools.combinations(divisors[1:], 2):
        item = div1 * div2 / gcd(div1, div2)
        if item in set_divisors:
            set_divisors.remove(item)

    print(len(set_divisors))


if __name__ == '__main__':
    answer()

Submission status: Time Limit Exceeded

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

def coprime(a, b):
    return bltin_gcd(a, b) == 1
def rmdb(n, li):
  lst = [x for x in li if x%n != 0]
  return lst

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

ng_set = set()
for i in range(1, len(cf_list)):
  for j in range(1, i):
    if cf_list[i] % cf_list[j] == 0:
      ng_set.add(cf_list[i])
      break
  
print(len(cf_list)-len(ng_set))

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,p):
    for i in range(p+1,min(x,y)+1):
        if x % i == 0 and y % i == 0 :
            return i
A,B = map(int,input().split())
ans = 1
p = 1
while True :
    c = check(A,B)
    if c == 1 :
        break
    p = check2(A,B,p)
    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 math
prime = [2, 3]
for n in range(5, 1000001, 2):
	isprime = True
	for i in range(1, len(prime)):
		if prime[i] ** 2 > n:
			break
		if n % prime[i] == 0:
			isprime = False
			break
	if isprime:
		prime.append(n)
data = input().split(" ")
a = int(data[0])
b = int(data[1])
c = math.sqrt(a)
p = []
if c <= math.sqrt(b):
	c = math.sqrt(b)
for i in range(78498):
	d = prime[i]
	if d >= c:
		break
	if a % d == 0:
		if b % d == 0:
			p.append(d)
print(len(p)+1)

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()

import numpy as np

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

prime_a = list(prime.find_factors(a).keys())
prime_b = list(prime.find_factors(b).keys())
pa = np.array(prime_a)
pb = np.array(prime_b)

#print(pa, pb)

#print(1+len(set(prime_a)&set(prime_b)))
print(1 + np.intersect1d(pa, pb).size)

Submission status: Time Limit Exceeded

Solution code:
import sys,fractions
sys.setrecursionlimit(100000)

def ins(): return input().split()
def ii(): return int(input())
def iil(): return list(map(int,ins()))
def lin(): return list(input())
def iin(): return map(int,ins())

a,b = iin()
t = fractions.gcd(a,b)

p=[0,0]+[1]*999999
k=len(p)
for i in range(k//2+1):
    if p[i]==0:continue
    for q in range(2*i,k,i):
        p[q]=0
cnt = 1
f = True
while f:
    f = False
    for i,j in enumerate(p):
        if t<i:
            break
        if j==1 and t%i==0:
            f = True
            t //= i
            cnt += 1
            p[i]=2
        elif j==2 and t%i==0:
            f = True
            t //= i
if t != 1:
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    x1, x2 = map(int, input().split())
    cf = []
    for i in range(2, min(x1, x2) + 1):
        if x1 % i == 0 and x2 % i == 0:
            appendable = True
            for j in cf:
                if i % j == 0:
                    appendable = False
                    break
            if appendable:
                cf.append(i)
    # cfは公約数のリスト
    # このリストの中で互いに素のものだけを残す
    # for i in range(len(cf)):
    #   fractions.gcd()
    print(len(cf) + 1)

Submission status: Time Limit Exceeded

Solution code:
import math

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

while len(stack)!=0:
    p=stack.pop()
    if A%p==0 and B%p==0:
        for x in divisor:
            if p%x==0 and x!=1:
                break
        else:
            divisor+=[p]

print(len(divisor))

Submission status: Time Limit Exceeded

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


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


c = cf(a, b)
len_c = len(c)
d = []
f = 0
for i in range(len(c)):
    for j in range(1, i-f):
        if c[i-f] % c[j] == 0:
            d.append(c[i-f])
            del(c[i-f])
            f += 1
            break
print(len_c - len(d))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

for i in range(2, min(A,B)+1):
    if A%i == 0 and B%i == 0:
        cf.append(i)
count = 1
for i in cf:
    if is_prime(i):
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
num_line=input().rstrip().split(" ")
numA=int(num_line[0])
numB=int(num_line[1])

if(numA>=numB):
    NumMax=numA
    NumMin=numB
else:
    NumMax=numB
    NumMin=numA

lst_p=[]
import math

def trial_division(target):
    dest = int(math.sqrt(target))
 
    for j in range(2,dest+1):
        if target % j == 0:
            return
    lst_p.append(target)

for i in range(2,NumMax):
    trial_division(i)

#print(lst_p)
lst2_p=[]
lst2_p.append(1)
  
for i in range(len(lst_p)):
    tst=lst_p[i]
    lst2_p.append(tst)
    if numA%tst!=0:
        lst2_p.remove(tst)
    
    elif numB%tst!=0:
        lst2_p.remove(tst)


print(len(lst2_p))

Submission status: Time Limit Exceeded

Solution code:
import math


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


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


ab = [int(i) for i in input().split()]
koyakusuList = cf(ab[0], ab[1])

res = 1
for i in range(1, len(koyakusuList)):
    if is_sosu(koyakusuList[i]):
        res += 1


print(res)

Submission status: Time Limit Exceeded

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

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

#for i in itertools.combinations(C, 2):
#    print(i)

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    if a == 1:
        return 1
    else:
        return 0
NG=[]
ans=0

for i in itertools.combinations(C, 2):
    a,b=i
    if a in NG:
        continue
    if b in NG:
        continue

    z=gcd(a,b)
    #print(a,b)
    #print(z)
    
    if z == 0:
        NG.append(max(a,b))

print(len(C)-len(NG))

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 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 and is_prime(i):
        cd.append(i)
print(len(cd) + 1)

Submission status: Time Limit Exceeded

Solution code:

def get_sieve_of_eratosthenes(n):
    prime = [1, 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 get_gcd(a, b):
    if b > a:
        a, b = b, a
    r = a%b
    if r == 0:
        return b
    else:
        return get_gcd(b, r)

A, B = map(int, input().split())
gcd = get_gcd(A, B)
if gcd == 1:
  print("1")
else:
  primes = get_sieve_of_eratosthenes(gcd)
  divisors = [p for p in primes if gcd%p==0]
  print(len(divisors))

Submission status: Time Limit Exceeded

Solution code:
import itertools

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 hogehoge(yakusu):
    is_ok = True
    m = len(yakusu)
    for i in range(m):
        c = yakusu[i]
        for j in range(i+1,m):
            d = yakusu[j]
            if len(cf(c,d)) > 1:
                is_ok = False            
    return is_ok

yakusu = cf(a,b)

stuff = yakusu
max_num = 1
for L in range(2, len(stuff)+1):
    for subset in itertools.combinations(stuff, L):
        # print(subset)
        # print(hogehoge(subset))
        if hogehoge(subset):
            max_num = len(subset)
            
print(max_num)

Submission status: Time Limit Exceeded

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

#ユークリッドの互除法
gc = fractions.gcd(a,b)
if gc == 1:
	print(1)
	exit()


cout = 1 #1がfalse判定される
for i in range(1,gc+1):
	if a % i == 0 and b % i == 0:
		if is_prime(i):
			cout+= 1
print(cout)

Submission status: Time Limit Exceeded

Solution code:
def cf(a, b):
    cf = [1]
    for i in range(2, min(a, b)+1):
        if a % i == 0 and b % i == 0:
            if (i == 2) or (i > 2 and i % 2 != 0):
                cf.append(i)
            else:
                pass
    return cf

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

for i in range(1, len(cf_l)):
    for j in range(i+1, len(cf_l)):
        if cf_l[j] % cf_l[i] == 0:
            cf_l.pop(j)

print(len(cf_l))

Submission status: Time Limit Exceeded

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



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

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

    return True

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

print(cf(a,b)+1)

Submission status: Time Limit Exceeded

Solution code:
import random


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

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

def is_prime(q,k=4):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし(但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        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

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


if A < B:
    A, B = B, A

div_list = [i for i in make_divisors(B) if A % i == 0]
prime_list = [1] + [i for i in range(1, gcd(A, B) + 1) if is_prime(i)]
print(len([i for i in prime_list if i in div_list]))

Submission status: Time Limit Exceeded

Solution code:
A, B = map(int, input().split())
N = [i for i in range(1, min(A//2, B//2)+1) if A%i == 0 and B%i==0]
M = 1

for i in range(len(N)):
	if i != 0:
		for m in N[i-1::-1]:
			if N[i] % m == 0:
				break
		if m == N[0]:
			M += 1

print(M)

Submission status: Time Limit Exceeded

Solution code:
import math
a, b = [int(i) for i in input().split()]

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()
if prime.is_prime(a) and prime.is_prime(b):
    print(1)
else:
    _gcd = prime.gcd(a, b)
    fact_dict = prime.find_factors(_gcd)
    print(len(fact_dict.keys()) + 1)

Submission status: Time Limit Exceeded

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

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

if len(lst) == 1:
    print(1)
else:
    check = [lst[1]]
    for i in range(1, len(lst)):
        for c in check:
            if lst[i] % c == 0:
                break
        else:
            check.append(lst[i])
    print(len(check)+1)

Submission status: Time Limit Exceeded

Solution code:
num = [int(x) for x in input().split()]
a, b = num[0], num[1]

def getPrimes(n): 
      
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
          
        if (prime[p] == True): 
              
            for i in range(p * p, n+1, p): 
                prime[i] = False
        p += 1
    return [p for p in range(2, n) if prime[p] and a%p==0 and b%p==0]

print(len(getPrimes(a))+1)

Submission status: Time Limit Exceeded

Solution code:
import math

a, b = map(int, open(0).read().split())

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

div_a = make_divisors(a)
div_b = make_divisors(b)

slist = div_a + div_b
elist = sorted([x for x in set(slist) if slist.count(x) > 1],reverse=True)
#print(elist)

delnum = 0
for i in range (0,len(elist)):
  if len(make_divisors(elist[i]))>2:
    delnum = delnum + 1 

print(len(elist)-delnum)

Submission status: Time Limit Exceeded

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

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

l = make_divisors(_gcd)
if len(l)==1:
    print(1)
    quit()
l.sort()

l2 = l[:]
for i,x in enumerate(l):
    for y in l[i+1:]:
        if fractions.gcd(x, y) != 1 and y in l2:
            l2.remove(y)
print(len(l2))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(int(1e6))

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

prime_map = {0: False, 1: False, 2: True, 3: True, 4: False, 5: True, 6: False}
def is_prime(n):
    if n in prime_map:
        pass
    elif (n % 2) == 0:
        prime_map[n] = False
    else:
        for i in range(3, (n//2), 2):
            if (n % i) == 0:
                prime_map[n] = False
                break
        else:
            prime_map[n] = True
    
    return prime_map[n]

primes = list()
for p in range(min(A, B)):
    if is_prime(p):
        primes.append(p)

prime_factors_count = 0
for f in primes:
    if A % f:
        pass
    elif B % f:
        pass
    else:
        prime_factors_count += 1

print(prime_factors_count + 1)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    a, b = map(int, input().split())
    d = []
    for i in range(2, min(a, b) + 1):
        if a % i == 0 and b % i == 0:
            if any([i % di == 0 for di in d]):
                continue
            d.append(i)
    print(len(d) + 1)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
a_b = input().split(" ")
A = int(a_b[0])
B = int(a_b[1])

p_nums = []
for i in range(1, min([A, B]) + 1):
    is_p_num = True
    if A % i == 0 and B % i == 0:
        for p in p_nums:
            if p == 1:
                continue
            if i % p == 0:
                is_p_num = False
                break
        if is_p_num:
            p_nums.append(i)

print(len(p_nums))