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 math
from fractions import gcd

a, b = map(int, input().split())
cd = set()
ans = 0

g = gcd(a, b)

if g == 1:
    cd.add(1)
else:
    for i in range(1, g+1):
        if a % i == 0 and b % i == 0:
            cd.add(i)

for s in cd:
    if s == 1:
        ans += 1
    else:
        for t in range(2, int(math.sqrt(s)) + 1):
            if s % t == 0:
                break
        else:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import time
from collections import deque
from collections import defaultdict
from copy import deepcopy

mod = 10 ** 9 + 7
t = time.time()


def inv(n, mod):
    return power(n, mod-2)

def iip():
    ret = [int(i) for i in input().split()]
    if len(ret) == 1:
        return ret[0]
    return ret

def soinsuu_bunkai(n):
    ret = []
    for i in range(2, n):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    return ret


def main():
    A, B = iip()

    a = set(soinsuu_bunkai(A))
    b = set(soinsuu_bunkai(B))

    ans = 1 # 1の場合
    for aa in a:
        if aa in b:
            ans+=1

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import math

a, b = map(int, input().split())
cd = set()
ans = 0

for i in range(1, min(a, b) + 1):
    if a % i == 0 and b % i == 0:
        cd.add(i)

for s in cd:
    if s == 1:
        ans += 1
    else:
        for t in range(2, int(math.sqrt(s)) + 1):
            if s % t == 0:
                break
        else:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
a, b = map(int, input().split())
cd = set()
ans = 0

for i in range(1, min(a, b) + 1):
    if a % i == 0 and b % i == 0:
        cd.add(i)


for s in cd:
    if s == 1:
        ans += 1
    else:
        for t in range(2, s // 2 + 1):
            if s % t == 0:
                break
        else:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

for i in range(1, min(a, b) + 1):
    if a % i == 0 and b % i == 0:
        cd.add(i)

max_cd = max(cd)

for s in range(2, max_cd+1):
    remove = set()
    for t in cd:
        if s >= t:
            pass
        elif t % s == 0:
            remove.add(t)
    cd -= remove

print(len(cd))

Submission status: Time Limit Exceeded

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

for i in range(1, min(a, b) + 1):
    if a % i == 0 and b % i == 0:
        if i == 1:
            ans += 1
        else:
            for s in range(2, i // 2 + 1):
                if i % s == 0:
                    break
            else:
                ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

for i in range(1, min(a, b) + 1):
    if a % i == 0 and b % i ==0:
        for s in range(2, i-1):
            if i % s == 0:
                break
        else:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def prime_pair(n):
    pairs = {}
    tmp = n
    for i in range(2, n):
        if tmp % i != 0:
            continue
        ex = 0
        while tmp % i == 0:
            ex += 1
            tmp /= i
        pairs[i] = ex
    return pairs

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


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

ppa = prime_pair(A)
ppb = prime_pair(B)

g = gcd(A,B)
ppg = prime_pair(g)

print(len(ppg.keys())+1)

Submission status: Time Limit Exceeded

Solution code:
import math

import math
def Sieve_of_Eratosthenes(N):
    if N<2: return set()
    prime=set(i for i in range(2,N+1))
    for i in range(2,math.ceil(N**0.5)+1):
        tmp=set()
        for j in prime:
            if j>i and j%i==0: tmp.add(j)
        for j in tmp:
            prime.remove(j)

    return prime

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

a,b=map(int,input().split())
n=gcd(a,b)
prime=list(Sieve_of_Eratosthenes(int(math.sqrt(n))+2))

ans=1
x=n
for p in prime:
    if x==1:
        break
    if x%p==0:
        ans+=1
        while x%p==0:
            x=x//p

if x!=1: ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

import math
def Sieve_of_Eratosthenes(N):
    if N<2: return set()
    prime=set(i for i in range(2,N+1))
    for i in range(2,math.ceil(N**0.5)+1):
        tmp=set()
        for j in prime:
            if j>i and j%i==0: tmp.add(j)
        for j in tmp:
            prime.remove(j)

    return prime

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

a,b=map(int,input().split())
n=gcd(a,b)
prime=Sieve_of_Eratosthenes(int(math.sqrt(n))+2)

dic={}
ans=1
x=n
for p in prime:
    if x==1:
        break
    if x%p==0:
        ans+=1
        while x%p==0:
            x=x//p

if x!=1: ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

import math
def Sieve_of_Eratosthenes(N):
    if N<2: return set()
    prime=set(i for i in range(2,N+1))
    for i in range(2,math.ceil(N**0.5)+1):
        tmp=set()
        for j in prime:
            if j>i and j%i==0: tmp.add(j)
        for j in tmp:
            prime.remove(j)

    return prime

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

a,b=map(int,input().split())
n=gcd(a,b)
prime=Sieve_of_Eratosthenes(int(math.sqrt(n))+2)

dic={}
ans=1
x=n
for p in prime:
    if x%p==0:
        ans+=1
        while x%p==0:
            x=x//p

if x!=1: ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

maxp = int(max(A,B)**0.5)
num = [x for x in range(2,maxp+1)]
ps = []
while num :
    num_min = min(num)
    if num_min >= maxp :
        break
    ps.append(num_min)
    for i in range(len(num)) :
        if i >= len(num) :
            break
        if num[i]%num_min == 0 :
            num.pop(i)

ans = 1
for p in ps :
    if A%p == 0 and B%p == 0 :
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from fractions import gcd

def main():
    a,b=map(int,input().split())
    g=gcd(a,b)
    prime=[i for i in range(g+1)]
    for i in range(2,int(g**0.5)+1):
        cnt=2
        if prime[i]>0:
            while cnt*i<=g:
                prime[cnt*i]=0
                cnt+=1
    ans=1
    for i in prime:
        if i<=1:
            continue
        else:
            if g%i==0:
                ans+=1
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

def get_sieve_of_eratosthenes(n):#n以下の素数のリストを返す
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
    return(data)

n=gcd(A,B)
ans = 1
if n==1:
    print(1)
else:
    plist = get_sieve_of_eratosthenes(n)
    for p in plist:
        if n==1:
            break
        if n%p==0:
            n = n//p
            ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


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 primes(x):
    is_prime = [True] * (x + 1)
    is_prime[0] = False
    is_prime[1] = False

    for i in range(1, int(sqrt(x))+1):
        if not is_prime[i]:
            continue
        for j in range(i*2, x+1, i):
            is_prime[j] = False

    ans = [1]
    for i in range(x+1):
        if is_prime[i]: ans.append(i)

    return ans


def main():
    A, B = MAP()

    lis_a = cf(A, B)
    lis_b = primes(lis_a[-1])
    cnt = 0 
    for a in lis_a:
        if a in lis_b: cnt += 1

    print(cnt)


if __name__ == '__main__':
        main()

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

A, B = MAP()

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 primes_for(n):
   is_prime = [True] * (n + 1)
   is_prime[0] = False
   is_prime[1] = False
   for i in range(2, n + 1):
       for j in range(i * 2, n + 1, i):
           is_prime[j] = False
   return [i for i in range(n + 1) if is_prime[i]]

a = cf(A, B)
b = primes_for(a[len(a) - 1])
b.append(1)

print(len(set(a) & set(b)))

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_left, bisect_right

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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


A, B = MAP()
a = divisor(A)
b = divisor(B)
a = set(a)
b = set(b)
kouyaku = a & b

ans = 1
for y in kouyaku:
    if len(divisor(y)) == 2:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math


# 公約数列挙
# 重複する約数は1つにまとまるので注意
def make_common_divisors(x1, x2):
    cd = [1]
    for i in range(2, min(x1, x2) + 1):
        if x1 % i == 0 and x2 % i == 0:
            cd.append(i)
    return cd


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


# 引数nが素数かどうかを判定
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


count = 1
for i in range(len(CD)):
    if is_prime(CD[i]):
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
m, n = map(int, input().split())
while True:
  if m < n:
    m, n = n, m
  if m%n:
    m, n = n, m%n
  else:
    break

def divisors(m):
    divisors = [1]
    for i in range(2, m+1):
        if m % i == 0:
            divisors.append(i)
        while m % i == 0:
            m //= i
        if m == 1:
            break
    return divisors

print(len(divisors(n)))

Submission status: Time Limit Exceeded

Solution code:
def divisors(m, n):
    divisors = [1]
    if m > n:
        m, n = n, m
    for i in range(2, m+1):
        if m % i == 0 and n % i == 0:
            divisors.append(i)
        while m % i == 0:
            m //= i
        while n % i == 0:
            n //= i
        if m == 1 or n == 1:
            break
    return divisors
m, n = map(int, input().split())
print(len(divisors(m, n)))

Submission status: Time Limit Exceeded

Solution code:
import sys
A,B = map(int,input().split())
answer = 1 #１で割ることは絶対に可能
if A%2 == 0 and B%2 == 0:
    answer += 1

if min(A,B) == 2:
    print(answer)
    sys.exit(0)
sosuu = [2]
A = min(A,B)
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:
            answer += 1
print(answer)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a,b):
    if a == 0 or b == 0:
        return max(a,b)
    else:
        c = max(a,b) % min(a,b)
        return gcd(c,min(a,b))

def prime(n):
    a = 2
    b = n
    ps = []
    while b != 1:
        if b % a == 0:
            ps.append(a)
            b /= a
        else:
            a += 1
    return ps

def count(ls):
    if ls == []:
        return 0
    else:
        n = len(ls)
        a = 1
        for i in range(n-1):
            if ls[i] != ls[i + 1]:
                a += 1
    return a

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

g = gcd(a,b)
ls = prime(g)
print(count(ls) + 1)

Submission status: Time Limit Exceeded

Solution code:
a, b = map(int, input().split())
c = min(a,b)
s = [1]
i = 2
while i <= c:
  if a%i==0 and b%i==0:
    a //= i
    b //= i
    if not(i in s):
      s.append(i)
    i = max(s)
    c = min(a,b)
  else:
    i += 1
print(len(s))

Submission status: Time Limit Exceeded

Solution code:
a, b = map(int, input().split())
c = min(a,b)
s = [1]
i = 2
while i <= c:
  if a%i==0 and b%i==0:
    a //= i
    b //= i
    if not(i in s):
      s.append(i)
    i = 2
    c = min(a,b)
  else:
    i += 1
print(len(s))

Submission status: Time Limit Exceeded

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

g = gcd(a,b)

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

Submission status: Time Limit Exceeded

Solution code:

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

a, b = map(int, input().split())
max = gcd(a, b)
pf=[]

#print(max)
tmp=max
i=2

while tmp != 1:
    if tmp%i == 0:
        pf.append(i)
        tmp=tmp/i
    else:
        i+=1

#print(pf)
spf = set(pf)
#print(spf)
print(len(spf)+1)

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

a, b = MAP()
kouyaku = set(divisor(a)) & set(divisor(b))
ans = 0
s = []
for k in kouyaku:
    except_one_k = divisor(k)
    # except_one_k.pop(0)
    # print(except_one_k)
    # s.append(divisor(k))
    if len(except_one_k) == 1 or len(except_one_k) == 2:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
A, B = map(int,input().split())
ans = 1
if A % 2 == 0 and B % 2 == 0:
    ans += 1
    while A % 2 == 0 and B % 2 == 0:
        A /= 2
        B /= 2
if A % 3 == 0 and B % 3 == 0:
    ans += 1
    while A % 3 == 0 and B % 3 == 0:
        A /= 3
        B /= 3
if A % 5 == 0 and B % 5 == 0:
    ans += 1
    while A % 5 == 0 and B % 5 == 0:
        A /= 5
        B /= 5

i = 3
while 2*i + 1 <= A and 2*i + 1 <= B:
    k = 2*i + 1
    if k % 3 == 0 or k % 5 == 0:
        i += 1
        continue
    elif A % k == 0 and B % k == 0:
        ans += 1
        A /= k
        B /= k
        while A % k == 0 and B % k == 0:
            A /= k
            B /= k
        i += 1
    else:
        i += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
A, B = map(int,input().split())
ans = 1
i = 2
while i <= A and i <= B:
    if A % i == 0 and B % i == 0:
        ans += 1
        A /= i
        B /= i
        while A % i == 0 and B % i == 0:
            A /= i
            B /= i
            continue
        i += 1
    else:
        i += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

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

def primes(n):
  primes = [2, 3]
  cands = list(range(3, n, 2))
  while True:
    last_prime = primes[-1]
    cands = [cand for cand in cands if cand % primes[-1] != 0]
    if len(cands) == 0:
      break
    primes.append(cands.pop(0))
  return primes
  

def main():
  a, b = map(int, input().strip().split())
  g = gcd(a, b)
  ps = []
  for p in primes(int(g ** 0.5)):
    if g % p == 0:
      ps.append(p)
    while g % p == 0:
      g //= p
      
  if g != 1:
    ps.append(g)
    
  print(len(ps) + 1)

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
A, B = (int(i) for i in input().split())
def euclid(a, b):
    while b:
        a, b = b, a%b
    return a
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
num = make_divisors(euclid(A,B))
if len(num) <= 2:
  print(len(num))
else:
  total_num  = [0]*len(num)
  for i in range(1,len(num)):
    for j in range(i,len(num)):
      #print(i)
      #print(" "+str(j))
      try:
        #print(i)
        #print(" "+str(j))
        tmp_index = num[i]*num[j]
        total_num[num.index(tmp_index)] = 1
      except:
        #print("NG")
        total_num = total_num
  print(total_num.count(0))

Submission status: Time Limit Exceeded

Solution code:
A, B = (int(i) for i in input().split())
def euclid(a, b):
    while b:
        a, b = b, a%b
    return a
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
num = make_divisors(euclid(A,B))
if len(num) <= 2:
  print(len(num))
else:
  total_num  = [0]*len(num)
  for i in range(1,len(num)):
    for j in range(i,len(num)):
      #print(i)
      #print(" "+str(j))
      try:
        #print(i)
        #print(" "+str(j))
        tmp_index = num[i]*num[j]
        total_num[num.index(tmp_index)] = 1
      except:
        #print("NG")
        total_num = total_num
  print(total_num.count(0))

Submission status: Time Limit Exceeded

Solution code:
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda x: [ni() for _ in range(x)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda x: [na() for _ in range(x)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda x: [ns() for _ in range(x)]
nas = lambda: stdin.readline().split()

a, b = na()

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

def primes(n):
    p = []
    i = 1
    while i * i <= n:
        if is_prime(i) or i == 1:
            p.append(i)
        if is_prime(n // i):
            p.append(n // i)
        i += 1
    return p

def p_fact(n):
    f = []
    for i in primes(n):
        if n % i == 0:
            f.append(i)
    return f

c, d = p_fact(a), p_fact(b)
e = [i if i in d else 1 for i in c]
f = set(e)
print(len(f))

Submission status: Time Limit Exceeded

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

# 素数だったら1を返す
def prime_number(n):
    for x in range(2,n):
        if n%x==0:
            return 0
    return 1

ans=0
m=min(a,b)//2+2
for i in range(1,m):
    if a%i==0 and b%i==0:
        ans+=prime_number(i)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

def sosuucheck(val):
    flg = True
    max_search = math.ceil(math.sqrt(val))
    if val <= 3:
        pass
    else:
        for i in range(2, max_search+1):
            if val % i == 0:
                flg = False
                break
    return flg

def yakusuu(a):
    t = []
    for i in range(1,a+1):
        if a%i==0:
            t.append(i)
    return t

def kouyakusuu(a,b):
    t = []
    u = 0
    d = 0
    if a>b:
        u = a
        d = b
    else:
        u = b
        d = a
    for i in range(1,d+1):
        if u%i==0 and d%i==0:
            t.append(i)
    return t

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

#t = list(map(yakusuu,kouyakusuu(a,b)))
t = kouyakusuu(a,b)
sn = 0
for i in t:
    if sosuucheck(i):
        sn += 1


print(sn)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
a, b = map(int, input().split())
g = gcd(a, b)
p = list()
for i in range(g-1):
  i += 2
  if g % (i) == 0:
    b = True
    for j in p:
      if (i) % j == 0:
        b = False
        break
    if b == True:
      p.append(i)
print(len(p)+1)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
from sys import stdin
from copy import deepcopy
from functools import reduce
from fractions import gcd
import math
import itertools
from collections import Counter
from itertools import chain  ##list(chain.from_iterable(l)) ##flatten
from heapq import heappush, heappop

"""
N = int(input())
A, B = map(int,input().split())
A = list(map(int,input().split())) ## 横一列
A = [int(input()) for _ in range(N)] ## 縦一列
lst = [list(map(int,input().split())) for i in range(M)] ## 二次元
"""

# 最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)


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)
        ref: 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())
num = gcd_list([A, B])
lst = prime.find_factors(num)
ans = 1 + len(lst)

#print(num)
#print(lst)
print(ans)