Problem:


Score : 400 points

Problem Statement

Given are positive integers A and B.

Let us choose some number of positive common divisors of A and B.

Here, any two of the chosen divisors must be coprime.

At most, how many divisors can we choose?

Definition of common divisor

An integer d is said to be a common divisor of integers x and y when d divides both x and y.

Definition of being coprime

Integers x and y are said to be coprime when x and y have no positive common divisors other than 1.

Definition of dividing

An integer x is said to divide another integer y when there exists an integer \alpha such that y = \alpha x.

Constraints

All values in input are integers.

1 \leq A, B \leq 10^{12}

Input

Input is given from Standard Input in the following format:

A B

Output

Print the maximum number of divisors that can be chosen to satisfy the condition.

Sample Input 1

12 18

Sample Output 1

3

12 and 18 have the following positive common divisors: 1, 2, 3, and 6.

1 and 2 are coprime, 2 and 3 are coprime, and 3 and 1 are coprime, so we can choose 1, 2, and 3, which achieve the maximum result.

Sample Input 2

420 660

Sample Output 2

4

Sample Input 3

1 2019

Sample Output 3

1

1 and 2019 have no positive common divisors other than 1.



Sample input:
12 18


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools
import collections
from collections import deque
 
sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
 
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()
 
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

def main():
    A, B = NMI()
    GCD = math.gcd(A, B)
    
    if A == 1 or B == 1:
      print(1)
    else:
      
      cnt = 0
      for n in get_sieve_of_eratosthenes(GCD):
          if GCD % n == 0:
              cnt += 1
      print(cnt+1)

    
 
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools
import collections
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

def main():
    A, B = NMI()
    GCD = math.gcd(A, B)
    
    if A == 1 or B == 1:
      print(1)
    else:
      
      cnt = 0
      for n in get_sieve_of_eratosthenes(GCD):

          if GCD % n == 0:
              cnt += 1

              while GCD % n == 0:
                  GCD = GCD//n
          if GCD == 1:
              print(cnt+1)
              sys.exit()
    


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

from math import gcd
n = gcd(a,b)

li = [1]
i = 1
for i in range(2,n+1):
    while n%i == 0:
        li.append(i)
        n //=i
print(len(set(li)))

Submission status: Time Limit Exceeded

Solution code:
import math
A, B = map(int, input().split())
gcd = math.gcd(A, B)
ans = 1
if gcd%2==0:
  ans += 1
if gcd >= 3:
  pn = [2]
  for i in range(3, gcd+1, 2):
    check=True
    for num in pn:
      if i % num == 0:
        check=False
        break
    if check:
      pn.append(i)
      if A%i==0 and B%i==0:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
A, B = map(int, input().split())
judge = min(A, B)
pn = [2]
ans = 1
if A%2==0 and B%2==0:
  ans += 1
if judge >= 3:
  for i in range(3, judge+1, 2):
    check=True
    for num in pn:
      if i % num == 0:
        check=False
        break
    if check:
      pn.append(i)
      if A%i==0 and B%i==0:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

def cal(a, b):
    c = [1]
    if a%2 == 0 and b%2 == 0:
        c.append(2)
    for i in range(3, min(a, b)+1, 2):
        if a%i == 0 and b%i == 0:
            if len(c) == 1:
                c.append(i)
            else:
                for j, k in enumerate(c[1:]):
                    if i%k == 0:
                        break
                    elif j == len(c)-2:
                        c.append(i)
    return c

ans = cal(a, b)
print(len(ans))

Submission status: Time Limit Exceeded

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

def cal(a, b):
    c = [1]
    for i in range(2, min(a, b)+1):
        if a%i == 0 and b%i == 0:
            if len(c) == 1:
                c.append(i)
            else:
                for j, k in enumerate(c[1:]):
                    if i%k == 0:
                        break
                    elif j == len(c)-2:
                        c.append(i)
    return c

ans = cal(a, b)
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import math

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


ans = 1
sosuu = [2]
A = min(a,b)+1
for L in range(3, A, 2): # 2 以外の素数は奇数なので
    for L2 in sosuu:
        if L % L2 == 0:
            break # 素数でないことがわかったらそれ以上ループする必要はない
    else: # break で抜けることがなかったら L は素数（Python 特有の制御構文）
        sosuu.append(L)
        if a%L==0 and b%L==0:
            ans += 1

if a%2==0 and b%2==0:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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


ans = 1
sosuu = [2]
A = min(a,b)+1
for L in range(3, A, 2): # 2 以外の素数は奇数なので
    if all(L % L2 != 0 for L2 in sosuu):  # すべての既存素数で割り切れなかったら素数
        sosuu.append(L)
        if a%L==0 and b%L==0:
            ans += 1

if a%2==0 and b%2==0:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

if min(a,b) == 1:
    print(1)
    exit()

ans = 1
tmp = 1
for i in range(2,(max(a,b)+1)):
    if a%i == 0 and b%i == 0:
        l = factorization(i)
        for j in range(len(l)):
            if tmp%l[j][0] == 0:
                break
            else:
                tmp *= l[j][0]
        else:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def cin():
    in_ = list(map(int,input().split()))
    if len(in_) == 1:  return in_[0]
    else:  return in_

def sieve(N):
    p = 0
    prime = []
    is_prime = [1 for _ in range(N + 1)]
    is_prime[0], is_prime[1] = 0, 0
    for i in range(2, N + 1):
        if is_prime[i]:
            p += 1
            temp = i
            prime.append(i)
            while(temp <= N):
                is_prime[temp] = 0
                temp += i
            is_prime[i] = 1
    return prime
  
A, B = cin()
s = sieve(min(A, B))
s.append(1)
ans = 0
for i in s:
    if A % i == 0 and B % i == 0:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

stdin = sys.stdin

nm = lambda: map(int, stdin.readline().split())

a, b = nm()

n = math.gcd(a,b)

count = 1 # 1
for i in range(2, n+1):
    if n%i ==0:
        count +=1
        while n%i == 0:
            n = n/i
    if n ==1:
        break

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())

a, b = nm()

n = math.gcd(a,b)

m = int(n**(1/2))


count = 1 # 1
for i in range(2, n+1):
    if n%i ==0:
        count +=1
        while n%i == 0:
            n = n/i
    if n ==1:
        break

print(count)

Submission status: Time Limit Exceeded

Solution code:
import math

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

def divisor(x):
    divs = []
    for i in range(1, math.floor(math.sqrt(x))+1):
        if x%i == 0:
            divs.append(i)
            if i**2 != x:
                divs.append(x//i)
    return divs

codiv = set(divisor(A)) & set(divisor(B))

for i in codiv:
    if len(divisor(i)) <= 2:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
def check1(a,b):
  check_num=[]
  for i in range(1,min(a,b)+1):
    if a%i==0 and b%i==0:
      check_num.append(i)
  return check_num
def check2(n):
  if n==2:
    return True
  if n%2==0:
    return False
  for i in range(3,int(n**.5)+1,2):
    if n%i==0:
      return False
  return True

a,b=map(int,input().split())
number=check1(a,b)
result=[]
for i in number:
  result.append(check2(i))
print(sum(result))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
@lru_cache(maxsize=None)
def check(a,b):
  check_num=[]
  for i in range(1,min(a,b)+1):
    if a%i==0 and b%i==0:
      check_num.append(i)
  return check_num
def check2(n):
  if n==2:
    return True
  if n%2==0:
    return False
  for i in range(3,int(n**.5)+1,2):
    if n%i==0:
      return False
  return True

a,b=map(int,input().split())
count=0
check_1=check(a,b)
check_2=[]
for i in range(len(check_1)):
  for j in range(i+1,len(check_1)):
    if check2(check_1[i]) and check2(check_1[j]):
      check_2.append(check_1[i])
      check_2.append(check_1[j])
print(len(set(check_2)) if check_2 else 1 if check_1 else 0)

Submission status: Time Limit Exceeded

Solution code:
def check(a,b):
  check_num=[]
  for i in range(1,min(a,b)+1):
    if a%i==0 and b%i==0:
      check_num.append(i)
  return check_num
def check2(n):
  if n==2:
    return True
  if n%2==0:
    return False
  for i in range(3,int(n**.5)+1,2):
    if n%i==0:
      return False
  return True

a,b=map(int,input().split())
count=0
check_1=check(a,b)
check_2=[]
for i in range(len(check_1)):
  for j in range(i+1,len(check_1)):
    if check2(check_1[i]) and check2(check_1[j]):
      check_2.append(check_1[i])
      check_2.append(check_1[j])
print(len(set(check_2)) if check_2 else 1 if check_1 else 0)

Submission status: Time Limit Exceeded

Solution code:
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

import itertools
import math
def main():
    a,b=map(int,input().split())
    x=[y for y in make_divisors(a) if b%y==0]
    ans = 0
    for e in itertools.product([0,1], repeat=len(x)):
        t = [x[i] for i,v in enumerate(e) if v==1]
        for i, j in itertools.combinations(t, 2):
            if math.gcd(i, j) != 1:
                break
        else:
            ans = max(ans, e.count(1))
    print(ans)
                
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache


@lru_cache(maxsize=None)
def get_dividers(n):
    """
    正の整数 n の約数を取得する
    """

    dividers = {i for i in range(1, int(n ** 0.5) + 1) if n % i == 0}
    return dividers | {n // d for d in dividers}


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

a_dividers = get_dividers(A)
b_dividers = get_dividers(B)
common_dividers = a_dividers & b_dividers
ans = []

for cd in sorted(common_dividers):
    dividers = get_dividers(cd) - {1}
    for d in ans:
        if d & dividers:
            break
    else:
        ans.append(dividers)

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
a,b = map(int,input().split())
#素数列挙
sosu = [2]
li = min(a,b)
for i in range(3,li+1,2):
    f = 0
    for j in sosu:
        if i%j == 0:
            f = 1
            break
    if f == 0:
        sosu.append(i)

sosu.append(1)
ans = 0
for i in sosu:
    if a%i == 0 and b%i == 0:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
a,b = map(int,input().split())
#素数列挙
sosu = [2]
li = min(a,b)
for i in range(3,li+1):
    if all(i%j != 0 for j in sosu):
        sosu.append(i)

sosu.append(1)
ans = 0
for i in sosu:
    if a%i == 0 and b%i == 0:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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

count = 0

num = min(A,B)
num_list= [i for i in range(2, num+1)]
prime_list = []
count = 1

if num == 1:
    pass
else:
    while True:
        prime = min(num_list)
        if prime > math.sqrt(num):
            break
        if (A%prime ==0) &(B%prime ==0):
            prime_list.append(prime)
        j = 0
        while j < len(num_list):
            if num_list[j]%prime == 0:
                num_list.pop(j)
            j +=1


print(1 + len(prime_list))

Submission status: Time Limit Exceeded

Solution code:
a,b=map(int,input().split())
import math
c= math.gcd(a,b)
l=[]
i=2
while i<=c:
  if c % i==0:
    c=c//i
    l.append(i)
  else:
    i+=1
print(len(set(l))+1)

Submission status: Time Limit Exceeded

Solution code:
#1は含まれない
def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1


A,B=map(int,input().split())
L = cf(A,B)
cnt = 1
for l in L:
    if is_prime(l):
        cnt+=1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    table = sorted(table)
    return table

def make_prime(U):
    is_prime = np.zeros(U,np.bool)
    is_prime[2] = 1
    is_prime[3::2] = 1
    M = int(U**.5)+1
    for p in range(3,M,2):
        if is_prime[p]:
            is_prime[p*p::p+p] = 0
    return is_prime, is_prime.nonzero()[0]
A, B = map(int, input().split())

A_list = set(divisor(A))
B_list = set(divisor(B))

list = A_list & B_list

_, primes = make_prime(10**9)

cnt = 1

for i in list:
    if i in primes:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

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

d = gcd(A, B)
ans = 1
i = 2
for i in range(2, round(pow(d, 2/1))):
  if d%i == 0:
    ans += 1
    while d%i == 0:
      d //= i
  i += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

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

d = gcd(A, B)
ans = 1
i = 2
while i <= d:
  if d%i == 0:
    ans += 1
    while d%i == 0:
      d //= i
  i += 1
print(ans)

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

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

print(len(cf))

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

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

res = 1
for c in cf:
    if is_prime(c):
        res += 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

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

m = gcd(A, B)
#print(m)

num = m+1
ans = 1

for i in range(2,num):
    if m%i:
        continue
    ans += 1
    while not m%i:
        m = m/i

print(ans)

Submission status: Time Limit Exceeded

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

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

def judge_prime(x):
    cnt = 0
    for i in range(1, int(x ** 0.5) + 1):
        if x % i == 0:
            cnt += 1
    if cnt == 1:
        return True
    return False

div_a = div(a)
div_b = div(b)

data = list(set(div_a) & set(div_b))

ans = 0
for x in data:
    if judge_prime(x):
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a,b=map(int,input().split())
def c(n):
  s=set([1])
  if n%2==0:
    s.add(2)
    while n%2==0:
      n//=2
  i=1
  while n>1:
    i+=2
    if n%i==0:
      s.add(i)
      while n%i==0:
        n//=i
  return s
s=c(a)
l=list(s)
for x in l:
  if b%x!=0:
    s.remove(x)
print(len(s))

Submission status: Time Limit Exceeded

Solution code:
a,b=map(int,input().split())
def c(n):
  s=set()
  if n%2==0:
    s.add(2)
    while n%2==0:
      n//=2
  i=1
  while n>1:
    i+=2
    if n%i==0:
      s.add(i)
      while n%i==0:
        n//=i
  return s
s=(c(a)&c(b))
print(len(s)+1)

Submission status: Time Limit Exceeded

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


def make_divisors(n):

    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1

    return lower_divisors + upper_divisors[::-1]


def gcd(a, b):

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


da = make_divisors(A)
common_divisors = []

for d in da:
    if B % d == 0:
        common_divisors.append(d)

cd = set(common_divisors)
lim = common_divisors[-1]
for i in common_divisors[1:]:
    a = 2
    cur = a * i
    while cur <= lim:
        if cur in cd:
            cd.remove(cur)
        a += 1
        cur = a * i

print(len(cd))

Submission status: Time Limit Exceeded

Solution code:
import math
from fractions import gcd
a,b=map(int,input().split())
gd = gcd(a,b)
gd_bun=list()
valid = [0 for i in range(int(math.sqrt(gd))+1)]
b=2
tmp=gd
while 1:
  if tmp %b==0:
    while 1:
      tmp = tmp // b
      gd_bun.append(b)
      if tmp%b:
        break
  if tmp==1:
    break
  b+=1
print(1+len(list(set(gd_bun))))

Submission status: Time Limit Exceeded

Solution code:
import math
from fractions import gcd
a,b=map(int,input().split())
gd = gcd(a,b)
gd_bun=list()
valid = [0 for i in range(int(math.sqrt(gd))+1)]
b=2
tmp=gd
while 1:
  if tmp %b==0:
    while 1:
      tmp = tmp // b
      gd_bun.append(b)
      if tmp%b:
        break
  if tmp==1:
    break
  b+=1
print(1+len(list(set(gd_bun))))

Submission status: Time Limit Exceeded

Solution code:
import fractions
import math

A,B=map(int,input().split())
C=fractions.gcd(A,B)
S=[]

for i in range(1,C+1):
    if C%i==0:
        S.append(i)
    

#print(S)

count=0
T=[]
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 range(2,100):
    tmp=is_prime(i)
    if tmp==True:
        T.append(i)
#print(T)
for i in range(len(S)):
    if S[i]in T:
        count+=1
        
count+=1

print(count)

Submission status: Time Limit Exceeded

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

# 最大公約数の算出
y = max(A,B)
x = min(A,B)
while y%x != 0:
  tmp = x
  x = y%x
  y = tmp

# 素因数分解
n = 2
p = []
while x != 1:
  if x % n == 0:
    x /= n
    p.append(n)
  else:
    n += 1
p.append(int(x))
p = list(set(p))
print(len(p))

Submission status: Time Limit Exceeded

Solution code:
import fractions
import itertools
from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

def dv(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
    
A,B = map(int,input().split())
Cd = list(set(dv(A))&set(dv(B)))
N = len(Cd)
ans = []
for i in range(N,0,-1):
    for c in itertools.combinations(Cd,i):
        if not c:
            continue
        Flag = 1
        for i in itertools.combinations(c, 2):
            if gcd_list(i) != 1:
                Flag = 0
                break
        if Flag == 1:
           ans.append(len(c))
    if ans:
        print(max(ans))
        exit()

Submission status: Time Limit Exceeded

Solution code:
import fractions
import itertools
from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

def dv(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
    
A,B = map(int,input().split())
Cd = list(set(dv(A))&set(dv(B)))
N = len(Cd)
ans = 0
for bit in range(1<<N):
    d = []
    for i in range(N):
        if (bit>>i)&1 == 1:
            d.append(Cd[i])
    if not d:
        continue
    Flag = 1
    for i in itertools.combinations(d, 2):
        if gcd_list(i) != 1:
            Flag = 0
            break
    if Flag == 1:
        ans = max(ans,len(d))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import itertools
from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

def dv(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
    
A,B = map(int,input().split())
Cd = list(set(dv(A))&set(dv(B)))
N = len(Cd)
ans = 0
for bit in range(1<<N):
    d = []
    for i in range(N):
        if (bit>>i)&1 == 1:
            d.append(Cd[i])
    if not d:
        continue
    Flag = 1
    for i in itertools.permutations(d, 2):
        if gcd_list(i) != 1:
            Flag = 0
            break
    if Flag == 1:
        ans = max(ans,len(d))
print(ans)

Submission status: Time Limit Exceeded

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

y = max(A,B)
x = min(A,B)
while y%x != 0:
  tmp = x
  x = y%x
  y = tmp

p = [1]
for val in range(2,x+1):
  flag = 1
  if val == 2 and x % val == 0:
    p.append(val)
  elif val % 2 != 0 and x % val == 0:
    for i in range(2,int(math.sqrt(val))+1):
      if val % i == 0:
        flag = 0
        break
    if flag == 1:
      p.append(val)
print(len(p))

Submission status: Time Limit Exceeded

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

y = max(A,B)
x = min(A,B)
while y%x != 0:
  tmp = x
  x = y%x
  y = tmp

p = [1]
for val in range(2,x+1):
  flag = 1
  if x % val == 0:
    for i in range(2,int(math.sqrt(val))+1):
      if val % i == 0:
        flag = 0
        break
    if flag == 1:
      p.append(val)
print(len(p))

Submission status: Time Limit Exceeded

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

y = max(A,B)
x = min(A,B)
while y%x != 0:
  tmp = x
  x = y%x
  y = tmp
#print(x)

p = [1]
for val in range(2,x+1):
  flag = 1
  if x % val == 0:
    for i in range(2,int(math.sqrt(val))+1):
      if val % i == 0:
        flag = 0
    if flag == 1:
      p.append(val)
print(len(p))

Submission status: Time Limit Exceeded

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

y = max(A,B)
x = min(A,B)
while y%x != 0:
  tmp = x
  x = y%x
  y = tmp
#print(x)

p = [1,2]
for val in range(3,x+1):
  flag = 1
  for i in range(2,int(math.sqrt(val))+1):
    if val % i == 0:
      flag = 0
  if flag == 1:
    p.append(val)
out = []
for i in range(len(p)):
  if x%p[i] == 0:
    out.append(p[i])
print(len(out))

Submission status: Time Limit Exceeded

Solution code:
import math

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

def get_sieve_of_eratosthenes(n):
    data = [i for i in range(2, n + 1)]
    for d in range(2, math.ceil(n**0.5)):
        data = [x for x in data if (x == d or x % d != 0)]
    return data

def check():
    A, B = map(int, input().split())
    divisor_list = cf(A,B)
    if not divisor_list:
        print(1)
    else:
        prime_list = get_sieve_of_eratosthenes(max(divisor_list))
        print(sum([1 for i in divisor_list if i in prime_list])+1)
check()

Submission status: Time Limit Exceeded

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

def check():
    A, B = map(int, input().split())
    divisor_list = cf(A,B)
    if not divisor_list:
        print(1)
    else:
        prime_list = get_sieve_of_eratosthenes(max(divisor_list))
        print(sum([1 for i in divisor_list if i in prime_list])+1)
check()

Submission status: Time Limit Exceeded

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

import math
def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False
  
  m = math.floor(math.sqrt(n)) + 1
  for p in range(3, m, 2):
      if n % p == 0:
        return False
  return True
import math
A,B=map(int,input().split())
ans=cf(A,B)
trueans=0
for a in ans:
    if isPrime(a):
        trueans+=1

print(trueans)

Submission status: Time Limit Exceeded

Solution code:
A, B = [int(s) for s in input().split(' ')]
limit = min(A, B) // 2
p = dict()
p[0] = 0
p[1] = 0
d = dict()
d[1] = 1 
primes = []
for i in range(2, limit + 1):
    if i not in d:
        # prime
        count = 0
        j = i + i
        while A % i == 0 and B % i == 0:
            count += 1
            A //= i
            B //= i
            p[j] = 0
            j += i
        if count > 0:
            d[i] = count
        if A == 1 or B == 1:
            break
    else:
        continue

print(len(d.keys()))

Submission status: Time Limit Exceeded

Solution code:
a, b = list(map(int, input().split(' ')))
def gcd(l, s):
  return l if s == 0 else gcd(s, l % s)

temp = gcd(a, b)

ans = 0
for i in range(2,1000000000):
  if temp % i == 0:
    ans += 1
    while temp % i == 0:
      temp = temp // i
  if temp == 1:
    break

print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
a, b = list(map(int, input().split(' ')))
def gcd(l, s):
  return l if s == 0 else gcd(s, l % s)

temp = gcd(a, b)

primes = [2]
def is_prime(p):
  for i in range(len(primes)):
    if p % primes[i] == 0:
      return False
    if primes[i] * primes[i] >= p:
      break
  return True

for p in range(3, 1000009, 2):
  if is_prime(p):
    primes.append(p)
ans = 0
for p in primes:
  if temp % p == 0:
    ans += 1
print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd


def is_prime(q):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False
    return pow(2, q-1, q) == 1


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

a, b = map(int, input().split())
if a > b:
    ans = cf(a,b)
else:
    ans = cf(b,a)

print(ans)

Submission status: Time Limit Exceeded

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


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


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


c = cf(a, b)

print(len(c) + 1)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd


def is_prime(q):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False
    return pow(2, q-1, q) == 1


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

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

ans = cf(a,b)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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


def is_prime(q):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False
    return pow(2, q-1, q) == 1


a, b = map(int, input().split())
cf = cf(a,b)
ans = 1
for i in range(len(cf)):
    if is_prime(cf[i]):
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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


def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


a_s = make_divisors(a)
b_s = make_divisors(b)


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


cnt = 0
for i in a_s:
    if isPrime(i):
        if i in b_s:
            cnt += 1

print(cnt + 1)

Submission status: Time Limit Exceeded

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


def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


def coprime2(a, b):
    return bltin_gcd(a, b) == 1


a_s = set(make_divisors(a))
b_s = set(make_divisors(b))

tmp = a_s & b_s
_max = max(tmp)


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


cnt = 0
for i in tmp:
    if isPrime(i):
        cnt += 1

print(cnt + 1)