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

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


# 最大公約数
def gcd(a, b):
  while b != 0:
    a, b = b, a % b

  return a


# 素因数分解
def primes(v):
  ps = []

  for i in range(2, int(v ** 0.5) + 1):
    if i ** 2 > v:
      break

    if v % i == 0:
      ps.append([i, 1])
      v //= i

      while v % i == 0:
        ps[-1][1] += 1
        v //= i

  if v > 1:
    ps.append([v, 1])

  return ps


def main():
  a, b = map(int, input().split())
  g = gcd(a, b)
  print(len(primes(g)) + 1)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
# 素因数分解してくれる関数
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

A, B = map(int, input().split())
A_soinsu = set(factorize(A))
B_soinsu = set(factorize(B))

ans = A_soinsu & B_soinsu

print(len(ans) + 1)

Submission status: Accepted

Solution code:
from collections import Counter
from fractions import gcd
a, b = map(int, input().split())
n = int(max(a, b)**(1/2)) + 1

g = gcd(a, b)
cnt = Counter()
m = 2
while m*m<= g:
    while g % m == 0:
        g //= m
        cnt[m] += 1
    m += 1
if g > 1:
    cnt[g] += 1

print(len(cnt) + 1)

Submission status: Accepted

Solution code:
# 素因数分解してくれる関数
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

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

A_soinsu = set(factorize(A))
B_soinsu = set(factorize(B))

ans = A_soinsu & B_soinsu

print(len(ans) + 1)

Submission status: Accepted

Solution code:
import fractions
a, b = map(int, input().split())
x = fractions.gcd(a, b)
t = x

i = 2
ans = 1;
while i * i <= t:
  if x % i == 0:
    while x % i == 0:
      x /= i
    ans += 1
  i += 1
if x != 1:
  ans += 1

print(ans)

Submission status: Accepted

Solution code:
def factoring(n):
    if n == 0:
        return {}
    if n == 1:
        return {}
    nOrigin = n
    n = n**0.5
    numlist = [0 for i in range(int(n) + 1)]
    numlist[0] = -1
    numlist[1] = -1

    #√√n以下の数について篩をかけていく
    t = 2
    while t < (n**0.5):
        if numlist[t] == 0:
            numlist[t] = t
            k = 2
            while t * k <= n:
                numlist[t * k] = -1
                k += 1
        t += 1

    #√√nより大きい数で、篩にかからなかった数は素数。
    while t <= n:
        if numlist[t] == 0:
            numlist[t] = t
        t += 1

    #√n以下の数で割っていく。
    result = {}
    for i in numlist:
        if i == -1:
            continue
        j = 0
        while nOrigin % i == 0:
            j += 1
            nOrigin = nOrigin / i
        if j == 0:
            continue
        else:
            result[i] = j

    if int(nOrigin) != 1:
        result[int(nOrigin)] = 1
    return result

def GCD(a, b):
    M = max(a, b)
    m = min(a, b)
    if m == 0:
        return M
    else:
        return GCD(m, M % m)


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

fact=factoring(GCD(A, B))
print(len(fact)+1)

Submission status: Accepted

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

import collections
import fractions

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

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

Submission status: Accepted

Solution code:
A, B = map(int, 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

A_list = prime_factorize(A)
B_list = prime_factorize(B)

A_and_B = set(A_list) & set(B_list)
print(len(A_and_B)+1)

Submission status: Accepted

Solution code:
import math
def func(num):
    lists = []
    root = math.floor(math.sqrt(num))
    
    while(num%2==0):
        num = num // 2
        if(num%2!=0):
            lists.append(2)
            
    for j in range(3,root+2,2):
        while(num%j==0):
            num = num //j
            if(num%j!=0):
                lists.append(j)
        if(num==1):
            break

    if(num>1):
        lists.append(num)
    return lists

if __name__ == "__main__":
    a,b = (int(i) for i in input().split())
    
    lists1 = func(a)
    lists2 = func(b)
    
    ans = set(lists1) & set(lists2)
    print(len(ans)+1)

Submission status: Accepted

Solution code:
import math
def func(num):
    lists = []
    root = math.floor(math.sqrt(num))
    
    while(num%2==0):
        num = num // 2
        if(num%2!=0):
            lists.append(2)
            
    for j in range(3,root+2,2):
        while(num%j==0):
            num = num //j
            if(num%j!=0):
                lists.append(j)
        if(num==1):
            break

    if(num>2):
        lists.append(num)
    return lists

if __name__ == "__main__":
    a,b = (int(i) for i in input().split())
    
    lists1 = func(a)
    lists2 = func(b)
    
    ans = set(lists1) & set(lists2)
    print(len(ans)+1)

Submission status: Accepted

Solution code:
#142d
import collections

A,B = map(int, input().split()) #K<=100

#正整数 A,Bが与えられます。
#A と B の正の公約数の中からいくつかを選びます。
#ただし、選んだ整数の中のどの異なる 2つの整数についても互いに素でなければなりません。
#最大でいくつ選べるでしょうか。
#整数 x,y が互いに素であるとは、x,y の正の公約数が 1 のみであることをいいます。

#https://note.nkmk.me/python-prime-factorization/
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

pfa = collections.Counter(prime_factorize(A))
#print(set(pfa.keys()))
pfb = collections.Counter(prime_factorize(B))
#print(set(pfb.keys()))
print(1+len(set(pfa) & set(pfb)))

Submission status: Accepted

Solution code:
from fractions import gcd

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

ans = 1

for d in xrange(2, g + 1):
    if (d * d) > g: break

    if (g % d == 0):
        ans += 1
        while (g % d == 0):
            g /= d

if (g > 1): ans += 1

print ans

Submission status: Accepted

Solution code:

import math


def primeFactorisation(x):
    res = set([1])
    while x % 2 == 0:
        res.add(2)
        x = x//2
    for i in range(3, int(math.sqrt(x)) + 1, 2):
        while (x % i == 0):
            res.add(i)
            x = x // i

    if (x > 2):
        res.add(x)
    return res


if __name__ == "__main__":
    prevs = []
    a, b = map(int, input().split())
    fa = primeFactorisation(a)
    fb = primeFactorisation(b)
    fres = fa.intersection(fb)
    print(len(fres))

Submission status: Accepted

Solution code:
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a


import random
def is_prime(q, k=50):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q % 2 == 0:
        return False

    d = (q - 1) >> 1
    while d & 1 == 0:
        d >>= 1
    for i in range(k):
        a = random.randint(1, q - 1)
        t = d
        y = pow(a, t, q)
        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 prime_num(target):
    ra = 2
    prime = 0
    while target>1:
        if target%ra == 0:
            prime += 1
            while target%ra==0:
                target = target//ra
            if is_prime(target):
                prime += 1
                break
        if ra == 2:
            ra += 1
        else:
            ra += 2
    return prime   
        
a, b = map(int, input().split())
gcd = xgcd(a, b)
if gcd == 1:
    print(1)
elif is_prime(gcd):
    print(2)
else:
    ans = prime_num(gcd)    
    print(ans+1)

Submission status: Accepted

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

def yaku(n):
  l=[]
  m=n
  for i in range(1,int((n)**(1/2))+1):
    if m%i==0:
      l.append(i)
      if m//i!=i:
        l.append(m//i)
  return l

def gcd(n,m):
  a=max(n,m)
  b=min(n,m)
  while b!=0:
    a,b=b,a%b
  return a

def prime(n):
  for i in range(2,int((n)**(1/2))+1):
    if n%i==0:
      return False
  return True

num=gcd(a,b)

l0=yaku(num)

num1=max(l0)

cd=yaku(num1)

pr=[]

for i in cd:
  if i==1:
    pr.append(i)
  else:
    if prime(i):
      pr.append(i)

print(len(pr))

Submission status: Accepted

Solution code:
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

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

af = set(factorize(a))
bf = set(factorize(b))

count = 0
print(len(af&bf)+1)

Submission status: Accepted

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

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

#print(gcd(660, 420))
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

#print(prime_factorize(9))

if __name__ == "__main__":
  gcd = gcd(A, B)
  c = collections.Counter(prime_factorize(gcd))
  ans = len(c.keys()) + 1
  print(ans)

Submission status: Accepted

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

A, B = map(int, input().split())
prime1 = get_prime(A)
prime2 = get_prime(B)
ans_prime = set(prime1) & set(prime2)
print(len(ans_prime) + 1)

Submission status: Accepted

Solution code:
A,B = map(int, input().split())
while B != 0: A, B = B, A % B 

ans = 0
if A == 1:
    print(1)
    exit()

c = 2
if A%c == 0:
    ans += 1
while A%c == 0:
    A //= c

c = 3
while c**2 <= A:
    if A == 1:
        break
    if A%c == 0:
        ans += 1
    while A%c == 0:
        A //= c
    c += 2

if A != 1: 
    ans += 1

print(ans+1)

Submission status: Accepted

Solution code:
import sys
import itertools
input = sys.stdin.readline

#複数入力
a,b=(int(x) for x in input().split())

def factorize(n):
    b = 2
    #本当は[]
    fct = [1]
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

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

Submission status: Accepted

Solution code:
import sys
import itertools
input = sys.stdin.readline

#複数入力
a,b=(int(x) for x in input().split())

def factorize(n):
    b = 2
    #本当は[]
    fct = [1]
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

#len(list(itertools.combinations(set(factorize(a))&set(factorize(b)),2)))
if len(set(factorize(a))&set(factorize(b)))==1:
    print(1)
else:
    print(len((set(factorize(a))&set(factorize(b)))))

Submission status: Accepted

Solution code:
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

X,Y= [int(i) for i in input().split()]
x=min(X,Y)
y=max(X,Y)

a=y%x
if a !=0:
        while a > 1:
                y=x
                x=a
                a=y%x
                
print(len(set(factorize(x))) + 1 if a==0 else 1)

Submission status: Accepted

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

a,b=[int(i) for i in input().split()]
val = gcd(a,b)

ct=1

for i in range(2,int(val**0.5)+2):
    if(val%i==0):
        ct+=1
        while(val%i==0):
            val//=i
if(val!=1):
    ct+=1
print(ct)

Submission status: Accepted

Solution code:
import fractions
a,b = map(int,input().split())
"""素因数分解"""
def factrize(n):
	b = 2
	fct = []
	while b*b <= n:
		while n % b == 0:
			n //= b
			#もし素因数を重複させたくないならここを加えてfct.append(b)を消す
			
			if not b in fct:
				fct.append(b)
			
			
		b = b+1
	if n > 1:
		fct.append(n)
	return fct #リストが帰る

gc = fractions.gcd(a,b)

ans = factrize(gc)
print(len(ans)+1)

Submission status: Accepted

Solution code:
from sys import stdin


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 = map(int, stdin.readline().rstrip().split())

Aprime = prime_factorize(A)
Bprime = prime_factorize(B)

Aset = set(Aprime)
Bset = set(Bprime)

cup = Aset & Bset

#print(Aset)
#print(Bset)

#print(cup)

print(1 + len(cup))

Submission status: Accepted

Solution code:
def yakusu(x):
    ans=[1]
    check=2
    while(x!=1 and check <= int(x**0.5)+2):
        if(x%check==0):
            ans.append(check)
            while(x%check==0):
                x=x//check
        check+=1
    if x != 1:
        ans.append(x)
    return ans
def main():
    a,b = map(int,input().split())	
    ans=0
    y1=yakusu(a)
    for i in y1:
        if b%i==0:
            ans+=1
    print(ans)

main()

Submission status: Accepted

Solution code:
def yakusu(x):
    ans=[1]
    check=2
    while(x!=1 and check <= int(x**0.5)+2):
        if(x%check==0):
            ans.append(check)
            while(x%check==0):
                x=x//check
        check+=1
    if x != 1:
      ans.append(x)
    return ans
def main():
    a,b = map(int,input().split())	
    ans=0
    y1=yakusu(a)
    for i in y1:
        if b%i==0:
            ans+=1
    print(ans)
 
main()

Submission status: Accepted

Solution code:
def yakusu(x):
    ans=[1]
    check=2
    while(x!=1 and check <= int(x**0.5)+2):
        if(x%check==0):
            ans.append(check)
            while(x%check==0):
                x=x//check
        check+=1
    if x != 1:
      ans.append(x)
    return ans
def main():
    a,b = map(int,input().split())	
    ans=0
    y1=yakusu(a)
    for i in y1:
        if b%i==0:
            ans+=1
    print(ans)

main()

Submission status: Accepted

Solution code:
import fractions
import numpy as np

A, B = map(int, open(0).read().split())
G = fractions.gcd(A, B)
upper_limit = int(np.sqrt(G))
ans = 1
for i in range(upper_limit):
    if G % (i + 2) == 0:
        ans += 1
        #print(i + 2)
        while G % (i + 2) == 0:
            G /= (i + 2)
            #print(G)
if G != 1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import fractions
from math import sqrt

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

G = fractions.gcd(A, B)
N = int(sqrt(max(A,B)))+1
g = G
ans = 1

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

print(ans)

Submission status: Accepted

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

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

n = gcd(a,b)
m = n
ans = 1

if m%2==0:
    ans += 1
    while m%2==0:
        m //= 2
f = 3

while f*f <= n:
    if m%f==0:
        ans += 1
        while m%f==0:
            m //= f
    f+=2

if m!=1:
    ans += 1

print(ans)

Submission status: Accepted

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

cd = []

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


for i in range(1,int(A**0.5)+1):
    if A % i == 0:
        if B % i == 0:
            cd.append(i)
        if B % (A / i) == 0:
            cd.append(int(A / i))

ans = 1
for i in cd:
    if is_prime(i):
        ans += 1

print(ans)

Submission status: Accepted

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

import math

def trial_division(target):
    dest = int(math.sqrt(target)) + 1

    for i in range(2, dest):
        if target % i == 0:
            return 0
    return 1

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

a_set = set(make_divisors(a))
b_set = set(make_divisors(b))

ab_set = a_set & b_set

c = 0
for ab in list(ab_set):
    c += trial_division(ab)

print(c)

Submission status: Accepted

Solution code:
A,B=list(map(int,input().split(" ")))
from collections import defaultdict
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=prime_factorize(A)
b=prime_factorize(B)
count1=defaultdict(lambda:0)
count2=defaultdict(lambda:0)
for i in range(len(a)):
    count1[a[i]]+=1
for i in range(len(b)):
    count2[b[i]]+=1

c=count1.keys()
d=count2.keys()
num=0
for i in c:
    if i in d:
        num+=1
print(num+1)

Submission status: Accepted

Solution code:
def prime_bunkai(num):
    temp = num
    ans_list = []
    for i in range(2, int(-(-temp**0.5)//1)+1):
        if num % i == 0:
            ans_list.append(i)
            while num % i == 0:
                num //= i

    if num != 1:
        ans_list.append(num)

    if ans_list == []:
        ans_list.append(temp)
    ans_list.append(1)
    return ans_list

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

ans = set(prime_bunkai(A)) & set(prime_bunkai(B))
print(len(ans))

Submission status: Accepted

Solution code:
from math import sqrt, ceil

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

def gcd(a, b):
  x, y = (a, b) if a > b else (b, a)
  while y > 0:
    x, y = y, x % y
  return x

d = gcd(a, b)
ans = 1
for i in range(2, ceil(sqrt(d))+1):
  if d % i == 0:
    ans += 1
    while(d % i == 0):
      d = d / i
if d != 1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
 

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([1, 1])
 
    return arr


a, b = map(int, input().split())
 
x = np.array(factorization(a))
y = np.array(factorization(b))
 
num = set(x[:, 0]) & set(y[:, 0])
 
print(len(num))

Submission status: Accepted

Solution code:
# def max_comn_div(n, m):
#     """give max common divisor"""
#     if n > m:
#         a, b = n, m
#     else:
#         a, b = m, n
#     while b != 0:
#         a, b = b, a % b
#     return a


# a = int(input())
# b = int(input())
# print(max_comn_div(a, b))

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


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


def div(n):
    """give divisors"""
    divisors = [1]
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            divisors.append(i)
            n /= i
    if n != 1:
        divisors.append(int(n))
    return set(divisors)


a, b = map(int, input().split())
# print(euc(a, b))
c = div(euc(a, b))
# print(c)
print(len(c))

Submission status: Accepted

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, int(sqrt_a) ):  
  if (a % (i) == 0):
    list_a.append( i )
    while( a % (i) == 0 ):
      a = a//(i)
if a > 1:
  list_a.append(a)
      
for i in range(2, int(sqrt_b) ):  
  if (b % (i) == 0):
    list_b.append( i )
    while( b % (i ) == 0 ):
      b = b//(i)
if b > 1:
  list_b.append(b)

#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: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time
sys.setrecursionlimit(10**7)
inf = 10**20

def eratosthenes(upperBound):
    """エラトステネスの篩アルゴリズムによって、upperBound以下の素数すべてからなるリストを計算する。

    Args:
        upperBound(int): 計算したい素数リストに含まれる素数の上限値。
    Returns:
        list[int]: 計算された素数リスト。
    
    Examples:
    >>> eratosthenes(10)
    [2, 3, 5, 7]
    >>> eratosthenes(11)
    [2, 3, 5, 7, 11]
    """
    primeNumbers = []
    isPrime = [True for _ in range(upperBound + 1)]
    isPrime[0] = isPrime[1] = False
    divider = 0
    while divider <= math.sqrt(upperBound):
        if isPrime[divider]:
            # primeNumbers.append(divider)
            multiple = 2* divider
            while multiple <= upperBound:
                isPrime[multiple] = False
                multiple += divider
        divider += 1
    return [i for i in range(upperBound + 1) if isPrime[i]]

primeNumberList = eratosthenes(1000010)

def factorize(number):
    """与えられた整数を素因数分解する。素因数とその指数を辞書として返却する。

    Args:
        number(int) 
    Returns:
        dict[int,int] 素因数->指数の辞書。
    >>> factorize(6)
    {2: 1, 3: 1}
    >>> factorize(20)
    {2: 2, 5: 1}
    """
    exponents = {}
    for primeNumber in primeNumberList:
        while number%primeNumber == 0:
            number /= primeNumber
            if primeNumber in exponents:
                exponents[primeNumber] += 1
            else:
                exponents[primeNumber] = 1
    if number != 1:
        exponents[number] = 1
    return exponents

A,B = map(int,input().split())
gcd = fractions.gcd(A,B)
factorizedGcd = factorize(gcd)
print(len(factorizedGcd.keys()) + 1)

Submission status: Accepted

Solution code:
from fractions import gcd

def solve(string):
    a, b = map(int, string.split())
    g = gcd(a, b)
    ans = 1 if g % 2 else 2
    while g % 2 == 0:
        g //= 2
    for i in range(3, int(g**0.5) + 1, 2):
        if g % i == 0:
            ans += 1
        while g % i == 0:
            g //= i
    return str(ans + 1) if g > 1 else str(ans)

if __name__ == '__main__':
    print(solve(input()))

Submission status: Accepted

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

g = gcd(A, B)
n = int(sqrt(g))+1
ans = 1
for p in range(2,n+1):
    if g%p==0:
        ans += 1
        while g%p==0:
            g = g//p
if g!=1:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(n)
  return table

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


a,b = map(int,input().split())
gcd = gcd(a ,b)
print(len(np.unique(prime_decomposition(gcd)))+1)

Submission status: Accepted

Solution code:
from fractions import gcd


def solve(string):
    a, b = map(int, string.split())
    g = gcd(a, b)
    ans = 1 if g % 2 else 2
    while g % 2 == 0:
        g //= 2
    for i in range(3, int(g**0.5) + 1, 2):
        if g % i == 0:
            ans += 1
        while g % i == 0:
            g //= i
    return str(ans + 1) if g > 1 else str(ans)


if __name__ == '__main__':
    print(solve(input()))

Submission status: Accepted

Solution code:
from fractions import gcd


def get_primes(n):
    ans = 1 if n % 2 else 2
    while n % 2 == 0:
        n //= 2
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            ans += 1
        while n % i == 0:
            n //= i
    return ans + 1 if n > 1 else ans


def solve(string):
    a, b = map(int, string.split())
    g = gcd(a, b)
    return str(get_primes(g))


if __name__ == '__main__':
    print(solve(input()))

Submission status: Accepted

Solution code:
from fractions import gcd
import numpy as np


def get_primes(n):
    ans = 1
    m = int(n**0.5) + 1
    flags = np.zeros(m + 1, dtype=bool)
    for i in range(2, m + 1):
        if flags[i]:
            continue
        if n % i == 0:
            ans += 1
        while n % i == 0:
            n //= i
        flags[i:m + 1:i] = 1
    return ans + 1 if n > 1 else ans


def solve(string):
    a, b = map(int, string.split())
    g = gcd(a, b)
    return str(get_primes(g))


if __name__ == '__main__':
    print(solve(input()))

Submission status: Accepted

Solution code:
from fractions import gcd
import numpy as np


def get_primes(n):
    ans = 1
    m = int(n**0.5) + 1
    flags = np.zeros(m + 1, dtype=bool)
    for i in range(2, m + 1):
        if flags[i]:
            continue
        if n % i == 0:
            ans += 1
        while n % i == 0:
            n //= i
        flags[i:m + 1:i] = 1
    if n > 1:
        ans += 1
    return ans


def solve(string):
    a, b = map(int, string.split())
    g = gcd(a, b)
    return str(get_primes(g))


if __name__ == '__main__':
    print(solve(input()))

Submission status: Accepted

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, int(sqrt_a)):
    if (a % (i) == 0):
        list_a.append(i)
        while(a % (i) == 0):
            a = a//(i)
if a != 1:
    list_a.append(a)

for i in range(2, int(sqrt_b)):
    if (b % (i) == 0):
        list_b.append(i)
        while(b % (i) == 0):
            b = b//(i)
if b != 1:
    list_b.append(b)

# 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: Accepted

Solution code:
from fractions import gcd
import numpy as np


def get_primes(n):
    ans = []
    m = int(n**0.5) + 1
    flags = np.zeros(m + 1, dtype=bool)
    for i in range(2, m + 1):
        if flags[i]:
            continue
        while n % i == 0:
            n //= i
        ans.append(i)
        flags[i:m + 1:i] = 1
    if n > 1 and all(map(lambda x: n % x, ans)):
        ans.append(n)
    return ans


def solve(string):
    a, b = map(int, string.split())
    g = gcd(a, b)
    return str(len([p for p in get_primes(g) if g % p == 0]) + 1)


if __name__ == '__main__':
    print(solve(input()))

Submission status: Accepted

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

def factorizaion(n):
    p=2
    fcr=[]
    while p*p<=n:
        while n%p==0:
            fcr.append(p)
            n//=p
        p+=1
    if n>1:
        fcr.append(n)
    return fcr

x=factorizaion(a)
y=factorizaion(b)
print(len(set(x)&set(y))+1)

Submission status: Accepted

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

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

def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n //= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(n)
  return table
  
tmp = set(prime_decomposition(gcd(a,b)))

print(len(tmp)+1)

Submission status: Accepted

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

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

a_set = set(prime_factorize(a))
b_set = set(prime_factorize(b))
cd = list(a_set & b_set)
print(len(cd)+1)

Submission status: Accepted

Solution code:
a,b = map(int,input().split())
def gcd(x,y):
    if x < y:
        x,y = y,x
    while x%y != 0:
        a = x%y
        x = y
        y = a
    return y
N = gcd(a,b)
import math
n = math.floor(math.sqrt(N))
ans = 1
for i in range(2,n+1):
    if N%i == 0:
        ans += 1
        while N%i == 0:
            N /= i
if N != 1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
#素因数分解
def prime_factorize(x0):
    tmp_l = [1]
    if x0 == 1:
        return tmp_l
    if x0%2 == 0:
        tmp_l.append(2)
        while x0 % 2 == 0:
            x0 //=2
    if x0 > 2:
        i = 3
        while 1:
            if i > pow(x0,1/2):
                if x0 == 1:
                    break
                tmp_l.append(x0)
                break
            if x0 % i == 0:
                tmp_l.append(i)
                while x0 % i == 0:
                    x0 //= i   
            i+=2
    return tmp_l

#最大公約数
def gcd(x0, y0):
    if x0<y0:
        tmp0 = x0
        x0 = y0
        y0 = tmp0
    if y0 == 0:
        return x0
    else:
        return gcd(y0, x0 % y0)
        
a,b=map(int,input().split())

g = gcd(a,b)
print(len(prime_factorize(g)))

Submission status: Accepted

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

def trial_division(target):
    if target == 1: return False
    dest = int(math.sqrt(target)) + 1
    #print(dest)
    for i in range(2,dest):
        #print(f'i :{i} target: {target}')
        if target % i == 0:
            return False

    return True

A_div = set(make_divisors(A))
B_div = set(make_divisors(B))
AB_div = A_div & B_div
#print(AB_div)
count=1

for i in AB_div:
    #print(i)
    #print(trial_division(i))
    if(trial_division(i)):
        count+=1
print(count)

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a
def prime_factorize(n):
    c = []
    while n % 2 == 0:
        c.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            c.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        c.append(n)
    return c
d=prime_factorize(gcd(a,b))
e = len(set(d))
print(e+1)