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:
def gcd(n,m):#n,mは正の整数、最大公約数　許容は？
    if n==0:
        return m
    elif m==0:
        return n
    elif n>m:
        n=n%m
        return gcd(n,m)
    else:
        m=m%n
        return gcd(n,m)

def get_sieve_of_eratosthenes_new(n):
    import math
    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]

primelist=get_sieve_of_eratosthenes_new(10**6)

A,B=map(int,input().split())
x=gcd(A,B)
count=1

for i in range(0,len(primelist)):
    if x%primelist[i]==0:
        count+=1
if x!=1 and count=1:
    print(2)
else:
    print(count)

Submission status: Runtime Error

Solution code:
from sympy import sieve

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 i in sieve:
        sn += 1

sn += 1

ans = sn*(sn-1)//2
print(ans)

Submission status: Runtime Error

Solution code:
from sympy import sieve

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 i in sieve:
        sn += 1

sn += 1

ans = sn*(sn-1)/2
print(ans)

Submission status: Runtime Error

Solution code:
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
A,B = [int(i) for i in input().split()]
ans = 1
lia = factorization(A)
lib = factorization(B)
na = len(lia)
nb = len(lib)
a = [0] * na
b = [0] * nb
for i in range(na):
    a[i] = lia[i][0]
for i in range(nb):
    b[i] = lib[i][0]
M = max(a[-1],b[-1])
li = [0] * (M+10)
for i in range(na):
    li[a[i]] +=1
for i in range(nb):
    li[b[i]] +=1
for i in range(2,M+1):
    if li[i] == 2:
        ans+=1
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import numpy as np
from sys import stdin
from copy import deepcopy
from functools import reduce
from math 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)

Submission status: Runtime Error

Solution code:
a,b = map(int,input().split())
minv = min(a,b)
maxv = max(a,b)
kouyaku = []
ans = kouyaku.copy()
#公約数を求める
for i in range(1,(minv//2)+1):
    if a%i==0  and b%i==0:
        kouyaku.append(i)
print(*kouyaku)
#互いに素になる数字を探す
i = 0
j = 1
kouyaku.pop()
while len(kouyaku)==i:
    while len(kouyaku)==j:
        if j%i==0:
            kouyaku.remove(j)
print(*kouyaku)

Submission status: Runtime Error

Solution code:
import math
A,B = map(int,input().split())
gcd = math.gcd(A,B)
C = []
for i in range(1,gcd+1):
    if i*i>gcd:break
    if gcd%i==0:
        C.append(i)
        if i!=gcd//i:
            C.append(gcd//i)
def is_prime(n):
    if n==1:return True
    for i in range(2,int(math.sqrt(n))+1):
        if n%i==0:return False
    return True
cnt = 0
for c in C:
    if is_prime(c):cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
import math

def searchPrimeNum(N):
    maxV=int(math.sqrt(N))
    searchList=[i for i in range(2, N+1)]
    primeNum=[]
    while searchList[0]<=maxV:
        primeNum.append(searchList[0])
        tmp=searchList[0]
        searchList=[i for i in searchList if i%tmp!=0]
    primeNum.extend(searchList)
    return primeNum

A, B=map(int, input().split())
primeNum=searchPrimeNum(max(A, B))
ans=1
for p in primeNum:
    if A%p==0 and B%p==0:
        ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
def Euclid(a,b):
  r = a % b
  if r == 0:
    return b
  return Euclid(b,r)

a,b = map(int,input().split())
c = Euclid(a,b) if a > b else Euclid(b,a)

def soinsu(a):
  for i in range(2,a+1):
    if a % i == 0:
      return i
    
ans = []
while 1:
  s = soinsu(c)
  c = int(c/s)
  ans.append(s)
  if c==1:
    break
print(len(set(ans)) + 1)

Submission status: Runtime Error

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


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


a, b = map(int, input().split())
q = prime_factorize(gcd(a, b))
print(len(q) + 1)

Submission status: Runtime Error

Solution code:
from math import gcd
from collections import Counter

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

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

x = gcd(A,B)

print(len(set(prime_factorize(x)))+1)

Submission status: Runtime Error

Solution code:
from math import gcd
import sys
from collections import Counter

read = lambda: sys.stdin.readline().rstrip()

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

class Solution(object):
    def disjoint_set_of_common_divisors(self, A, B):
        return len(Counter(prime_factorize(gcd(A, B))).keys())+1

def main():
    
    A0, B0 = map(int, read().split())
    #A0 = tuple(map(int, read().split()))

    res = Solution().disjoint_set_of_common_divisors(A0, B0)

    print(res)
 
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from math import gcd
import sys
from collections import Counter

read = lambda: sys.stdin.readline().rstrip()

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 disjoint_set_of_common_divisors(A, B):

    return len(Counter(prime_factorize(gcd(A, B))).keys())+1

def main():
    
    A0, B0 = map(int, read().split())
    #A0 = tuple(map(int, read().split()))

    res = disjoint_set_of_common_divisors(A0, B0)

    print(res)
 
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from math import gcd
import sys
from collections import Counter

read = lambda: sys.stdin.readline().rstrip()

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 disjoint_set_of_common_divisors(A, B):

    return len(Counter(prime_factorize(gcd(A, B))).keys())+1

def main():
    
    A0, B0 = map(int, input().split())
    #A0 = tuple(map(int, read().split()))

    res = disjoint_set_of_common_divisors(A0, B0)

    print(res)
 
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from math import gcd
import sys
from collections import Counter

read = lambda: sys.stdin.readline().rstrip()

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)
    print(a)
    return a

def disjoint_set_of_common_divisors(A, B):

    return len(Counter(prime_factorize(gcd(A, B))).keys())+1

def main():
    
    A0, B0 = map(int, read().split())
    #A0 = tuple(map(int, read().split()))

    res = disjoint_set_of_common_divisors(A0, B0)

    print(res)
 
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import fractions
import math

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

def get_primes(n):
  primes = [2]
  for i in range(3, (n+1), 2):
    for p in primes:
      if i % p == 0:
        break
      if i < p ** 2:
        primes.append(i)
        break
    else:
      primes.append(i)
  return primes

def get_primes2(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]

for p in get_primes2(min(C, 10**6)):
  if p ** 2 > C:
    break
  if C % p == 0:
    pfac.append(p)
    while C % p == 0:
      C //= p
if C != 1:
  pfac.append(C)


print(len(pfac) + 1)

Submission status: Runtime Error

Solution code:
import fractions
A, B = map(int, input().split())
C = fractions.gcd(A, B)
pfac = []

def get_primes(n):
  primes = [2]
  for i in range(3, (n+1), 2):
    for p in primes:
      if i % p == 0:
        break
      if i < p ** 2:
        primes.append(i)
        break
    else:
      primes.append(i)
  return primes

def get_primes2(n):
    import math
    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]

for p in get_primes2(min(C, 10**6)):
  if p ** 2 > C:
    break
  if C % p == 0:
    pfac.append(p)
    while C % p == 0:
      C //= p
if C != 1:
  pfac.append(C)


print(len(pfac) + 1)

Submission status: Runtime Error

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

def f(a,b):
  for i in range(min(a,b),2,-1):
    if a%i==0 and b%i==0:
      max=i
      break
  re=[1,max]
  for i in range(2,max):
    if a%i==0 and b%i==0:re.append(i)
  return re

def g(n):
  for i in range(2,n):
    if n%i==0:return False
  else:return True

ans=[g(i) for i in f(a,b)]
print(ans.count(True))

Submission status: Runtime Error

Solution code:
import fractions
A, B = map(int, input().split())
C = fractions.gcd(A, B)
ans = 1
primes = [2]

if C % 2 == 0:
  ans += 1
  while C % 2 == 0:
    C //= 2

p = 3
while C > 1:
  for prime in primes:
    if p % prime == 0:
      continue
  primes.append(p)
  if C % P == 0:
    ans += 1
  while C % p == 0:
    C //= p
  p += 2
print(ans)

Submission status: Runtime Error

Solution code:
import fractions
import itertools
import math

# nの約数をすべて求める
def make_divisors(n):
    divisors = {}
    #for i in range(1, int(n**0.5)+1):
    for i in itertools.takewhile(lambda i: i**2<=n, itertools.count(1)):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)
    
    return divisors

# 素因数分解
# 素因数とその指数をペアにして配列で返す
def factorize(n):
    # 素因数の候補
    # i=2,...,floor(sqrt(n)) つまりi**2<=nになるまで
    remainder = n
    ret = {}
    for i in itertools.takewhile(lambda i: i**2<=n, itertools.count(2)):
        # 現在の余りをiで割れるだけ割る
        if remainder % i:
            continue
        else:
            # 割れるなら，割れる回数と余りを求める
            p = 0
            while remainder % i == 0:
                remainder //= i
                p += 1

            ret.add((i,p))

    # 2以上の余りが残っていれば，追加
    if remainder > 1: ret.add((remainder,1))

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

# 答えの集合は1or素数で構成されるとして良い (a*b,a>1,b>1となる要素があれば，aも公約数だから，a*bをaに置き換えても最適解になるから)
# つまり，A,Bをそれぞれ素因数分解し，共通の素因数の数を数えればよい
# これは，gcd(A,B)の素因数の数と同じ
gcd = fractions.gcd(A,B)
divs = factorize(gcd)
print(len(divs) + 1) # + 1は"1"の数

Submission status: Runtime Error

Solution code:
from math import sqrt
from fractions import gcd 
A, B = map(int,input().split())
Y = gcd(A, B)
ans = 1
if Y != 1:
    for i in range(2, min(Y+1,int(sqrt(Y))+2)):
        tmp = 0
        while True:
            if Y%i == 0:
                Y /= i
                tmp += 1
            else:
                if tmp > 0:
                    ans += 1
                break
    if ans == 1:
        ans += 1
        errtest[4]+a
print(ans)

Submission status: Runtime Error

Solution code:
def gcd(a, b): 
      
    # Everything divides 0  
    if (a == 0 or b == 0): 
            False
      
    # base case 
    if (a == b): 
        return a 
  
    # a is greater 
    if (a > b): 
        return gcd(a-b, b) 
          
    return gcd(a, b-a) 

m=list(input().split())
a=int(m[0])
b=int(m[1])
l=[]
count=0
if a>b:
    for i in range(2,a):
        if a%i==0 and b%i==0:
            l.append(i)
else:
    for i in range(2,b):
        if a%i==0 and b%i==0:
            l.append(i)
for i in range(len(l)):
    for j in range(i,len(l)):
        if gcd(i,j)==1:
            count+=1
print(count)

Submission status: Runtime Error

Solution code:
def gcd(a, b): 
      
    # Everything divides 0  
    if (a == 0 or b == 0): 
            False
      
    # base case 
    if (a == b): 
        return a 
  
    # a is greater 
    if (a > b): 
        return gcd(a-b, b) 
          
    return gcd(a, b-a) 

a=int(input())
b=int(input())
l=[]
count=0
if a>b:
    for i in range(2,a):
        if a%i==0 and b%i==0:
            l.append(i)
for i in range(len(l)):
    for j in range(i,len(l)):
        if gcd(i,j)==1:
            count+=1
print(count)

Submission status: Runtime Error

Solution code:
def primes(n):
    prime = [1]*(n+1)
    p=2
    while p*p <= n+1:
        if(prime[p]==True):
            i=p*p
            while i <= n+1:
                prime[i]=0
                i+=p
        p+=1
    return prime
    
def g(a,b):
    if(b==0):
        return a
    else:
        return g(b,a%b)
        
n,m = map(int,input().split())
if(n<=m):
    a=n
    b=m
else:
    a=m
    b=n
if a==1:
    print(a)
else:
    gcd = g(b,a)
    l =[]
    for i in range(1,gcd):
        if(n%i==0 and m%i==0):
            l.append(i)
    p = primes(gcd)
    count=0
    for i in range(len(l)):
        if(p[l[i]]==1):
            count+=1
    print(count)

Submission status: Runtime Error

Solution code:
def primes(n):
    i = 2
    prime = []
    while i**2<= n:
        if n % i:
            i += 1
        else:
            n =n//i
            prime.append(i)
    if n > 1:
        prime.append(n)
    return prime
a = int(input())
b = int(input())
pa=set(primes(a))
pb=set(primes(b))
inte=pa.intersection(pb)
print(len(inte)+1)

Submission status: Runtime Error

Solution code:
def primes(n):
    prime = [1]*(n+1)
    p=2
    while p*p <= n+1:
        if(prime[p]==True):
            i=p*p
            while i <= n+1:
                prime[i]=0
                i+=p
        p+=1
    return prime
    
def g(a,b):
    if(b==0):
        return a
    else:
        return g(b,a%b)
        
n = int(input())
m = int(input())
if(n<=m):
    a=n
    b=m
else:
    a=m
    b=n
if a==1:
    print(a)
else:
    gcd = g(b,a)
    l =[]
    for i in range(1,gcd):
        if(n%i==0 and m%i==0):
            l.append(i)
    p = primes(gcd)
    count=0
    for i in range(len(l)):
        if(p[l[i]]==1):
            count+=1
    print(count)

Submission status: Runtime Error

Solution code:
def primes(n):
    prime = [1]*(n+1)
    p=2
    while p*p <= n+1:
        if(prime[p]==True):
            i=p*p
            while i <= n+1:
                prime[i]=0
                i+=p
        p+=1
    return prime
    
def g(a,b):
    if(b==0):
        return a
    else:
        return g(b,a%b)
        
n = int(input())
m = int(input())
if(n<=m):
    a=n
    b=m
else:
    a=m
    b=n
if a==1:
    print(a)
else:
    gcd = g(b,a)
    l =[]
    for i in range(1,gcd):
        if(n%i==0 and m%i==0):
            l.append(i)
    p = primes(gcd)
    count=0
    for i in range(len(l)):
        if(p[l[i]]==1):
            count+=1
    print(count)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!

def factorization(n) : 
    arr = []
    temp = n
    for i in range(2, int(n**0.5//1)+1) : 
        if temp % i == 0 : 
            while temp % i == 0 : 
                temp = temp // i
            arr.append(i)
            
    if temp != 1 : 
        arr.append(i)
        
    # if arr == [] : 
    #     arr.append(n)
        
    return(len(arr))
 
A, B = map(int, input().split())
 
if A >= B : 
    L = A
    S = B
else : 
    L = B
    S = A
 
while True : 
    R = L % S
    if R == 0 : 
        GCD = S
        break
    L = S
    S = R
 
cnt = 1
divisor_list = []
 
for i in range(2, GCD+1) : 
    if GCD % i == 0 : 
        divisor_list.append(i)

n = factorization(GCD)

print(n+1)

Submission status: Runtime Error

Solution code:
import math
# 素数かどうか判定する関数 
def isPrime(n):
    if n == 0 : return False
    if n < 2 : return True
    else :
        for i in range(2,n):
            if n % i == 0:
                return False
        return True

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

# 公約数のリストを作成
nmax = math.gcd(a, b)
nlist = []
for i in range(1, nmax):
    if a%i == b%i == 0 :
        nlist.append(i)
nlist.append(nmax)

# 公約数の中から素数を数える
cnt = 0
for item in nlist:
    if isPrime(item): cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
import math
import itertools
from functools import reduce

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

a, b = map(int, input().split())
nmax = math.gcd(a, b)
nlist = []
for i in range(1, nmax):
    if a%i == b%i == 0 :
        nlist.append(i)
nlist.append(nmax)
l = len(nlist)
ans = 0
for i in range(2,l+1):
    comb = list(itertools.combinations(nlist,i))
    for combitem in comb :
        comb2 = list(itertools.combinations(combitem,2))
        cnt = 0
        for comb2item in comb2 :
            gcd = gcd_list(comb2item)
            if gcd != 1: 
                cnt = 0
                break
            if gcd == 1:
                cnt += 1
        ans = max(ans,cnt)
print(ans)

Submission status: Runtime Error

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

def factor(n):
    table = [0] * (n + 1)
    ans = [1]
    for i in range(2, n + 1):
        if table[i] == 0:
            if n % i == 0:
                ans.append(i)
            for j in range(i + i, n + 1, i):
                table[j] = 1
    return ans

ans = len(set(factor(a)) & set(factor(b)))
print(ans)

Submission status: Runtime Error

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

def factor(n):
    table = [0] * (n + 1)
    ans = []
    for i in range(2, n + 1):
        if table[i] == 0:
            if n % i == 0:
                ans.append(i)
            for j in range(i + i, n + 1, i):
                table[j] = 1
    return ans

ans = len(set(factor(a)) & set(factor(b))) + 1
print(ans)

Submission status: Runtime Error

Solution code:
from functools import reduce
from fractions import gcd
A, B = map(int,input().split())
def Eratosthenes(n):
    if n == 1:
      return [1]
    if n == 2:
      return [1, 2]
    dp = [False]*n
    dp[0] = dp[1] = True
    prime = []
    l = [1]
    for i in range(2, n):
        if dp[i]:
            continue
        prime.append(i)
        if n%i==0:
          l.append(i)
        for j in range(i*2, n, i):
            dp[j] = True
            i += 1
    return l
print(len(Eratosthenes(reduce(gcd,[A,B]))))

Submission status: Runtime Error

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

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)
  
def Eratosthenes(n):
    if n == 1:
      return [1]
    if n == 2:
      return [1, 2]
    dp = [False]*n
    dp[0] = dp[1] = True
    prime = []
    l = [1]
    for i in range(2, n):
        if dp[i]:
            continue
        prime.append(i)
        if n%i==0:
          l.append(i)
        for j in range(i*2, n, i):
            dp[j] = True
            i += 1
    return l
  
print(len(Eratosthenes(gcd(A,B))))

Submission status: Runtime Error

Solution code:
A, B = map(int,input().split())
def Eratosthenes(n):
    if n == 1:
      return [1]
    if n == 2:
      return [1, 2]
    dp = [False]*n
    dp[0] = dp[1] = True
    prime = []
    l = [1]
    for i in range(2, n):
        if dp[i]:
            continue
        prime.append(i)
        if n%i == 0:
          l.append(i)
        for j in range(i*2, n, i):
            dp[j] = True
            i += 1
    return l
print(len(set(Eratosthenes(A))&set(Eratosthenes(B))))

Submission status: Runtime Error

Solution code:
A, B = map(int,input().split())
def Eratosthenes(n):
    if n == 1:
      return [1]
    if n == 2:
      return [1, 2]
    dp = [False]*n
    dp[0] = dp[1] = True
    prime = []
    l = []
    for i in range(2, n):
        if dp[i]:
            continue
        prime.append(i)
        if n%i == 0:
          l.append(i)
        for j in range(i*2, n, i):
            dp[j] = True
            i += 1
    return l
print(len(set(Eratosthenes(A))&set(Eratosthenes(B)))+1)

Submission status: Runtime Error

Solution code:
def main():
    x,y = map(int,input().split())
    tmp = []
    i = 2
    ans = 0
    if x == y:
        ans += 1
    for i in range(2,min((-(-x**0.5//1))+1,(-(-y**0.5//1)+1))):


        if i > x or i > y:
            break
        if x % i ==0 and y % i == 0:
            tmp.append(i)
            while True:
                if x % i == 0:
                    x = x//i
                else:
                    break
            while True:
                if y % i == 0:
                    y = y//i
                else:
                    break
        i += 1
    ans += len(tmp) + 1

    print(ans)
    # print(tmp)
if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30

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

def hurui(n):
    is_prime = [0] * (n+10)
    for i in range(2, n+1):
        is_prime[i] = 1
    for i in range(2, n+1):
        if is_prime[i] == 1:
            j = i*2
            while j <= n:
                is_prime[j] = 0
                j += i
    return is_prime

def main():
    a, b = list(map(int, input().strip().split()))
    g = gcd(a, b)
    is_prime = hurui(10**6+10)
    i = 1
    c = 0
    while i**2 <= g:
        if g % i == 0:
            if is_prime[i] == 1:
                # print("i: ", i)
                c += 1
            if i != g // i and is_prime[g//i] == 1:
                # print("i: ", i)
                c += 1
        i += 1
    # print(g)
    print(c+1)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math
import random


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 is_prime3(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 range(k):
        a = random.randint(1, q - 1)
        t = d
        y = pow(a, t, q)
        # [0,s-1]の範囲すべてをチェック
        while t != q - 1 and y != 1 and y != q - 1:
            y = pow(y, 2, q)
            t <<= 1
        if y != q - 1 and t & 1 == 0:
            return False
    return True


a, b = map(int, input().split())
gcd = math.gcd(a, b)
divisors = make_divisors(gcd)

ans = 1
for divisor in divisors:
    if is_prime3(divisor):
        ans += 1

print(str(ans))