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:
import math
a, b = map(int, input().split())
n = math.gcd(a, b)


l = []
for i in range(n):
    if a % (i+2) == 0 and b % (i+2) == 0:
        l.append(i+2)

primes = [2]
for x in l:
    if all(x % prime !=0 for prime in primes):
        primes.append(x)

if  a % 2 == 0 or b % 2 == 0:
    ans = len(primes) +1
else:
    ans = len(primes)
print(ans)

Submission status: Runtime Error

Solution code:
a,b=map(int,input().split())
lista=[]
import fractions
gcd=fractions.gcd(a,b)

for i in range(2,gcd+1):
    if a% i == 0 and b % i == 0: 
        lista.append(i)
        
listb=[]
for i in range(len(lista)):   
    if pow(2, lista[i]-1, lista[i]) == 1:
            listb.append(lista[i])
#print(listb)   

if lista[0]==2:   
    print(len(listb)+2)

else:
    print(len(listb)+1)

Submission status: Runtime Error

Solution code:
import math
a,b=[int(i) for i in input().split()]
p=math.gcd(a,b)
def f(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 = temp//i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
if f(p)[0][0]==1:
    print(1)
else:
    print(len(f(p))+1)

Submission status: Runtime Error

Solution code:
A,B = map(int, input().split())
count = 1
import numpy as np
def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum
if A <= B:
    A_list = seachPrimeNum(A)
    for i in range(len(A_list)):
        if B % A_list[i] == 0 and A % A_list[i] == 0:
            count += 1

else:
    B_list = seachPrimeNum(B)
    for i in range(len(B_list)):
        if A % B_list[i] == 0 and B % B_list[i] == 0:
            count += 1
print(count)

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 sieve_of_eratosthenes(target):
    dest = int(math.sqrt(target))
    target_list = list(range(2, target + 1))
    prime_list = []

    while True:
        num_min = min(target_list)
        if num_min >= dest:
            prime_list.extend(target_list)
            break
        prime_list.append(num_min)

        i = 0

        while True:
            if i >= len(target_list):
                break
            elif target_list[i] % num_min == 0:
                target_list.pop(i)
            i += 1

    return prime_list


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())
    C = A
    if A > B:
        C = B
        sosu = sieve_of_eratosthenes(A)
    else:
        sosu = sieve_of_eratosthenes(B)
    L = [1]

    for i in sosu:
        if(A % i == 0 and B % i == 0):
            L.append(i)
    print(len(L))

    return

# E


def E():
    return

# F


def F():
    return


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

Submission status: Runtime Error

Solution code:
from functools import reduce
from fractions import gcd
import numpy as np

# List=[15,25,30]
# print(reduce(gcd,List))
a, b = map(int, input().split())


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


list_a = make_divisors(a)
list_b = make_divisors(b)

# print(list_a, list_b)
cd = set(list_a) & set(list_b)
# print(cd)

# c = 0
# for i in range(len(cd) - 1):
#     if gcd(cd[i], cd[i + 1]) == 1:
#         c += 1

# print(c + 1)


def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2, N + 1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum


# print(seachPrimeNum(100))
pnl = set(seachPrimeNum(max(cd)))
print(len(cd & pnl) + 1)

Submission status: Runtime Error

Solution code:
import math

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

G = math.gcd(A, B)
ans = 1

for i in range(G-1):
    if (G < i):
        break
    if(G % (i+2) == 0):
        ans += 1
        j = 1
        while(G % ((i+2)**j) == 0):
            G /= i+2
            j += 1

print(ans)

Submission status: Runtime Error

Solution code:
a,b=map(int,input().split())
lista=[]
import fractions
gcd=fractions.gcd(a,b)

for i in range(2,gcd+1):
    if a% i == 0 and b % i == 0: 
        lista.append(i)
        
listb=[]
for i in range(len(lista)):   
    if pow(2, lista[i]-1, lista[i]) == 1:
            listb.append(lista[i])
#print(listb)   

if lista[1]==2:   
print(len(listb)+2)

else:
    print(len(listb)+1)

Submission status: Runtime Error

Solution code:
import math

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

A,B = list(map(int,input().split()))
 
aaa = []
 
aaa = make_divisors(math.gcd(A,B))
        
count = 0
 
for i in range(len(aaa)):
    if isPrime(aaa[i]) == True:
        count += 1
        
print(count+1)

Submission status: Runtime Error

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

from math import gcd as bltin_gcd

def coprime2(a, b):
    return bltin_gcd(a, b) == 1
  
A,B = map(int,input().split())

kouyaku =  cf(A,B)

for x in list(itertools.combinations(kouyaku, 2)):
    if not coprime2(x[0],x[1]):
        if x[1] in kouyaku:
            kouyaku.remove(x[1])
            
print(len(kouyaku)+1)

Submission status: Runtime Error

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

r=a%b
maxdiv=0
while True:
  if b%r==0:
    break
  else:
    r1=b%r
    b=r
    r=r1

prime=[1]

for i in range(2,math.ceil(r/2)+1):
#  print (i)
  while True:
    if r%i==0:
      prime.append(i)
      r=r/i
    else:
      break

#print(prime)
print(len(set(prime)))

Submission status: Runtime Error

Solution code:
from math import gcd as bltin_gcd

def divisors(n, limit):
    # get factors and their counts
    factors = {}
    nn = n
    i = 2
    while i*i <= nn and i <= limit:
        while nn % i == 0:
            factors[i] = factors.get(i, 0) + 1
            nn //= i
        i += 1
    if nn > 1:
        factors[nn] = factors.get(nn, 0) + 1

    primes = list(factors.keys())

    # generates factors from primes[k:] subset
    def generate(k):
        if k == len(primes):
            yield 1
        else:
            rest = generate(k+1)
            prime = primes[k]
            for factor in rest:
                prime_to_i = 1
                # prime_to_i iterates prime**i values, i being all possible exponents
                for _ in range(factors[prime] + 1):
                    yield factor * prime_to_i
                    prime_to_i *= prime

    # in python3, `yield from generate(0)` would also work
    for factor in generate(0):
        yield factor

def common_elements(list1, list2):
    return list(set(list1).intersection(list2))

def is_prime(n):
  """
  Assumes that n is a positive natural number
  """
  # We know 1 is not a prime number
  if n == 1:
      return False

  i = 2
  # This will loop from 2 to int(sqrt(x))
  while i*i <= n:
      # Check if i divides x without leaving a remainder
      if n % i == 0:
          # This means that n has a factor in between 2 and sqrt(n)
          # So it is not a prime number
          return False
      i += 1
  # If we did not find any factor in the above loop,
  # then n is a prime number
  return True

a, b = [int(x) for x in input().split(' ')]

a, b = (a, b) if a <= b else (b, a)

la = list(divisors(a, 1e12 + 10))
lb = list(divisors(b, a))
la, lb = (la, lb) if len(la) <= len(lb) else (lb, la)

commonDivs = common_elements(la, lb)

primes = [x for x in commonDivs if is_prime(x)]

primes.append(1)

count = 0

for i in range(len(primes) - 1):
  x = primes[i]
  for j in range(i+1, len(primes)):
    y = primes[j]
    if bltin_gcd(x, y) == 1:
      count += 1

if primes == [1]:
  print(1)
else: 
  print(count)

Submission status: Runtime Error

Solution code:
a,b=map(int,input().split())
lista=[]
import fractions
gcd=fractions.gcd(a,b)

for i in range(2,gcd+1):
    if a% i == 0 and b % i == 0: 
        lista.append(i)
        
listb=[]
for i in range(len(lista)):   
    if pow(2, lista[i]-1, lista[i]) == 1:
            listb.append(lista[i])
print(listb)   

if lista[1]=2:   
print(len(listb)+2)

else:
    print(len(listb)+1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import os

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):
        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):
        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):
        d = n - 1
        while d & 1 == 0:
            d >>= 1

        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):
        p = Prime.seed_primes[seed % len(Prime.seed_primes)]
        return (p * x + seed) % n

    def find_factor(self, n, seed=1):
        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 = [int(i) for i in input().split(' ')]

#素因数分解
ap = prime.find_factors(a)
bp = prime.find_factors(b)

#print(ap, bp)

al = []
bl = []

for i in ap:
    al.append(i)
for i in bp:
    bl.append(i)

print(len(list(set(al) & set(bl))) + 1)

Submission status: Runtime Error

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

kouyaku =  cf(A,B)

for x in list(itertools.combinations(kouyaku, 2)):
    if not coprime2(x[0],x[1]):
        if x[1] in kouyaku:
            kouyaku.remove(x[1])
            
print(len(kouyaku)+1)

Submission status: Runtime Error

Solution code:
from sympy import isprime
from itertools import combinations
from math import gcd
def cd(a,b):
    count=0
    p=[]
    if a>b:
        n=b
    else:
        n=a
    for i in range(1,n+1):
        if a%i==0 and b%i==0:
            p.append(i)

    for i in p:
        if isprime(i):
            count += 1
        elif i==1:
            count+=1

    return count
p,q=input().split()
print(cd(int(p),int(q)))

Submission status: Runtime Error

Solution code:
a, b = map(int, input().split())
n = min(a, b) // 2
*t, = [True] * (n + 1)
#for i in range(len(t)):
#    if not t[i]:
#        continue
#    if a % t[i] == 0 and b % t[i] == 0:
#        for j in range(i+1, len(t)):
#            if t[j] == -1:
#                continue
#            if t[j] % t[i] == 0:
#                print(t[j], t[i])
#                t[j] = -1
#    else:
#        t[i] = -1
print(1)

Submission status: Runtime Error

Solution code:
def gcd(a,b):
  if a==b:
    return a
  elif b>a:
    return gcd(b-a,a)
  else:
    return gcd(a-b,b)

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,B=[int(x) for x in input().split()]

import collections
c = collections.Counter(prime_factorize(gcd(A,B)))
print(len(list(c.keys()))+1)

Submission status: Runtime Error

Solution code:
from numpy import gcd

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

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

count = 0
if len(CD) == 1:
    count += 1
else:
    for i in range(len(CD)):
        for k in range(i+1,len(CD)):
            if ((i != k) and gcd(CD[i],CD[k]) == 1):
                count += 1

print(count)

Submission status: Runtime Error

Solution code:
a,b=map(int,input().split())
n=min(a,b)
if n==1:
  print(1)
  exit
if n >= 2:
     prime = [2]
     for i in range(3, n//2 + 1):
         for p in prime:
             if i % p == 0:
                 break
         else:
             prime.append(i)
            
ctr=1
for i in range(len(prime)):
  if n%prime[i]==0:
    ctr+=1
print(ctr*(ctr-1)//2)

Submission status: Runtime Error

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

import math
# import time

G = math.gcd(A, B)
ans = 1
# print("G:", G)



for i in range(G-1):
    if (G < i):
        break
    # print("G % (i+1) == 0:", G % (i+1) == 0)
    if(G % (i+2) == 0):
        ans += 1
        j = 1
        while(G % ((i+2)**j) == 0):
            G /= i+2
            j += 1
            # print("i:", i + 2, "j:", j)
            # time.sleep(1)

print(ans)

Submission status: Runtime Error

Solution code:
import math
import collections

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

gcd = math.gcd(a, b)


def prime_factorize(n):
    a = list()
    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


c = collections.Counter(prime_factorize(gcd))
print(len(c.keys()) + 1)

Submission status: Runtime Error

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

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

def cf(x1, x2):
    array = [1]
    for i in primes(gcd(x1, x2)):
        if x1 % i == 0 and x2 % i == 0:
            array.append(i)
    return array 

def cf_count(x1, x2):
    count = 1
    n = gcd(x1, x2)
    for i in primes(n):
        if x1 % i == 0 and x2 % i == 0:
            count += 1
    return count

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]]

print(cf_count(A, B))

Submission status: Runtime Error

Solution code:
def check2(x,y,p,t):
    for i in range(p+1,t+1,1):
        if x % i == 0 and y % i == 0 :
            return i
        if i == t :
          return 1 
A,B = map(int,input().split())
ans = 1
p = 1
t = min(A,B)
while True :
    p = check2(A,B,p,t)
    if p == 1 :
        break
    while True :
        if A % p == 0 and B % p == 0 :
            A = (A//p)
            B = (B//p)
        else :
            break
    ans += 1
print(ans)

Submission status: Runtime Error

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

l = []
for i in range(n):
    if a % (i+2) == 0 and b % (i+2) == 0:
        l.append(i+2)

primes = [2]
for x in l:
    if all(x % prime !=0 for prime in primes):
        primes.append(x)

if  a % 2 == 0 or b % 2 == 0:
    ans = len(primes) +1
else:
    ans = len(primes)
print(ans)

Submission status: Runtime Error

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

cf.sort()
for i in cf[:]:
	for j in cf[:]:
		if i >= j:
			continue
		if i%j == 0:
			cf.remove(i)
		elif j%i == 0:
			cf.remove(j)
print(sum(int(i) for i in kekka))

Submission status: Runtime Error

Solution code:
a, b = map(int, input().split())
g = []
from math import gcd
g.append(gcd(a,b))
g.append(1)
if not a%2 and not b%2:
    g.append(2)
for i in range(3,g[0],2):
    if not a%i and not b%i:
        c = True
        for k in range(2, len(g)):
            if gcd(g[k],i)!=1:
                c = False
                break
        if c:
            g.append(i)
c = True
for i in range(1, len(g)):
    if gcd(g[0],g[i])!=1:
        c = False
        break
if c and g[0] != 1:
    print(len(g))
else:
    print(len(g)-1)

Submission status: Runtime Error

Solution code:
from math import gcd as bltin_gcd
import itertools

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

A, B = map(int, input().split())
koyakusuu_list = []
for a in range(1, A+1):
    if a == 1:
        koyakusuu_list.append(1)
    elif B % a == 0 and A % a == 0:
        flag = 0
        for kouyakusuu in koyakusuu_list:
            if coprime2(a, kouyakusuu):
                continue
            else:
                flag += 1
        if flag == 0:
            koyakusuu_list.append(a)

print(len(set(koyakusuu_list)))

Submission status: Runtime Error

Solution code:
if a == 1 or b == 1:
  print(1)
def prime(n):
  pf=[1]
  for i in range(2,int(n**0.5)+1):
    while n%i==0:
      pf.append(i)
      n//=i
  list(set(pf))
  return pf
a, b = map(int, input().split())
if a == 1 or b == 1:
  print(1)
else:
  print(len(set(prime(a)+prime(b))))

Submission status: Runtime Error

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

#A , B = 12, 18
#d = []
#print(A, B)
import numpy as np
if A > B:
    A_arr = np.array([A] * B)
    B_arr = np.array([B] * B)
    arr = np.arange(1, B + 1)
else:
    A_arr = np.array([A] * A)
    B_arr = np.array([B] * A)
    arr = np.arange(1, A + 1)

gcds = np.nonzero((A_arr % arr == 0) * (B_arr % arr == 0))[0] + 1

ret = set()


import fractions
for i in gcds:
    for j in gcds:
        if fractions.gcd(i, j) == 1:
            ret.add(j)

print(len(ret))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	A,B = inputMap()
	m = min(A,B)
	an = gcd(A,B)
	lin = []

	ans = 0
	for i in range(1,an+1):
		if is_prime(i) == True:
			lin.append(i)

	lin = lin[::-1]
	con = 0
	for i,val in enumerate(lin):
		if m < val * lin[i+1]:
			con+=1
		else:
			break

	print(len(lin)-con)


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

def gcd(a, b):
	if a > b:
		a, b = b, a

	while a > 0:
		a, b = b % a, a
	return b

if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
import math
import collections

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

gcd = math.gcd(a, b)


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


c = collections.Counter(prime_factorize(gcd))
print(len(c.keys()) + 1 )

Submission status: Runtime Error

Solution code:
for i in range(1, int(max([A, B])**0.5) + 1):
    is_p_num = True
    if A % i == 0 and B % i == 0:
        for p in p_nums:
            if p == 1:
                continue
            if i % p == 0:
                is_p_num = False
                break
        if is_p_num:
            p_nums.append(i)

Submission status: Runtime Error

Solution code:
N = list(map(int, input().split()))
if (N[0] == 1 and N[1] >= 1) or N[1] == 1:
  print(1)
elif N[0] > 1 or N[1] > 1:
  list =[]
  for i in range(2,min(N)):
    if N[0] % i == 0 and N[1]% i == 0:
      if len(list) == 0:
        list.append(i)
      else:
        f = True
        for j in list:
          if i % j == 0:
            f = False
            break
          if f :
            list.append(i)

print(len(list)+1)

Submission status: Runtime Error

Solution code:
import math

def isdevided(x):
    devisors = [1]
    for i in range(2, x):
        if (x % i) == 0:
            devisors.append(i)
            while (x % i == 0):
                x /= i
                x = int(x)

        else:
            continue
                
    
    return devisors

get = input().split()
A = int(get[0])
B = int(get[1])

C = math.gcd(A,B)

ls = isdevided(C)

print(len(ls))

Submission status: Runtime Error

Solution code:
  a, b = [int(x) for x in input().split()]
  if a > b:
    a, b = b, a

  cnt = 1 # 公約数１の分

  if a != 1:
    f = a
    if b % f == 0:
      cnt += 1

    f = 2
    if a % f == 0:
      if b % f == 0:
        cnt += 1

    f = 3
    while f <= a:
      if a % f == 0:
        if b % f == 0:
          cnt += 1
        a //= f
      f += 2

  print(cnt)

Submission status: Runtime Error

Solution code:
a,b = map(int,input().split())
c = []
for i in range(2,min(a,b)+1):
    if a % i == 0 and b % i == 0:
       c.append(i)
for k in range(len(c)):
    for j in range(len(c)):
        if (c[k])%(c[j])==0:
           if c[k] != c[j]:
              c.pop(k)

c.append(1)
print(c)

Submission status: Runtime Error

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

l = []
for i in range(n):
    if a % (i+2) == 0 and b %1 (i+2) == 0:
        l.append(i+2)
    
primes = [2]
for x in l:
    if all(x % prime !=0 for prime in primes):
        primes.append(x)

if  a % 2 == 0 or b % 2 == 0:
    ans = len(primes) +1
else:
    ans = len(primes)
print(ans)

Submission status: Runtime Error

Solution code:
a,b=map(int,input().split())
n=min(a,b)
            
if n >= 2:
     prime = [2]
     for i in range(3, n//2 + 1):
         for p in prime:
             if i % p == 0:
                 break
         else:
             prime.append(i)
            
ctr=1
for i in range(len(prime)):
  if n%prime[i]==0:
    ctr+=1
print(ctr*(ctr-1)//2)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(int(1e6))

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

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]]

min_n = min(A, B)
if min_n < 2:
    primes = list()
else:
    primes_n = primes(min_n)

prime_factors_count = 0
for f in primes_n:
    if (A % f) or (B % f):
        pass
    else:
        prime_factors_count += 1

print(prime_factors_count + 1)

Submission status: Runtime Error

Solution code:
import numpy as np
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

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

    if temp!=1:
        arr.append(temp)

    if arr==[]:
        arr.append(n)

    return arr
#print(factorization(A),factorization(N))

a=len(list(set(factorization(A))&set(factorization(N))))

a = cmb(a+1, 2)
print(a)

Submission status: Runtime Error

Solution code:
a,b=map(int,input().split())
a,b=min(a,b),max(a,b)
ans=1
is_prime = [True]*(a+1)
is_prime[0]=False
is_prime[1]=False
for i in range(2,a+1):
  if is_prime[i]:
    if a%i==0 and b%i==0:
      ans+=1
    while a%i==0:
      a//=i
    if a==1:
      break
    for j in range(i*2,a+1,i):
      is_prime[j] = False
print(ans)

Submission status: Runtime Error

Solution code:
import fractions
a,b = map(int, input().split())
g = fractions.gcd(a,b)
l = [0]*(g-1)

for i in range(2, g+1):
  if g%i == 0 and min(a,b)%i == 0:
    for j in range(2, i):
      if i%j == 0:
        break
    else:
      l[i] = 1

print(l.count(1)+1)

Submission status: Runtime Error

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

def yakusu(n):
    num = []
    
    for i in range(1, n+1):
        if n % i == 0:
            num.append(i)
    return num

def kouyaku(a,b):
    a_yaku = set(yakusu(a))
    b_yaku = set(yakusu(b))
    return list(a_yaku & b_yaku)

import math

count = 0
kou_n = kouyaku(A,B)
list_01 = [-1 for i in range(len(kou_n))]

for i in range(len(kou_n)):
    if list_01[i] == -1:
        count += 1
        list_01[i] = 1 #1:探索済み
        for j in range(i, len(kou_n)):
            if math.gcd(kou_n[i], kou_n[j]) != 1:
                list_01[j] = 1
print(count)

Submission status: Runtime Error

Solution code:
import math
import heapq
A,B = list(map(int,input().split()))
GCD = math.gcd(A,B)
CD = []
for i in range(1,int(GCD**(0.5))+1):
    if GCD % i == 0:
        CD.append(i)
        if not i == GCD//i:
            CD.append(GCD//i)
CD.sort()
ans = 1
tmp_idx = 0
CD.pop(0)
CD_old = CD[:]
while (len(CD_old)>0):
    tmp = CD_old.pop(0)
    CD_new = []
    for i in range(len(CD_old)):
        if not CD_old[i] % tmp == 0:
            CD_new.append(CD_old[i])
    ans += 1
    CD_old = CD_new
print(ans)

Submission status: Runtime Error

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

minAB = min(A,B);

hurui = [True] * (minAB+1)
"""
upper = int(math.sqrt(minAB+1))
ans = 1

for i in range(2, upper+1):

    if not(hurui[i]):
        continue
    
    for j in range(2*i, minAB+1, i):
        hurui[j] = False

    if A % i == 0  and B % i == 0:
        ans += 1
"""
ans = 1
print(ans)

Submission status: Runtime Error

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


def era_prime(N):
    temp = [True]*(N+1)
    temp[0] = temp[1] = False
    for i in range(2, ceil(sqrt(N+1))):
        if temp[i]:
            temp[i+i::i] = [False]*(len(temp[i+i::i]))
    primes = [n for n in range(N+1) if temp[n]]
    return primes


prime_list = era_prime(fractions.gcd(A, B))
ans = 1


for i in range(2, fractions.gcd(A, B)+1):
    if A % i == 0 and B % i == 0:
        if i in prime_list:
            ans += 1

print(ans)