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:
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
print(1+len(set(prime_factorize(a))&set(prime_factorize(b))))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
from math import gcd, sqrt
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


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


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


primes = prime_factorize(g)
print(len(primes)+1)

Submission status: Accepted

Solution code:
def factorization(n):
    arr = set()
    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.add(i)

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

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

    return arr

a,b = map(int, input().split())
a_soi = factorization(a)
b_soi = factorization(b)
both = list(a_soi & b_soi)
print(len(both)+1)

Submission status: Accepted

Solution code:
import math

a, b = list(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

fact = prime_factorize(gcd)
print(len(set(fact)) + 1)

Submission status: Accepted

Solution code:
def Prime_Factorization(N):
    if N<0:
        R=[[-1,1]]
    else:
        R=[]

    N=abs(N)
    k=2
    while k*k<=N:
        if N%k==0:
            C=0
            while N%k==0:
                C+=1
                N//=k
            R.append([k,C])
        k+=1

    if N!=1:
        R.append([N,1])
    if not R:
        R.append([N,1])

    return R
#============================
from math import gcd
A,B=map(int,input().split())
G=gcd(A,B)

if G==1:
    print(1)
else:
    P=Prime_Factorization(G)
    print(len(P)+1)

Submission status: Accepted

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

def factorize(n):
    factor = []
    if n % 2 == 0:
        f = [2, 1]
        n //= 2
        while n % 2 == 0:
            n //= 2
            f[1] += 1
        factor.append(f)

    k = 3
    while k * k <= n:
        if n % k == 0:
            f = [k, 1]
            n //= k
            while n % k == 0:
                n //= k
                f[1] += 1
            factor.append(f)
        k += 2
    if n != 1:
        factor.append([n, 1])
    return factor

a, b = map(int, input().split())
c = gcd(a, b)
f = factorize(c)
print(len(f) + 1)

Submission status: Accepted

Solution code:
def factorize(N):  # 素因数分解
    p, PRIME = 2, set()
    while p * p <= N:
        if N % p == 0:
            N //= p
            PRIME.add(p)
        else:
            p += 1
    if N > 1:
        PRIME.add(N)
    return PRIME


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

ans = factorize(a) & factorize(b)
print(len(ans) + 1)

Submission status: Accepted

Solution code:
import bisect, copy, heapq, math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

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

if g==1:
    print(1)
else:
    print(len(factorization(g))+1)

Submission status: Accepted

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

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

def cal(c):
    d = []
    while c%2 == 0:
        d.append(2)
        c //= 2
    f = 3
    while f**2 <= c:
        if c%f == 0:
            d.append(f)
            c //= f
        else:
            f += 2
    if c != 1:
        d.append(c)
    return d
    
c = gcd(a, b)
d = cal(c)
print(len(set(d))+1)

Submission status: Accepted

Solution code:
A,B = list(map(int,input().split()))
# A=10**10
# B=10**12

def gcd(a,b):
    x=min(a,b)
    y=max(a,b)
    
    while y%x != 0:
#         print(x,y)
        x_= y%x
        y = x
        x = x_
    return x

gcd = 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

P_F=[1]
P_F.extend(prime_factorize(gcd))
print(len(set(P_F)))

Submission status: Accepted

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

if min(a,b) == 1:
    print(1)
    exit()

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 //= i
            arr.append(i)
    if temp!=1:
        arr.append(temp)
    if arr==[]:
        arr.append(n)
    return arr

A = factorization(a)
B = factorization(b)
ans = len(set(A) & set(B))
print(ans+1)

Submission status: Accepted

Solution code:
import collections

def cin():
    in_ = list(map(int,input().split()))
    if len(in_) == 1:  return in_[0]
    else:  return in_

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 = cin()
A, B = min(A, B), max(A, B)
res = collections.Counter(prime_factorize(A))
keys = list(res.keys())
keys.append(1)
ans = 0
for i in keys:
    if B % i == 0:
        ans += 1
print(ans)

Submission status: Accepted

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

def prime_factorize(n):
    res = set()
    i = 2
    while i * i <= n:
        if n % i == 0:
            res.add(i)
            while n % i == 0:
                n //= i
        i += 1
    if n != 1:
        res.add(n)
    return res

ans = prime_factorize(A) & prime_factorize(B)
print(len(ans) + 1)

Submission status: Accepted

Solution code:
def prime_factorize(n):
    # 素因数分解して素数と1の集合を作る
    a = {1}
    while n % 2 == 0:
        a.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.add(n)
    return a


A, B = map(int, input().split())
cds = prime_factorize(A) & prime_factorize(B)
print(len(cds))

Submission status: Accepted

Solution code:
def prime_factorize(n):
    a = [1]
    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())
cds = set(prime_factorize(A)) & set(prime_factorize(B))
print(len(cds))

Submission status: Accepted

Solution code:
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3

    # for f in range(3,int(n**0.5)+1,2):
    #     if n%f == 0:
    #         a.append(f)
    #         n //= f
    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 = list(map(int,input().split()))
A, B = set(prime_factorize(a)), set(prime_factorize(b))
C = A&B
# print(A,B,C)

print(len(C)+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 = prime_factorize(A)
B = prime_factorize(B)
C = []
for i in A:
    if i in B:
        C += i,
print(1+len(set(C)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from math import gcd

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


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


print(len(factorization(g)) + (g != 1))

Submission status: Accepted

Solution code:
def input_li():
    return list(map(int, input().split()))


def input_int():
    return int(input())


def prime_factorization(n):
    table = []
    for x in range(2, int(n ** 0.5) + 1):
        while n % x == 0:
            table.append(x)
            n //= x
    if n > 1:
        table.append(n)
    return table


A, B = input_li()
A_SET = set(prime_factorization(A))
B_SET = set(prime_factorization(B))
print(len(A_SET & B_SET) + 1)

Submission status: Accepted

Solution code:
def input_li():
    return list(map(int, input().split()))


def input_int():
    return int(input())


def prime_factorization(n):
    table = []
    for x in range(2, int(n ** 0.5) + 1):
        while n % x == 0:
            table.append(x)
            n //= x
    if n > 1:
        table.append(n)
    return table


A, B = input_li()
A_SET = set(prime_factorization(A))
B_SET = set(prime_factorization(B))
print(len((A_SET) & set(B_SET)) + 1)

Submission status: Accepted

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

def factors_count(n):
    facs = dict()
    while n%2 == 0:
        facs.setdefault(2, 0)
        facs[2] += 1
        n //=2

    for f in range(3, int(n**0.5)+ 1, 2):
        while n%f == 0:
            facs.setdefault(f, 0)
            facs[f] += 1
            n //= f
    if n != 1:
        facs.setdefault(n, 0)
        facs[n] += 1
    return facs

afacs = factors_count(a)
bfacs = factors_count(b)

facs = set(afacs.keys()) & set(bfacs.keys())
print(len(facs)+1)

Submission status: Accepted

Solution code:
import sys
import math

stdin = sys.stdin

nm = lambda: map(int, stdin.readline().split())

a, b = nm()

n = math.gcd(a,b)

count = 1 # 1
for i in range(2, int(n**(1/2))+1):
    if n%i ==0:
        count +=1
        while n%i == 0:
            n = n/i
    if n ==1:
        break
if n != 1:
    count += 1

print(count)

Submission status: Accepted

Solution code:
from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
import math
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math as M
MOD=10**9+7
import random
#####################################
a,b=INPUT()
A=min(a,b)
B=max(a,b)
X=[]
P=[]
for i in range(1,int(M.sqrt(A)+1)):
    if A%i==0:
        if A//i==i:
            P.append(i)
        else:
            P.append(i)
            P.append(A//i)
Q=[]

for i in range(1,int(M.sqrt(B)+1)):
    if B%i==0:
        if B//i==i:
            Q.append(i)
        else:
            Q.append(i)
            Q.append(B//i)
X=list(set(P)&set(Q))
X.sort()
ans=0
#sprint(X)
bool=[True]*len(X)
for i in range(len(X)):
    if X[i]!=1 and bool[i]==True:
        ele=X[i]
        for j in range(i+1,len(X)):
            if X[j]%ele==0:
                bool[j]=False

for i in range(len(X)):
    if bool[i]==True:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    a,b = map(int,input().split())

    #gcd(a,b)の素因数分解
    import math
    gcd = math.gcd(a,b)

    p = []
    for i in range(2,int(math.sqrt(gcd))+1):
        while gcd % i == 0:
            gcd /= i
            p.append(i)
            
    p.append(int(gcd))
    p.append(1)
    print(len(list(set(p))))

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from math import*
A,B=sorted(map(int,input().split()))
prime=[]
i=1
while i**2<=A:
    if A%i==0:
        prime.append(i)
        prime.append(A//i)
    i+=1

prime=list(set(prime))
prime.sort()
L=len(prime)
ans=[1]*L
j=1
while j<L:
    now=prime[j]
    if B%now:
        ans[j]=0
    if ans[j]==0:
        j+=1
        continue
    k=j+1
    while k<L:
        if prime[k]%now==0:
            ans[k]=0
        k+=1
    j+=1

print(sum(ans))

Submission status: Accepted

Solution code:
from collections import Counter

def gcd(m, n):
    r = m % n
    return gcd(n, r) if r else n

def pf(N):
    res = []
    x = N
    y = 2
    while y*y <= x:
        while x % y == 0:
            res.append(y)
            x //= y
        y += 1
    if x > 1:
        res.append(x)
    return res

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math

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

def divisor(x):
    divs = []
    for i in range(1, math.floor(math.sqrt(x))+1):
        if x%i == 0:
            divs.append(i)
            if i**2 != x:
                divs.append(x//i)
    return divs

def evPrimal(x):
    if x < 4:
        return True
    divs = []
    for i in range(2, math.floor(math.sqrt(x))+1):
        if x%i == 0:
            return False
    return True

codiv = set(divisor(A)) & set(divisor(B))

for i in codiv:
    if evPrimal(i):
        count += 1

print(count)

Submission status: Accepted

Solution code:
def main():
    import numpy as np
    import math

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

    num_to_search = int(math.sqrt(gcd)) + 1

    def factorize_prime(number):
        RV = [1]
        
        if (number != 1):      
            while (number % 2 == 0):
                number //= 2
                RV.append(2)
            
            for i in range(3, num_to_search + 1):
                if (number % i == 0):
                    while (number % i == 0):
                        number //= i
                        RV.append(i)
        
        if (number != 1):
            RV.append(number)
        
        return(RV)

    
    cnt = factorize_prime(gcd)
    ans = len(set(cnt))
    


    
    print(ans)





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def prime_factors(n):       # 戻り値はiterable type
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            yield i             # whileループを進めるごとにイテレータに値を貯め続ける
    if n > 1:
        yield n

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

data = set(prime_factors(A)) & set(prime_factors(B))
print(len(data) + 1)

Submission status: Accepted

Solution code:
from fractions import gcd
def factorization(n):
    fac = {}
    count = 0
    while n % 2 == 0:
        n //= 2
        count += 1
    if count > 0:
        fac[2] = count
    for i in range(3, int(n ** .5) + 1, 2):
        count = 0
        while n % i == 0:
            n //= i
            count += 1
        if count > 0:
            fac[i] = count
    if n > 1:
        fac[n] = 1
    return fac

A, B = map(int, input().split())
fac = factorization(gcd(A, B))
print(len(fac) + 1)

Submission status: Accepted

Solution code:
def divisors(n):
    i = 1
    table = set()
    while i * i <= n:
        if not n % i:
            table.add(i)
            table.add(n//i)
        i += 1
    return table

def max2(x,y):
    return x if x > y else y

def rec(start_set, t):
    global res
    res = max2(res, t)
    next_set = []
    i = start_set[0]
    for j in start_set[1:]:
        if gcd(data[i], data[j]) == 1:
            next_set.append(j)
    if next_set:
        rec(next_set, t+1)
    return res

from math import gcd

A, B = map(int, input().split())
data = divisors(A) & divisors(B)
data = list(data)
data.sort()
L = len(data)
res = 0
print(rec(list(range(L)),1))

Submission status: Accepted

Solution code:
def primeFact(n):
    i = 2
    pl = []
    while i * i <= n:
        while n % i == 0:
            n /= i
            pl.append(i)
        i += 1
    if n > 1:
        pl.append(int(n))
    return pl


a, b = map(int, input().split())
print(len(set(primeFact(a)) & set(primeFact(b))) + 1)

Submission status: Accepted

Solution code:

from collections import defaultdict


def prime_factor(n):
    d = defaultdict(int)
    for i in range(2, n + 1):
        if i * i > n:
            break

        while n % i == 0:
            d[i] += 1
            n //= i

    if n != 1:
        d[n] += 1

    return d


A, B = map(int, input().split())
prime_a = prime_factor(A)
prime_b = prime_factor(B)
print(len(set(prime_a) & set(prime_b)) + 1)

Submission status: Accepted

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

# In[18]:


import math


# In[23]:


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


# In[24]:


# #nの約数を全て求める
# def divisor(n): 
#     i = 1
#     table = []
#     while i * i <= n:
#         if n%i == 0:
#             table.append(i)
#             table.append(n//i)
#         i += 1
#     table = list(set(table))
#     return table


# In[29]:


# def func():
#     mylist = []
#     tmp = 1
#     if A<=B:
#         for x in divisor(A):
#             if B%x==0 and math.gcd(tmp,x)==1:
#                 mylist.append(x)
#                 tmp *= x
#     else:
#         for x in divisor(B):
#             if A%x==0 and math.gcd(tmp,x)==1:
#                 mylist.append(x)
#                 tmp *= x
# #     print(mylist)
#     print(len(mylist))
# if __name__=="__main__":
#     func()


# In[30]:


gcd=math.gcd(A,B)
m = gcd
pf = {}
for i in range(2, int(m**0.5)+1):
    while m % i == 0:
        pf[i] = pf.get(i, 0)+1
        m //= i
if m > 1:
    pf[m] = 1
print(len(pf)+1)


# In[ ]:

Submission status: Accepted

Solution code:
a = list(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

print(len(set(prime_factorize(a[0])) & set(prime_factorize(a[1])))+1)

Submission status: Accepted

Solution code:
import bisect,collections,copy,heapq,itertools,math,string
import numpy as np
from numba import njit
import sys
sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

A,B = LI()

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

Ad = make_divisors(A)
Bd = make_divisors(B)
# c = list(Ad.intersection(Bd))
c = list(set(Ad) & set(Bd))

def is_prime_custom(n):
    # custom
    if n == 1: return True

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

count = 0
for i in c:
    if is_prime_custom(i):
        count += 1
print(count)

Submission status: Accepted

Solution code:
from math import *
from copy import deepcopy
A,B = map(int,input().split())
C = gcd(A,B)
E = deepcopy(C)
D = set()
for i in range(2,floor(sqrt(E))+1):
    while True:
        if C/i != (C/i)//1:
            break
        D.add(i)
        C /= i
if C != 1:
    D.add(int(C))
print(len(D)+1)

Submission status: Accepted

Solution code:
def prime_factorization(n):
    table = []
    for x in range(2, int(n ** 0.5) + 1):
        while n % x == 0:
            table.append(x)
            n //= x
    if n > 1:
        table.append(n)
    return table


A, B = map(int, input().split())
ad = set(prime_factorization(A))
bd = set(prime_factorization(B))

cnt = 0
for a in ad:
    if a in bd:
        cnt += 1
print(cnt+1)

Submission status: Accepted

Solution code:


A, B = 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, cnt])

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

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

    return arr

a_fac = factorization(A)
b_fac = factorization(B)
ans = 0
is_one = False
for af in a_fac:
    for bf in b_fac:
        if af[0] == bf[0]:
            ans += 1
            if af[0] == 1:
                is_one = True
if is_one:
    print(ans)
else:
    print(ans+1)

Submission status: Accepted

Solution code:
from math import sqrt

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

def divisor(a, b):
    max_num = int(sqrt(a))
    divisor_list = []
    for i in range(1, max_num + 1):
        if a % i == 0 and b % i == 0:
            divisor_list.append(i)
            # for j in divisor_list:
            #     if a % (i*j) == 0 and b % (i*j) == 0:
            #         divisor_list.append(i)
            # divisor_list.append(i)
        tmp = a//i
        if a % tmp == 0 and b % tmp == 0:
            divisor_list.append(tmp)
            # for j in divisor_list:
            #     if a % (tmp*j) == 0 and b % (tmp*j) == 0:

    return list(set(divisor_list))

common_list = divisor(A, B)
common_list.sort()

# print(common_list)

length = len(common_list)
max_common = common_list[-1]
prods = []
dic = {c: 0 for c in common_list}

for i in range(1, length):
    for j in range(1, length):
        prod = common_list[i] * common_list[j]
        if prod > max_common:
            continue
        else:
            dic[prod] = 1
ans = 0
for c in common_list:
    if dic[c] == 0:
        ans += 1
        # print(c)

print(ans)

Submission status: Accepted

Solution code:
# from pprint import pprint
# import math
# import collections

# n = int(input())
a, b = map(int, input().split(' '))


# a = list(map(int, input().split(' ')))

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n ** 0.55 // 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


fact_a = set([f[0] for f in factorization(a)])
fact_b = set([f[0] for f in factorization(b)])

ans = fact_a & fact_b
ans.add(1)

# print(fact_a, fact_b)
print(len(ans))

Submission status: Accepted

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)

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

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

    return arr
  

a,b=map(int,input().split())
al=factorization(a)
bl=factorization(b)

com=set(al) & set(bl)
if a==1 and b==1:
  print(1)
else:
  print(len(com)+1)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

A, B = mapint()
from math import gcd
g = 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 len(set(a))

print(prime_factorize(g)+1)

Submission status: Accepted

Solution code:
from collections import Counter
a,b=map(int,input().split())
def p_fact(n):
  m=n
  i=2
  a=[1]
  while n>1:
    if i>m**.5:
      a+=[n]
      break
    if n%i==0:
      n//=i
      a+=[i]
    else:i+=1  
  return a
af,bf=p_fact(a),p_fact(b)
da,db={},{}
for i in af:
  if da.get(i):da[i]+=1
  else:da[i]=1
for i in bf:
  if db.get(i):db[i]+=1
  else:db[i]=1
dc={}
for i in da:
  if db.get(i):dc[i]=min(da[i],db[i])
print(len(dc))

Submission status: Accepted

Solution code:
from fractions import gcd

A,B = map(int,input().split())
C = gcd(A,B)
nse = set()

for i in range(1,int(C**0.5+1)):
  if C%i == 0:
    nse.add(i)
    nse.add(C//i)
    
nli = list(nse)
nli.sort()
size = len(nli)

for i in range(1,size):
  n = nli[i]
  for j in range(i+1,size):
    if nli[j]%n == 0 :
      nse.add(nli[j])
      nse.remove(nli[j])

print(len(nse))

Submission status: Accepted

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

# 約数列挙関数
def make_divisor(n):
    divisor = []
    for i in range(1, int(n**(1/2))+1):
        if n % i == 0:
            divisor.append(i)
            if i != n//i:
                divisor.append(n//i)
    return divisor

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

cmn_div = make_divisor(max_cmn_div)
ans = 0
for i in cmn_div:
    if check_prime(i):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import math
a,b=map(int, input().split())
gcd=math.gcd(a,b)
m = gcd
pf = {}
for i in range(2, int(m**0.5)+1):
    while m % i == 0:
        pf[i] = pf.get(i, 0)+1
        m //= i
if m > 1:
    pf[m] = 1
print(len(pf)+1)

Submission status: Accepted

Solution code:
primes = []
boo = [True] * (int(1e6) + 1)
boo[0] = False; boo[1] = False
for i in range(2, len(boo)):
    if boo[i]:
        for j in range(i*i, len(boo), i):
            boo[j] = False
        primes.append(i)
        
# Finds the prime factors of a number
def findPF(num):
    ans = []
    PF_idx = 0
    PF = primes[PF_idx]
    while PF * PF <= num:
        while num % PF == 0:
            num //= PF
            ans.append(PF)
        PF_idx += 1
        PF = primes[PF_idx]
    if num != 1:
        ans.append(num)
    return ans

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

a, b = map(int, input().split())
temp = gcd(a, b)
print(len(set(findPF(temp)))+1)

Submission status: Accepted

Solution code:
import math
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= map(int,input().split())
c=math.gcd(a,b)
if c==1:
  print(1)
else:
  print(len(factorization(c))+1)

Submission status: Accepted

Solution code:
from math import sqrt


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

    return True


def make_divisors(a, b):
    lower_divisors = []
    upper_divisors = []

    i = 1
    n = min(a, b)
    m = max(a, b)

    while i*i <= n:
        if n % i == 0:
            # 大きい方の数が割れるか確認
            if m % i == 0:
                # 素数であるか確認
                if is_prime(i):
                    lower_divisors.append(i)

            # 割り切れる場合 i で割った数も約数
            if i != n // i:

                # i で割った数で大きいほうが割り切れるか
                if m % (n // i) == 0:

                    # 素数であるか
                    if is_prime(n//i):
                        upper_divisors.append(n//i)
        i += 1

    return lower_divisors + upper_divisors[::-1]


def main():
    A, B = [int(x) for x in input().split()]
    divisors = make_divisors(A, B)
    print(len(divisors))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
t = 1
# t = input()
# t = int(t)
def max(a,b):
	if a > b:
		return a
	return b
while t > 0:
	t -= 1
	a,b = map(int,input().strip().split())
	j = 1
	ma = {}
	mb = {}
	if a%2 == 0:
		ma[2] = 1
		while a%2 == 0:
			a /= 2
	p = math.sqrt(a) + 1
	p = int(p)
	for i in range(3,p,2):
		if a%i == 0:
			ma[i] = 1
			while a%i == 0:
				a /= i
	if a > 2:
		ma[a] = 1
	if b%2 == 0:
		mb[2] = 1
		while b%2 == 0:
			b /= 2
	p = math.sqrt(b) + 1
	p = int(p)
	for i in range(3,p,2):
		if b%i == 0:
			mb[i] = 1
			while b%i == 0:
				b /= i
	if b > 2:
		mb[b] = 1
	ans = 1
	for x,y in ma.items():
		if x in mb:
			ans += 1
	print(ans)

Submission status: Accepted

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

d=math.gcd(a,b)

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
  
r=make_divisors(d)
l=len(r)
ans=1
w=[True]*l
if l>=2:
  for x in range(1,l):
    if w[x]==True:
      ans+=1
      for y in range(x,l):
        if r[y]%r[x]==0:
          w[y]=False
          
print(ans)

Submission status: Accepted

Solution code:
import math
a, b = 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[i] = cnt
    if temp!=1:
        arr[temp] = 1
    if arr==[]:
        arr[n] = 1
    return arr


g = math.gcd(a, b)
print(len(factorization(g))+1)