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: Runtime Error

Solution code:
a, b = map(int, input().split())
def gcd(p, q):
    if p < q:
        p, q = q, p
    while q > 0:
        p, q = q, p%q
    return p
  
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

divisors = make_divisors(gcd(a, b))

def prime(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for j in range(4, n+1, 2):
        is_prime[j] = False
    for i in range(3, int(n**0.5) + 1, 2):
        if not is_prime[i]:
            continue
        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]]

prime = [1] + prime(divisors[-1])
print(divisors, prime)
ans = set(divisors) & set(prime)
print(ans)
print(len(ans))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Oct  1 07:06:32 2019

@author: avina
"""
from math import gcd,sqrt
a,b = map(int, input().split())

num = gcd(a,b)
ans = 0

for i in range(2,num):
    if a%i == 0 and b%i == 0:
        w = int(sqrt(i))+1
        t = True
        for j in range(2,w):
            if i%j == 0:
                t = False
                break
        if t:
            ans+=1

print(ans+1)

Submission status: Runtime Error

Solution code:
#coding: UTF-8
import math
a,b=map(int,input().split())
def main(a,b):
    yakusuu=[]
    m=math.gcd(a,b)
    for i in range(m//2):
        if (m/(i+1)).is_integer():
            yakusuu.append(i+1)
    yakusuu.append(m)
    n=len(yakusuu)
    ans=n
    for i in reversed(range(n)):
        if yakusuu[i]>1:
            for j in range(i//2):
                if (yakusuu[i]/yakusuu[j+1]).is_integer():
                    yakusuu[i]=0
                    ans-=1
                    break
                #else:
                    #break
    print(ans)
main(a,b)

Submission status: Runtime Error

Solution code:
import math
import collections

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
    


a = 840
b = 1680

c = math.gcd(a,b)
d = collections.Counter(prime_factorize(c))
e = d.keys()
print(e)

Submission status: Runtime Error

Solution code:
from math import *

def next_int():
    return int(input())

def next_ints():
    return list(map(int, input().split()))

a, b = next_ints()
n = gcd(a, b)
ans = 1
i = 2
while i*i <= n:
    if n%i == 0:
        ans += 1
        while n%i == 0:
            n //= i
    i += 1
if n != 1:
    ans += 1
print(int(ans), end="")

Submission status: Runtime Error

Solution code:
from math import *

def next_int():
    return int(input())

def next_ints():
    return list(map(int, input().split()))

a, b = next_ints()
n = gcd(a, b)
ans = 1
i = 2
while i*i <= n:
    if n%i == 0:
        ans += 1
        while n%i == 0:
            n //= i
    i += 1
if n != 1:
    ans += 1
print(ans,end="")

Submission status: Runtime Error

Solution code:
from math import *

def next_int():
    return int(input())

def next_ints():
    return list(map(int, input().split()))

a, b = next_ints()
n = gcd(a, b)
ans = 1
i = 2
while i*i <= n:
    if n%i == 0:
        ans += 1
        while n%i == 0:
            n //= i
    i += 1
if n != 1:
    ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import math
 
def gcd(a,b):
  if b == 0:
    return a
  else:
    return gcd(b, a % b)
 
A, B = map(int, input().split(" "))
if A >= B:
  C = gcd(A,B)
else:
  C = gcd(B,A)

c = math.ceil(math.sqrt(C)) + 1
l = [1]
f = [1] + [0]*c

for i in range(2,c+1):
  if f[i-1] == 0:
    f[i-1] = 1
    if C % i == 0:
      l.append(i)
      while C % i == 0:
        C //= i
    for j in range(i+i, c+1, i):
      f[j-1] = 1
      
if C > 1:
  l.appned(C)

print(len(l))

Submission status: Runtime Error

Solution code:
import math
 
def gcd(a,b):
  if b == 0:
    return a
  else:
    return gcd(b, a % b)

A, B = map(int, input().split(" "))
if A >= B:
  C = gcd(A,B)
else:
  C = gcd(B,A)

#c = math.ceil(math.sqrt(C)) + 1
l = [1]
f = [0]*C
ans = 0
 
for i in range(2,C+1):
  if f[i-1] == 0:
    f[i-1] = 1
    if C % i == 0:
      l.append(i)
    for j in range(i+i, C+1, i):
      f[j-1] = 1

print(len(l))

Submission status: Runtime Error

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

h = [i for i in range(1,max(a, b))if a % i == 0 and b % i == 0]

import itertools
import math
x = 0
for c in itertools.combinations(h, 2):
    if math.gcd(c[0], c[1]) == 1:
        x = x +1
print(x)

Submission status: Runtime Error

Solution code:
import math
 
def gcd(a,b):
  if b == 0:
    return a
  else:
    return gcd(b, a % b)

A, B = map(int, input().split(" "))
if A >= B:
  C = gcd(A,B)
else:
  C = gcd(B,A)

#c = math.ceil(math.sqrt(C)) + 1
l = [1]
f = [0]*C
ans = 0
 
for i in range(2,C+1):
  if f[i-1] == 0:
    f[i-1] = 1
    l.append(i)
    for j in range(i+i, C+1, i):
      f[j-1] = 1

for i in l:
  if C % i == 0:
    ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import math

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

list_a = []
list_b = []
sqrt_a = math.sqrt(a)
sqrt_b = math.sqrt(b)


for i in range(2, float(sqrt_a) ):  
  if (a % (i) == 0):
    list_a.append( i )
    while( a % (i) == 0 ):
      a = a//(i)
      
for i in range(2, float(sqrt_b) ):  
  if (b % (i) == 0):
    list_b.append( i )
    while( b % (i ) == 0 ):
      b = b//(i)

#print(list_a)
#print(list_b)

set_a = set(list_a)
set_b = set(list_b)

set_ab = set_a & set_b
  
print(len(set_ab) + 1)

Submission status: Runtime Error

Solution code:
a, b = map(int, input().split())
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
n = gcd(a, b)

def cd(num):
    k = []
    if num%2 == 0:
        if is_prime(2):
            k.append(i) 
    for i in range(1,num+1):
        if num%i == 0:
            if is_prime(i):
                k.append(i) 
    return k

def is_prime(num):
    for i in range(2, num):
        if num % i == 0:
            return False
    return True


gc = gcd(a,b)
c = cd(gc)

print(len(c))

Submission status: Runtime Error

Solution code:
a, b = map(int, input().split())
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
n = gcd(a, b)

def cd(num):
    k = []
    if num%2 == 0:
        if is_prime(2):
            k.append(i) 
    for i in range(1,num+1,2):
        if num%i == 0:
            if is_prime(i):
                k.append(i) 
    return k

def is_prime(num):
    for i in range(2, num):
        if num % i == 0:
            return False
    return True


gc = gcd(a,b)
c = cd(gc)

print(len(c))

Submission status: Runtime Error

Solution code:
a, b = map(int, input().split())
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
n = gcd(a, b)

def cd(num):
    k = []
    if num%2 == 0:
        if is_prime(2):
    for i in range(1,num+1,2):
        if num%i == 0:
            if is_prime(i):
                k.append(i) 
    return k

def is_prime(num):
    for i in range(2, num):
        if num % i == 0:
            return False
    return True


gc = gcd(a,b)
c = cd(gc)

print(len(c))

Submission status: Runtime Error

Solution code:
a, b = map(int, input().split())
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
n = gcd(a, b)

def cd(num):
    k = []
    for i in [1,2] + list(range(3,num+1,2)):
        if num%i == 0:
            if is_prime(i):
                k.append(i) 
    return k

def is_prime(num):
    for i in range(2, num):
        if num % i == 0:
            return False
    return True


gc = gcd(a,b)
c = cd(gc)

print(len(c))

Submission status: Runtime Error

Solution code:
a, b = map(int, input().split())
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
n = gcd(a, b)

def cd(num):
    k = []
    for i in [1,2] + list(range(3,num+1)):
        if num%i == 0:
            if is_prime(i):
                k.append(i) 
    return k

def is_prime(num):
    for i in range(2, num):
        if num % i == 0:
            return False
    return True


gc = gcd(a,b)
c = cd(gc)

print(len(c))

Submission status: Runtime Error

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

def gcd(num):
    k = []
    for i in [1,2]+list(range(3, num+1, 2)):
        if num%i == 0:
            k.append(i) 
    return k

def is_prime(num):
    for i in range(2, num):
        if num % i == 0:
            return False
    return True

ka = gcd(a)
kb = []
for i in ka:
  if b%i == 0:
    if is_prime(i):
        kb.append(i)

print(len(kb))

Submission status: Runtime Error

Solution code:
def sieve(N, limit):
    is_prime = [True] * (N + 1)
    is_prime[0] = False
    is_prime[1] = False

    for i in range(2, limit + 1):
        if not is_prime[i]:
            continue
        for j in range(i + i, N + 1, i):
            is_prime[j] = False
    return [i for i in range(2, N + 1) if is_prime[i]]


A, B = map(int, input().split())
max_num = max(A, B)
limit = int(max_num ** 0.5)
primes = sieve(max_num, limit)
a_prime = {i for i in primes if A % i == 0}
b_prime = {i for i in primes if B % i == 0}

common = a_prime.intersection(b_prime)
print(len(common) + 1)

Submission status: Runtime Error

Solution code:
def sieve(N, limit):
    primes = []
    data = [i + 1 for i in range(1, N)]
    while True:
        p = data[0]
        if limit <= p:
            return primes + data
        primes.append(p)
        data = [e for e in data if e % p != 0]


A, B = map(int, input().split())
max_num = max(A, B)
limit = int(max_num ** 0.5)
primes = sieve(max_num, limit)
a_prime = {i for i in primes if A % i == 0}
b_prime = {i for i in primes if B % i == 0}

common = a_prime.intersection(b_prime)
print(len(common) + 1)

Submission status: Runtime Error

Solution code:
import itertools
from math import gcd
A,B = map(int,input().split())
div = min(A,B)
koyaku =[i for i in range(1,div+1) if A%i==0 and B%i==0]
pairs = list(itertools.combinations(koyaku,2))
todel = set()
for v in pairs:
  if(gcd(v[0],v[1])!=1):
    todel.add(max(v[0],v[1]))
for i in todel:
  koyaku.remove(i)

print(len(koyaku))

Submission status: Runtime Error

Solution code:
from math import gcd, sqrt, ceil

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


def PrimeFactorization(n: int):
    N = n

    counter = 0
    while n % 2 == 0:
        counter += 1
        n = n // 2
    thelist = [(2, counter)]

    for i in range(3, ceil(1 + sqrt(N)), 2):
        counter = 0
        while n % i == 0:
            n = n // i
            counter += 1
        if counter != 0:
            thelist.append((i, counter))

    return thelist


print(len(PrimeFactorization(g))+1)

Submission status: Runtime Error

Solution code:
#coding: utf-8
import math
# from fractions import gcd

# GCDの約数を素因数分解する
def primeFactor(n):
    flg = 0
    count = 0
    tmp = math.sqrt(n)
    i = 2

    if n == 1:
        return 1

    while i <= tmp:
        # print(str(i)+str(',')+str(gcd_cnt))
        if n % i == 0:
            if flg == 0:
                flg = 1
                count += 1
            n = n // i
        else:
            flg = 0
            i += 1
    # if flg == 1:
    #     count += 1
    # print(str('素数=')+str(count)+str(' n=')+str(n)+str(' i=')+str(i))
    if n > 1:
        count += 1
    # 1を足す
    count += 1
    return count


# # print(len(div))
m,n = map(int,input().split())
p = math.gcd(m,n)
# print(str('gcd=')+ str(p))
ans = primeFactor(p)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from io import StringIO
import unittest
import math
class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """12 18"""
        output = """3"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """420 660"""
        output = """4"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """1 2019"""
        output = """1"""
        self.assertIO(input, output)
def kouyaku(n):
    i=1
    table=[]
    while i*i<=n:
        if n%i==0:

            table.append(i)
            if i*i != n:
                table.append(n//i)
        i+=1

    table.sort()

    return table
def resolve():
    (A,B)=(int(i) for i in input().split())
    t=math.gcd(A,B)
    if t==1:
        print(1)
        return
    kouyakusu=kouyaku(t)
    count=1

    kouyakusu.remove(1)

    while kouyakusu!=[]:

        x=kouyakusu[0]
        count+=1
        kouyakusu=[i for i in kouyakusu if i%x !=0]
    print(count)


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
import sys
from io import StringIO
import unittest
import math
class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """12 18"""
        output = """3"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """420 660"""
        output = """4"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """1 2019"""
        output = """1"""
        self.assertIO(input, output)
def kouyaku(n):
    i=1
    table=[]
    while i*i<=n:
        if n%i==0:

            table.append(i)
            if i*i != n:
                table.append(n//i)
        i+=1

    table.sort()

    return table
def resolve():
    (A,B)=(int(i) for i in input().split())
    t=math.gcd(A,B)
    if t==1:
        print(1)
        return
    kouyakusu=kouyaku(t)
    count=1

    kouyakusu.remove(1)

    while kouyakusu:

        x=kouyakusu[0]
        count+=1
        kouyakusu=[i for i in kouyakusu if i%x !=0]
    print(count)


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
import sys
from io import StringIO
import unittest
import math
class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """12 18"""
        output = """3"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """420 660"""
        output = """4"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """1 2019"""
        output = """1"""
        self.assertIO(input, output)
def kouyaku(n):
    i=1
    table=[]
    while i*i<=n:
        if n%i==0:

            table.append(i)
            if i*i != n:
                table.append(n//i)
        i+=1

    table.sort()

    return table
def resolve():
    (A,B)=tuple(map(lambda x: int(x),input().split()))
    t=math.gcd(A,B)
    if t==1:
        print(1)
        return
    kouyakusu=kouyaku(t)
    count=1

    kouyakusu.remove(1)

    while kouyakusu:

        x=kouyakusu[0]
        count+=1
        kouyakusu=[i for i in kouyakusu if i%x !=0]
    print(count)


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
import math


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


A, B = map(int, input().split())
d = math.gcd(A, B)
n = 1
s = set()
while n ** 2 <= d:
    if d % n == 0:
        if is_prime(n):
            s.add(n)
        if is_prime(d // n):
            s.add(d // n)
    n += 1
s.add(1)
print(len(s))

Submission status: Runtime Error

Solution code:
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 primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        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,b=map(int,input().split())
ad=set(make_divisors(a))
bd=set(make_divisors(b))
common=ad & bd
pr=set(primes(max(common)))
ans=common & pr 
print(len(ans)+1)

Submission status: Runtime Error

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

    # divisors.sort()
    return divisors

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        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,b=map(int,input().split())
ad=set(make_divisors(a))
bd=set(make_divisors(b))
common=ad & bd
pr=set(primes(max(common)))
ans=common & pr 
print(len(ans)+1)

Submission status: Runtime Error

Solution code:
import random

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

def is_prime(q,k=50):
    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 xrange(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 factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a

def divisorize(fct):
    b, e = fct.pop()  # base, exponent
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

x=[]
y=[]
z=[]

if a==1:
  x.append(1)
else:
  fct_a = factorize(a)
  for div in divisorize(fct_a):
    x.append(num(div))

if b==1:
  y.append(1)
else:
  fct_b = factorize(b)
  for div in divisorize(fct_b):
    y.append(num(div))

z=x+y
w=[m for m in set(z) if z.count(m) > 1]

c=0

for i in range(0,len(w)):
  if is_prime(w[i]):
    c+=1
print(c+1)

Submission status: Runtime Error

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

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 factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a

def divisorize(fct):
    b, e = fct.pop()  # base, exponent
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

x=[]
y=[]
z=[]

fct_a = factorize(a)
for div in divisorize(fct_a):
  x.append(num(div))

fct_b = factorize(b)
for div in divisorize(fct_b):
  y.append(num(div))

z=x+y
w=[m for m in set(z) if z.count(m) > 1]

c=0

for i in range(0,len(w)):
  if is_prime(w[i]):
    c+=1
print(c+1)

Submission status: Runtime Error

Solution code:
def solve(n):
    res = set()
    for i in range(2, n):
        while n % i == 0:
            res.add(i)
            n /= i
        if(n<=1) break
    res.add(1)
    return res
 
 
A, B = [int(_) for _ in input().split()]
print(len(solve(A) & solve(B)))

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


def LI(): return list(map(int, input().split()))


def LF(): return list(map(float, input().split()))


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(list, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


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


def gcdx(x, y):
    g = 0
    if (x % y != 0):
        g = x % y
        gcdx(y, g)
    return g


mod = 1000000007
inf = float('INF')


def A():
    a = II()
    b = a//2
    p = b/a
    if a % 2:
        print(1-p)
    else:
        print(p)

    return

# B


def B():
    N, K = map(int, input().split())
    h = LI()
    count = 0

    for i in h:
        if i >= K:
            count += 1
        else:
            continue
    print(count)
    return

# C


def C():
    N = II()
    A = LI()
    J = [0] * N
    for i, n in enumerate(A):
        J[n-1] = i+1
    for s in J:
        print(s, end=" ")

    return

# D


def D():
    A, B = map(int, input().split())
    g = gcd(A, B)
    #go = g
    #myset = set([1])
    sq = int(sqrt(g)) + 2
    ans = 1

    for i in range(2, sq):
        if g % i == 0:
            ans += 1
        while g % i == 0:
            g /= i

            # myset.add(i)
        if g == 1:
            break
        if i == sq - 1:
            # myset.add(go)
            ans += 1

    print(ans)

    return

# E


def E():
    N, M = LI()

    price = [-1] * N
    ans = [0]*N

    for i in range(M):
        a, b = LI()
        c = LI()
        for k in c:
            if price[k-1] > a/b or price[k-1] == -1:
                price[k-1] = a/b
                ans[i] = a

    if -1 in price:
        print(-1)
    else:
        print(sum(price))

    return

# F


def F():
    return


# Solve
if __name__ == '__main__':
    E()

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


def LI(): return list(map(int, input().split()))


def LF(): return list(map(float, input().split()))


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(list, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


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


def gcdx(x, y):
    g = 0
    if (x % y != 0):
        g = x % y
        gcdx(y, g)
    return g


mod = 1000000007
inf = float('INF')


def A():
    a = II()
    b = a//2
    p = b/a
    if a % 2:
        print(1-p)
    else:
        print(p)

    return

# B


def B():
    N, K = map(int, input().split())
    h = LI()
    count = 0

    for i in h:
        if i >= K:
            count += 1
        else:
            continue
    print(count)
    return

# C


def C():
    N = II()
    A = LI()
    J = [0] * N
    for i, n in enumerate(A):
        J[n-1] = i+1
    for s in J:
        print(s, end=" ")

    return

# D


def D():
    A, B = map(int, input().split())
    g = gcd(A, B)
    go = g
    myset = set([1])
    sq = int(sqrt(g)) + 2
    ans = 1

    for i in range(2, sq):
        if g % i == 0:
            ans++
        while g % i == 0:
            g /= i

            myset.add(i)
        if g == 1:
            break
        if i == sq - 1:
            myset.add(go)
            ans++

    print(ans)

    return

# E


def E():
    N, M = LI()

    price = [-1] * N
    ans = [0]*N

    for i in range(M):
        a, b = LI()
        c = LI()
        for k in c:
            if price[k-1] > a/b or price[k-1] == -1:
                price[k-1] = a/b
                ans[i] = a

    if -1 in price:
        print(-1)
    else:
        print(sum(price))

    return

# F


def F():
    return


# Solve
if __name__ == '__main__':
    D()

Submission status: Runtime Error

Solution code:
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
  
  def gcd(x,y):
    if y == 0:
       return x
    else:
       return gcd(y, x % y)

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

koyaku_insu = prime_factorize(koyaku)


print(len(koyaku_insu))

Submission status: Runtime Error

Solution code:
from math import gcd
a, b = map(int, input().split())
g = gcd(a, b)
ans = 1
for i in range(2, int(g ** 0.5) + 1):
  if g % i != 0:
    continue
  while g % i == 0:
    g //= i
  ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from fractions import gcd


def primes(N):
    p = [False, False] + [True] * (N - 1)
    for i in range(2, int(N ** 0.5) + 1):
        if p[i]:
            for j in range(i * 2, N + 1, i):
                p[j] = False
    return [i for i in range(N + 1) if p[i]]


def prime_factors(N):
    ret = []
    for p in primes(int(N ** 0.5) + 1):
        while N % p == 0:
            ret.append(p)
            N //= p
    if N > 1:
        ret.append(N)
    return ret


A, B = map(int, input().split())
g = gcd(A, B)
print(len(set(trial_division(g))) + 1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import math


def factorize(a):
    ret = set()
    i = 2
    while i * i < a:
        if a % i != 0:
            i += 1
        else:
            while a % i == 0:
                a //= i
                ret.add(i)
            i += 1
    if a != 1:
        ret.add(a)
    return ret

def main():
    A, B = map(int,input().split())
    ABgcd = math.gcd(A, B)
    ABfactor = factorize(ABgcd)
    Ans = len(ABfactor) + 1
    print(Ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
def make_divisors(a,b):
    n = min(a,b)
    m = max(a,b)
    divisors=[]
    for i in range(2,int(math.sqrt(n)) + 1):
        if n==1:
            break
        if n % i ==0:
            if m % i ==0:
                divisors.append(i)
            while n % i == 0 and n != 1:
                n //= i
    if n != 1 and m % n ==0:
        divisors.append(n)
    return divisors
lst = make_divisors(A, B) #この中から素数を数えたらいい
print (len(lst) + 1)

Submission status: Runtime Error

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

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

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())
if (A==1)or(B==1)or(coprime(A,B)):
  print(1)
else:
  A=make_divisors(A)
  B=make_divisors(B)
  C=list(set(A)&set(B))
  C=C.sort(reverse=True)
  count=0
  for i in range(len(C)):
    for j in range(i+1,len(C)):
      if (C[j]!=1)and(C[i]%C[j]==0):
        count=count+1
        break
  print(len(C)-count)

Submission status: Runtime Error

Solution code:
import sys
from fractions import gcd
def main(a, b):
    #a, b = [int(i) for i in sys.stdin.readline().split()]
    _gcd = gcd(a,b)
    #memo_ls = [0 for i in range(_gcd)]
    #memo_set = set()
    cnt = 0
    if _gcd == 1:
        print(1)
    else:
        div = 2
        while _gcd > 1:
            if _gcd % div == 0:
                while _gcd % div == 0:
                    _gcd /= div
                cnt += 1
            if div > 2:
              div += 2
            else:
	          div += 1
        #print(memo_set)
        print(cnt + 1)

if __name__ == "__main__":
    a, b = [int(i) for i in sys.stdin.readline().split()]
    main(a, b)

Submission status: Runtime Error

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

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

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())
if (A==1)or(B==1)or(coprime(A,B)):
  print(1)
else:
  A=make_divisors(A)
  B=make_divisors(B)
  C=list(set(A)&set(B))
  C.sort(reverse=True)
  count=0
  for i in range(len(C)):
    for j in range(i+1,len(C)):
      if (C[j]!=1)and(C[i]%C[j]==0):
        count=count+1
        break
print(len(C)-count)