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 fractions

def return_prime(aa):
    a_list = [1]
    prime_list = []
    if aa % 2 == 0:
        a_list.append(2)
    for i in range(3, aa + 1, 2):
        if len([i % prime for prime in prime_list if i % prime == 0]) == 0:
            prime_list.append(i)
            if aa % i == 0:
                a_list.append(i)
    return a_list

a, b = map(int, input().split())
a_list = return_prime(fractions.gcd(a, b))
print(len(set(a_list)))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        A, B = map(int, input().split())

        _gcd = gcd(A, B)

        root_gcd = _gcd ** 0.5
        p = 2
        prim_num = 1
        while p <= root_gcd or _gcd > 1:
            tmp = _gcd
            while True:
                if _gcd % p == 0:
                    _gcd /= p
                else:
                    break
            if tmp != _gcd:
                prim_num += 1

            p += 1
        print(prim_num)


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

def main():
    A, B = [int(i) for i in input().split()]
    G = gcd(A, B)
    factor = set()
    i = 2
    while G > 1:
        while True:
            if G % i == 0:
                factor.add(i)
                G = G // i
            else:
                break
        i += 1
    print(len(list(factor))+1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

def main():
    A, B = [int(i) for i in input().split()]
    G = gcd(A, B)
    factor = set()
    i = 2
    while G != 1:
        while True:
            if G % i == 0:
                factor.add(i)
                G = G // i
            else:
                break
        i += 1
    print(len(list(factor))+1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

    G = gcd(A, B)
    factor = set()
    i = 2
    while G != 1:
        while True:
            if G % i == 0:
                factor.add(i)
                G = G // i
            else:
                break
        i += 1
    print(len(list(factor))+1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())


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

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return table


l = gcd(n, m)

ans = 0
i = 2

while(l != 1):
    if(n % i == 0 and m % i == 0 and l % i == 0):
        ans += 1

    while(l % i == 0):
        l //= i
    i += 1

print(ans + 1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())


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

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return table


l = gcd(n, m)

ans = 0

for i in range(2, l+1):
    if(n % i == 0 and m % i == 0 and l % i == 0):
        ans += 1

    while(l % i == 0):
        l //= i

print(ans + 1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
sys.setrecursionlimit(10**6)
#input=sys.stdin.readline
show_flg=False
show_flg=True


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

a,b=MI()
g=gcd(a,b)
ans=set()
ans.add(1)



for i in range(2,int(g**0.5)+2):
    if g%i==0:
        ans.add(i)
        while g%i==0:
            g//=i

for i in range(2,g+1):
    if g%i==0:
        ans.add(i)
    
    
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

    G = gcd(A, B)
    factor = set()
    for i in range(2, G + 1):
        while G % i == 0:
            factor.add(i)
            G = G // 2
    print(len(list(factor))+1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
A,B=list(map(int,input().split(" ")))
def prime(N):
    p=[]
    for i in range(1,N+1):
        p.append(i)
        for j in range(2,i):
            if i%j==0:
                p.remove(i)
                break
    return p
def gcd(m,n):
    for i in range(max(m,n),0,-1):
        if m%i==0 and n%i==0:
            return i
            break

M=gcd(A,B)
pri=prime(M)
num=0
for i in range(len(pri)):
    if M%pri[i]==0:
        num+=1
print(num)

Submission status: Time Limit Exceeded

Solution code:
[A, B] = list(map(int, input().split()))
C = [i for i in range(1, min(A, B) + 1) if A % i == 0 and B % i == 0]
D = []
for i in C:
    for j in C:
        if i != j and j != 1 and i % j == 0:
            D.append(i)
E = list(set(C)-set(D))
print(len(E))

Submission status: Time Limit Exceeded

Solution code:
a, b = map(int, input().split())
k = []
for i in range(1, min(a, b)+1):
    if a % i == 0 and b % i == 0:
        k.append(i)
cnt = 0
for n in k:
    if n == 1:
        cnt += 1
    elif n == 2:
        cnt += 1
    else:
        flg = ""
        for p in range(2, n):
            if n % p == 0:
                flg = "composite"
                break
            else:
                flg = "prime"
        if flg == "prime":
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# ABC142D - Disjoint Set of Common Divisors
def gcd(x: int, y: int) -> int:
    while y:
        x, y = y, x % y
    return x


def prime_factors(x: int) -> list:
    if x % 2:
        max_prime, factors = 0, []
    else:
        max_prime, factors = 2, [2]
        while x % 2 == 0:
            x //= 2
    for i in range(3, x + 1, 2):
        if x % i == 0:
            max_prime = i
            factors.append(i)
            while x % i == 0:
                x //= i
    if x > 2:  # when x is prime greater than 2
        factors.append(x)
    return factors


def main():
    # compute the number of prime factors of gcd(A, B)
    A, B = map(int, input().split())
    g = gcd(A, B)
    ans = len(prime_factors(g)) + 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

f = fractions.gcd(A, B)

kouyakusuu = []

if f % 2 == 0:
    kouyakusuu.append(2)
    while f % 2 == 0:
        f = f / 2

for i in range(3, int(f)+1, 2):
    # print(f, i)
    if f % i != 0:
        continue
    else:
        kouyakusuu.append(i)
        while f % i == 0:
            f = f / i
    if f == 1:
        break
print(len(kouyakusuu)+1)

Submission status: Time Limit Exceeded

Solution code:
[A, B] = list(map(int, input().split()))
C = []
D = []
for i in range(1, round(A/2)+2):
    if A % i == 0 and B % i == 0:
        C.append(i)
if len(C) > 2:
    for i in range(2, len(C)):
        for j in range(1, i):
            if C[i] % C[j] == 0:
                D.append(C[i])
E = list(set(C) - set(D))
print(len(E))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

def trial_division(n):
    f = 2
    d = {}
    while n > 1:
        if n % f == 0:
            d[f] = d.get(f,0) + 1
            n//=f
        else:
            f += 1
    return d

g = gcd(*map(int, input().split()))
ans = trial_division(g)
print(len(ans)+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from fractions import gcd

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

g = gcd(a,b)

def sosuu(a):
    sosuu_list = set()
    sosuu_list.add(1)
    i = 2
    while 1:
        flag = True
        while a > i:
            if a % i == 0:
                # print(a,i)
                a = a//i
                sosuu_list.add(i)
                flag = False
            else:
                i += 1
        if flag:
            sosuu_list.add(a)
            return sosuu_list
        i += 1

a = sosuu(g)
print(len(a))

Submission status: Time Limit Exceeded

Solution code:
import math
#最大公約数
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)
#因数分解
def factorize(x):
    ans=1#約数１
    div=2
    flag=0
    while div<=x:
        while x%div==0:
            x=x//div
            flag=1
        if flag==1:
            ans+=1
        div+=1
        flag=0
    return ans

a,b=map(int,input().split())
g=gcd(a,b)
f=factorize(g)
print(f)

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

f = fractions.gcd(A, B)

kouyakusuu = []
# print(f)
for i in range(2, f+1):
    # print(f, i)
    if f % i != 0:
        continue
    else:
        kouyakusuu.append(i)
        while f % i == 0:
            f = f / i
    if f == 1:
        break
# print(kouyakusuu)
print(len(kouyakusuu)+1)

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

f = fractions.gcd(A, B)

kouyakusuu = []
for i in range(2, f+1):
    if f % i != 0:
        continue
    else:
        kouyakusuu.append(i)
        while f % i == 0:
            f = f / i
print(len(kouyakusuu)+1)

Submission status: Time Limit Exceeded

Solution code:

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

def bunkai(n):
    sosu= {1}
    tmp = n
    stop_flag = n
    
    if tmp%2 == 0:
        while tmp%2==0:
            tmp //=2
        sosu.add(2)
    
    for i in range(3,n+1,2):
        if tmp%i == 0:
            while tmp%i==0:
                tmp //=i
            sosu.add(i)
            stop_flag = tmp 
            
        if i > stop_flag:
            break
#        else:
#            stop_flag = int(stop_flag/i) 
            
    if tmp!=1:
        sosu.add(tmp)
                
    if sosu==[1]:
        sosu.add(n)
    
    return sosu

def check_sosu(n,x):
    ans=0
    tmp = n
    for i in x:
        if (tmp % i) == 0:
            ans+=1
    return ans

ans = check_sosu(B,bunkai(A))

print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

def bunkai(n):
    sosu= {1}
    tmp = n
    stop_flag = n
    
    for i in range(2,n+1):
        if tmp%i == 0:
            while tmp%i==0:
                tmp //=i
            sosu.add(i)
            stop_flag = tmp 
            
        if i > stop_flag:
            break
#        else:
#            stop_flag = int(stop_flag/i) 
            
    if tmp!=1:
        sosu.add(tmp)
                
    if sosu==[1]:
        sosu.add(n)
    
    return sosu

def check_sosu(n,x):
    ans=0
    tmp = n
    for i in x:
        if (tmp % i) == 0:
            ans+=1
    return ans

ans = check_sosu(B,bunkai(A))

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)
	else : return gcd(b, a % b)
		
G = gcd(A, B)
ctr = 1
for i in range(2, G + 1):
    if G == 1: 
        break
    if G % i == 0: 
        ctr += 1
    while G % i == 0:
        G /= i
        
        
print(ctr)

Submission status: Time Limit Exceeded

Solution code:
import math
#1は入っていない
#素数判定
def primesqrt(x):
    for i in range(1,math.floor(math.sqrt(x))+1):
        if x%i==0 and i!=1:
            return False
        #print(sosu)
    return True

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

ans=1
for num in yaku:
    if primesqrt(num):
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
a,b = map(int,input().split())
div_list = []
ans = 0
check = 0
ans_list = []
for i in range(1,min(a,b)):
    if a%i == 0 and b%i == 0:
        div_list.append(i)
if min(a,b) == 1:
    print(1)
    sys.exit()

#print(div_list)
ans_list.append(div_list[1])
for i in range(1,len(div_list)):
    check = 0
    for j in ans_list:
        if div_list[i] % j == 0:
            check = 1
            break
    if check == 0:
        ans_list.append(div_list[i])
ans_list.append(1)
print(len(ans_list))

Submission status: Time Limit Exceeded

Solution code:
import sys
a,b = map(int,input().split())
div_list = []
ans = 0
for i in range(1,min(a,b)):
    if a%i == 0 and b%i == 0:
        div_list.append(i)
if min(a,b) == 1:
    print(1)
    sys.exit()

#print(div_list)

for i in range(1,len(div_list)):
    for j in div_list[1:i]:
        if div_list[i] % j == 0:
            ans += 1
            break
print(len(div_list) - ans)

Submission status: Time Limit Exceeded

Solution code:
a,b=map(int,input().split())
yaku=[]
flag=0
for i in range(2,min(a,b)+1):
    if a%i==0 and b%i==0:
        yaku.append(i)
ans=len(yaku)
flag=0
for i in range(1,len(yaku)+1):
    flag=0
    for j in range(i+1,len(yaku)+1):
        if yaku[-i]%yaku[-j]==0:
            flag=1
            #print(i)
            break
    if flag==1:
        ans-=1
        #print("ans=",ans)
print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
import math

class Prime:
    seeds = [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 ,101 ,103 ,107 ,109 ,113 ,127 ,131 ,137 ,139 ,149 ,151 ,157 ,163 ,167 ,173 ,179 ,181 ,191 ,193 ,197 ,199 ,211 ,223 ,227 ,229 ,233 ,239 ,241 ,251 ,257 ,263 ,269 ,271 ,277 ,281 ,283 ,293 ,307 ,311 ,313 ,317 ,331 ,337 ,347 ,349 ,353 ,359 ,367 ,373 ,379 ,383 ,389 ,397 ,401 ,409 ,419 ,421 ,431 ,433 ,439 ,443 ,449 ,457 ,461 ,463 ,467 ,479 ,487 ,491 ,499 ,503 ,509 ,521 ,523 ,541 ,547 ,557 ,563 ,569 ,571 ,577 ,587 ,593 ,599 ,601 ,607 ,613 ,617 ,619 ,631 ,641 ,643 ,647 ,653 ,659 ,661 ,673 ,677 ,683 ,691 ,701 ,709 ,719 ,727 ,733 ,739 ,743 ,751 ,757 ,761 ,769 ,773 ,787 ,797 ,809 ,811 ,821 ,823 ,827 ,829 ,839 ,853 ,857 ,859 ,863 ,877 ,881 ,883 ,887 ,907 ,911 ,919 ,929 ,937 ,941 ,947 ,953 ,967 ,971 ,977 ,983 ,991 ,997 ,1009 ,1013 ,1019 ,1021 ,1031 ,1033 ,1039 ,1049 ,1051 ,1061 ,1063 ,1069 ,1087 ,1091 ,1093 ,1097 ,1103 ,1109 ,1117 ,1123 ,1129 ,1151 ,1153 ,1163 ,1171 ,1181 ,1187 ,1193 ,1201 ,1213 ,1217 ,1223 ,1229 ,1231 ,1237 ,1249 ,1259 ,1277 ,1279 ,1283 ,1289 ,1291 ,1297 ,1301 ,1303 ,1307 ,1319 ,1321 ,1327 ,1361 ,1367 ,1373 ,1381 ,1399 ,1409 ,1423 ,1427 ,1429 ,1433 ,1439 ,1447 ,1451 ,1453 ,1459 ,1471 ,1481 ,1483 ,1487 ,1489 ,1493 ,1499 ,1511 ,1523 ,1531 ,1543 ,1549 ,1553 ,1559 ,1567 ,1571 ,1579 ,1583 ,1597 ,1601 ,1607 ,1609 ,1613 ,1619 ,1621 ,1627 ,1637 ,1657 ,1663 ,1667 ,1669 ,1693 ,1697 ,1699 ,1709 ,1721 ,1723 ,1733 ,1741 ,1747 ,1753 ,1759 ,1777 ,1783 ,1787 ,1789 ,1801 ,1811 ,1823 ,1831 ,1847 ,1861 ,1867 ,1871 ,1873 ,1877 ,1879 ,1889 ,1901 ,1907 ,1913 ,1931 ,1933 ,1949 ,1951 ,1973 ,1979 ,1987 ,1993 ,1997 ,1999 ,2003 ,2011 ,2017 ,2027 ,2029 ,2039 ,2053 ,2063 ,2069 ,2081 ,2083 ,2087 ,2089 ,2099 ,2111 ,2113 ,2129 ,2131 ,2137 ,2141 ,2143 ,2153 ,2161 ,2179 ,2203 ,2207 ,2213 ,2221 ,2237 ,2239 ,2243 ,2251 ,2267 ,2269 ,2273 ,2281 ,2287 ,2293 ,2297 ,2309 ,2311 ,2333 ,2339 ,2341 ,2347 ,2351 ,2357 ,2371 ,2377 ,2381 ,2383 ,2389 ,2393 ,2399 ,2411 ,2417 ,2423 ,2437 ,2441 ,2447 ,2459 ,2467 ,2473 ,2477 ,2503 ,2521 ,2531 ,2539 ,2543 ,2549 ,2551 ,2557 ,2579 ,2591 ,2593 ,2609 ,2617 ,2621 ,2633 ,2647 ,2657 ,2659 ,2663 ,2671 ,2677 ,2683 ,2687 ,2689 ,2693 ,2699 ,2707 ,2711 ,2713 ,2719 ,2729 ,2731 ,2741 ,2749 ,2753 ,2767 ,2777 ,2789 ,2791 ,2797 ,2801 ,2803 ,2819 ,2833 ,2837 ,2843 ,2851 ,2857 ,2861 ,2879 ,2887 ,2897 ,2903 ,2909 ,2917 ,2927 ,2939 ,2953 ,2957 ,2963 ,2969 ,2971 ,2999 ,3001 ,3011 ,3019 ,3023 ,3037 ,3041 ,3049 ,3061 ,3067 ,3079 ,3083 ,3089 ,3109 ,3119 ,3121 ,3137 ,3163 ,3167 ,3169 ,3181 ,3187 ,3191 ,3203 ,3209 ,3217 ,3221 ,3229 ,3251 ,3253 ,3257 ,3259 ,3271 ,3299 ,3301 ,3307 ,3313 ,3319 ,3323 ,3329 ,3331 ,3343 ,3347 ,3359 ,3361 ,3371 ,3373 ,3389 ,3391 ,3407 ,3413 ,3433 ,3449 ,3457 ,3461 ,3463 ,3467 ,3469 ,3491 ,3499 ,3511 ,3517 ,3527 ,3529 ,3533 ,3539 ,3541 ,3547 ,3557 ,3559 ,3571 ,3581 ,3583 ,3593 ,3607 ,3613 ,3617 ,3623 ,3631 ,3637 ,3643 ,3659 ,3671 ,3673 ,3677 ,3691 ,3697 ,3701 ,3709 ,3719 ,3727 ,3733 ,3739 ,3761 ,3767 ,3769 ,3779 ,3793 ,3797 ,3803 ,3821 ,3823 ,3833 ,3847 ,3851 ,3853 ,3863 ,3877 ,3881 ,3889 ,3907 ,3911 ,3917 ,3919 ,3923 ,3929 ,3931 ,3943 ,3947 ,3967 ,3989 ,4001 ,4003 ,4007 ,4013 ,4019 ,4021 ,4027 ,4049 ,4051 ,4057 ,4073 ,4079 ,4091 ,4093 ,4099 ,4111 ,4127 ,4129 ,4133 ,4139 ,4153 ,4157 ,4159 ,4177 ,4201 ,4211 ,4217 ,4219 ,4229 ,4231 ,4241 ,4243 ,4253 ,4259 ,4261 ,4271 ,4273 ,4283 ,4289 ,4297 ,4327 ,4337 ,4339 ,4349 ,4357 ,4363 ,4373 ,4391 ,4397 ,4409 ,4421 ,4423 ,4441 ,4447 ,4451 ,4457 ,4463 ,4481 ,4483 ,4493 ,4507 ,4513 ,4517 ,4519 ,4523 ,4547 ,4549 ,4561 ,4567 ,4583 ,4591 ,4597 ,4603 ,4621 ,4637 ,4639 ,4643 ,4649 ,4651 ,4657 ,4663 ,4673 ,4679 ,4691 ,4703 ,4721 ,4723 ,4729 ,4733 ,4751 ,4759 ,4783 ,4787 ,4789 ,4793 ,4799 ,4801 ,4813 ,4817 ,4831 ,4861 ,4871 ,4877 ,4889 ,4903 ,4909 ,4919 ,4931 ,4933 ,4937 ,4943 ,4951 ,4957 ,4967 ,4969 ,4973 ,4987 ,4993 ,4999]

    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.seeds: return True
        if any(map(lambda x: n % x == 0, self.seeds)): return False

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

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

        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.seeds[:_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.seeds[seed % len(Prime.seeds)]
        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

    def decompose(self, n):
        ps_max = self.seeds[-1]
        primes = {}

        for p in self.seeds:
            while n % p == 0:
                primes.setdefault(p, 0)
                primes[p] += 1
                n //= p

        while n > ps_max:
            factor = self.find_factor(n)
            while n % factor == 0:
              primes.setdefault(factor, 0)
              primes[factor] += 1
              n //= factor

        return primes

prime = Prime()

a, b = map(int, input().split())
primes = prime.decompose(prime.gcd(a, b))

print(len(primes) + 1)