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:
from functools import lru_cache


@lru_cache(maxsize=None)
def prime_factorization(n):
    """
    nを素因数分解して素因数のリストを返却する
    """
    primes = []
    while n % 2 == 0:
        primes.append(2)
        n //= 2
    i = 3
    while i ** 2 <= n:
        while n % i == 0:
            primes.append(i)
            n //= i
        i += 2
    if n != 1:
        primes.append(n)
    return primes


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

a_primes = set(prime_factorization(A))
b_primes = set(prime_factorization(B))

print(len(a_primes & b_primes) + 1)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque

def run():
    A,B = map(int, sysread().split())
    K = math.gcd(A,B)
    factorials = []
    L = int(max(A,B)**0.5)
    for i in range(2, L+1):
        done = False
        limit = int(i ** 0.5)
        for j in factorials:
            if j > limit:break
            if not i % j:
                done = True
                break
        if not done:
            factorials.append(i)

    factors = [1]
    for f in factorials:
        if f > K:break
        if not K % f:
            factors.append(f)
            while not K % f:
                K = K // f

    if K != 1:
        factors.append(K)
    print(len(factors))


    #print(factorials)
if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
def main():
    import sys

    def input(): return sys.stdin.readline().rstrip()
    
    def gcd(x,y):
        r = x%y
        if r==0:
            return y

        return gcd(y, r)

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

    tmp = c
    cnt = 1
    for i in range(2, int(c**0.5)+1):

        if tmp%i == 0:
            cnt += 1
            while tmp%i == 0:
                tmp /= i
    if tmp != 1:
        cnt += 1
    print(cnt) 

            
            
    




    
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import gcd

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]
  
A,B=map(int,input().split())
GCD = gcd(A,B)
GCDs = make_divisors(GCD)
ans = [1 for i in range(len(GCDs)//2+1)]
for i in range(1,len(GCDs)//2):
  for j in range(i+1,len(GCDs)//2+1):
    if GCDs[j]%GCDs[i]==0:ans[j]=0
print(sum(ans))

Submission status: Accepted

Solution code:
from fractions import gcd
def factorization(n): # => {prime:count,...}
    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:
a,b = map(int,input().split())
def gcd(x,y):
    if y == 0:
        return x
    return gcd(y,x%y)

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

Submission status: Accepted

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

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

def factorization(n):
    arr = [[1,1]]
    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])

    return arr

Cfac = factorization(C)
print(len(Cfac))

Submission status: Accepted

Solution code:
import math
from functools import reduce


def prime_factorize(n):
    """素因数分解する。"""
    def facs(n):
        """試し割り法における割る数を生成する。"""
        yield 2
        max_prime = int(pow(n, 0.5)) + 2
        for x in range(3, max_prime, 2):
            yield x

    ans = set()
    for fac in facs(n):
        if n % fac == 0:
            ans.add(fac)
            while n % fac == 0:
                n //= fac
    if n != 1:
        ans.add(n)
    return ans


def gcd_list(numbers):
    # これじゃすべての最大公約数を出しているだけ。
    # すべての組み合わせにおいて最大公約数が1でなくてはいけない。
    return reduce(math.gcd, numbers)


def main():
    a, b = [int(x) for x in input().split()]
    gcd_ = math.gcd(a, b)
    primes = prime_factorize(gcd_)
    print(len(primes) + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
from functools import reduce


def prime_factorize(n):
    """素因数分解する。"""
    def facs(n):
        """試し割り法における割る数を生成する。"""
        yield 2
        max_prime = int(pow(n, 0.5)) + 2
        for x in range(3, max_prime, 2):
            yield x

    ans = set()
    for fac in facs(n):
        while n % fac == 0:
            ans.add(fac)
            n //= fac
    if n != 1:
        ans.add(n)
    return ans


def gcd_list(numbers):
    # これじゃすべての最大公約数を出しているだけ。
    # すべての組み合わせにおいて最大公約数が1でなくてはいけない。
    return reduce(math.gcd, numbers)


def main():
    a, b = [int(x) for x in input().split()]
    gcd_ = math.gcd(a, b)
    primes = prime_factorize(gcd_)
    print(len(primes) + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
from collections import Counter
a, b = map(int, input().split())
x = math.gcd(a, b)

Nso = []
Nruto = math.sqrt(x)
Nruto = math.floor(Nruto)

for i in range(2, Nruto+1):
    while x % i == 0:
        x = x//i
        Nso.append(i)
    if x == 1:
        break
    Nruto = math.sqrt(x)
    Nruto = math.floor(Nruto)

Nso.append(x)
Nso.append(1)
Nso = Counter(Nso)
print(len(Nso))

Submission status: Accepted

Solution code:
def is_prime(n):
    if n == 2 or n == 3: return True
    if n < 2 or n%2 == 0: return False
    if n < 9: return True
    if n%3 == 0: return False
    r = int(n**0.5)
    f = 5
    while f <= r:
        if n%f == 0: return False
        if n%(f+2) == 0: return False
        f +=6
    return True  

def divisors(n):
    lower_divs , upper_divs = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divs.append(i)
            if i != n // i:
                upper_divs.append(n//i)
        i += 1
    return lower_divs + upper_divs[::-1]

def resolve():
    A, B = list(map(int, input().split()))
    divs = divisors(A)
    i = 1
    cnt = 0
    while i < len(divs):
        if B%divs[i]==0 and is_prime(divs[i]):
            cnt += 1
        i += 1
    print(cnt+1)
    

if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
import math
n,m=map(int,input().split())
gcd=math.gcd(m,n)
i=1
ans=[]
max=int(math.sqrt(gcd))
for i in range(2,max+2):
    while gcd%i==0:
        ans.append(i)
        gcd//=i
if gcd>1:
  ans.append(n)

print(len(set(ans))+1)

Submission status: Accepted

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

A,B = (int(x) for x in input().rstrip('\n').split())
c = math.gcd(A,B)
if c==1:
  print(1)
else:
  ps=[]
  d = math.floor(math.sqrt(c))
  for i in range(2,d+2):
    if c%i==0:
      if all(i%x!=0 for x in ps):
        ps.append(i)
        while c % i ==0:
          c = c//i
  if c > 1:
    ps.append(0)
  print(len(ps)+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())
list_A = set(prime_factorize(a))
list_B = set(prime_factorize(b))
ans = list_A & list_B
print(len(ans) + 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

print(len(set(prime_factorize(a)).intersection(set(prime_factorize(b))))+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())
aa = prime_factorize(a)
bb = prime_factorize(b)
ab = list(set(aa) & set(bb))
ab.sort()
print(len(ab)+1)

Submission status: Accepted

Solution code:
from collections import defaultdict
from sys import stdin
input = stdin.readline


def prime_fatorization(n):
  # O(sqrt(n))
  # a = []
  a = defaultdict(int)
  while not(n % 2):
    # a.append(2)
    a[2] += 1
    n //= 2
  f = 3
  while f * f <= n:
    if not(n % f):
      # a.append(f)
      a[f] += 1
      n //= f
    else:
      f += 2
  if n != 1:
    # a.append(n)
    a[n] += 1
  return a


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

  aprime = prime_fatorization(A)
  bprime = prime_fatorization(B)

  aset = set(aprime.keys())
  bset = set(bprime.keys())

  print(1+len(aset & bset))


if(__name__ == '__main__'):
  main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from sys import stdin
input = stdin.readline


def prime_fatorization(n):
  # O(sqrt(n))
  # a = []
  a = defaultdict(int)
  while not(n % 2):
    # a.append(2)
    a[2] += 1
    n //= 2
  f = 3
  while f * f <= n:
    if not(n % f):
      # a.append(f)
      a[f] += 1
      n //= f
    else:
      f += 2
  if n != 1:
    # a.append(n)
    a[n] += 1
  return a


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

  aprime = prime_fatorization(A)
  bprime = prime_fatorization(B)

  aset = set()
  bset = set()

  for ap in aprime.keys():
    aset.add(ap)

  for bp in bprime.keys():
    bset.add(bp)

  print(1+len(aset & bset))


if(__name__ == '__main__'):
  main()

Submission status: Accepted

Solution code:
import math

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

def factorization(n):
    plist = primelist(int(n**0.5))
    factor = []
    for p in plist:
        k = 0
        while n%p==0:
            k+=1
            n//=p
        if k>0:
            factor.append((p,k))
        if n==1:
            break
    if n!=1:
        factor.append((n,1))

    return factor

def 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 main():
    a,b = tuple(map(int,input().split()))

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math

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

def factorization(n):
    plist = primelist(int(n**0.5))
    factor = []
    for p in plist:
        k = 0
        while n%p==0:
            k+=1
            n//=p
        if k>0:
            factor.append((p,k))
        if n==1:
            break
    if n!=1:
        factor.append((n,1))

    return factor

def 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 main():
    a,b = tuple(map(int,input().split()))

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

if __name__ == "__main__":
    main()

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())
g = math.gcd(a,b)
l = factorization(g)
l = list(map(lambda x:x[0],l))
lenl = len(l) if l != [1] else 0
print(lenl+1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict, deque

def F(n: int):
    i = 2
    while i * i <= n:
        while n % i == 0: yield i; n //= i
        i += 1
    if n != 1: yield n

(a, b), c = map(lambda x: set(F(int(x))), input().split()), 0
for i in a: c += 1 if i in b else 0
print(c + 1)

Submission status: Accepted

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

a,b = map(int,input().split())
A = prime_factorize(a)
B = prime_factorize(b)
G = []
for i in set(A):
    if i in set(B):
        G.append(i)
print(len(set(G)) + 1)

Submission status: Accepted

Solution code:
import math
A, B = map(int, input().split())
 
 
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)
    a.sort()
    return a
 
 
print(len(list(set(prime_factorize(math.gcd(A, B))))))

Submission status: Accepted

Solution code:
#D 素数の公約数-> 素因数分解で共通な素因数を求めて個数を入力
import sys
a, b = map(int, input().split())

#素因数分解(2以降)
def factorization(n):
    arr = []
    tmp = n
    #2から√n でnを割る ･･･割れた回数を指数として追加
    for i in range(2, int(n ** 0.5 // 1) + 1):
        if tmp % i == 0:
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            arr.append([i, cnt])
    if tmp != 1:  #割り切れなかったとき
        arr.append([tmp, 1])
    if arr == []: #素数の場合(割れなかった場合)
        arr.append([n, 1])
    return arr

a = factorization(a)
b = factorization(b)
ans = 1
# print(a, b)
if a[0][0] == b[0][0] == 1:
    print(ans)
    sys.exit()
for i in a:
    for j in b:
        if i[0] == j[0]:
            ans += 1
print(ans)

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 set(a)
A,B=map(int,input().split())
sa, sb = prime_factorize(A),prime_factorize(B)
print(len(sa&sb)+1)

Submission status: Accepted

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

lst = factorization(g)
if lst[0][0] == 1:
  print(1)
  exit()
else:
  print(len(lst) + 1)

Submission status: Accepted

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

a,b=map(int,input().split())
a=make_divisors(a)
b=make_divisors(b)
a=set(a)
b=set(b)
s=sorted(a&b)
ans=[1]
for i in s[1:]:
    switch=0
    for j in ans[1:]:
        if i%j==0:
            switch=1
            break
    if switch==0:
        ans.append(i)
print(len(ans))

Submission status: Accepted

Solution code:
def factorize(N):
    if N == 1: return {1:1}
    res = {}
    for i in range(2, N):
        if i**2 > N: break
        if N % i != 0: continue
        num = 0
        while N % i == 0:
            N = int(N/i)
            num += 1
        res[i] = num
    if N>1: res[N] = 1
    return res

A, B = map(int, input().split())
resA = factorize(A)
resB = factorize(B)
res = set(resA.keys()) & set(resB.keys())
ans = len(res) if 1 in res else len(res)+1
print(ans)

Submission status: Accepted

Solution code:
#n=int(input())
a,b=map(int,input().split())
#l=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]

def prime_factorize(n):
    n_origin=n+0
    primelist=[]
    a=2
    while a*a<=n_origin:
        if n%a!=0:
            a+=1
            continue
        ex=0
        while n%a==0:
            ex+=1
            n=n//a
        primelist.append([a,ex])
        a+=1
    if n!=1:
        primelist.append([n,1])
    return primelist

import math
gcd=math.gcd(a,b)#最大公約数
primelist=prime_factorize(gcd)
print(len(primelist)+1)

Submission status: Accepted

Solution code:
# Coding is about expressing your feeling, and
# there is always a better way to express your feeling_feelme
import sys
import math
# sys.stdin=open('input.txt','r')
# sys.stdout=open('output2.txt','w')
from sys import stdin,stdout
from collections import deque,defaultdict
from math import ceil,floor,inf,sqrt,factorial,gcd,log2
from copy import deepcopy
ii1=lambda:int(stdin.readline().strip())
is1=lambda:stdin.readline().strip()
iia=lambda:list(map(int,stdin.readline().strip().split()))
isa=lambda:stdin.readline().strip().split()
mod=int(1e9 + 7)

def divisor(n):
    ans={}
    m=int(n**0.5)+1
    for i in range(1,m):
        if n%i==0:
            ans[i]=1
            ans[n//i]=1
    return ans
def prime(n):
    if n<=3:
        return True
    m=int(n**0.5)+1
    if n%2==0:
        return False
    for i in range(3,m,2):
        if n%i==0:
            return False
    return True

a,b=iia()
ans=divisor(a)
ans2=divisor(b)
res=[]
for i,j in ans.items():
    if i in ans2:
        res.append(i)

#print(res)
count=0
for i in res:
    if prime(i):
        count+=1
print(count)

Submission status: Accepted

Solution code:
import sys
import math

A, B = map(int, sys.stdin.readline().split())
gcd = math.gcd(A, B)


def factrization_prime(number):
    factor = {}
    div = 2
    s = math.sqrt(number)
    # print(s)
    while div < s:
        div_cnt = 0
        while number % div == 0:
            div_cnt += 1
            number //= div
        if div_cnt != 0:
            factor[div] = div_cnt
        div += 1
    if number > 1:
        factor[number] = 1
    return factor

factors = factrization_prime(gcd)
print(len(factors) + 1)

Submission status: Accepted

Solution code:
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

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

a, b = MAP()
n = gcd(a, b)
s = sorted(divisor(n))
t = [1]*len(s)

ans = 0
for i in range(1, len(s)-1):
    if t[i] == 0:
        continue
    else:
        for j in range(i+1, len(s)):
            if t[j] == 0:
                continue
            else:
                if s[j] % s[i] == 0:
                    t[j] = 0
print(sum(t))

Submission status: Accepted

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


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

#「公約数は最大公約数の約数」
# ans = 最大公約数の素因数の個数

# A,Bの最大公約数
temp = math.gcd(A, B)
# 最大公約数を素因数分解する
temp = prime_factorize(temp)
# setにして重複除く
temp = set(temp)
# 長さを取得
ans = len(list(temp))

print(ans)

Submission status: Accepted

Solution code:
def make_divisors(n:int) -> list:
    """約数を列挙"""
    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]

import math
def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False
  m = math.floor(math.sqrt(n)) + 1
  for p in range(3, m, 2):
      if n % p == 0:
        return False
  return True

A, B = map(int, input().split())
div_A = make_divisors(A)
div_B = make_divisors(B)
cd = (set(div_A) & set(div_B))
ans = 0
for n in cd:
    if isPrime(n):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from math import gcd

def factorization(n):
    pf_cnt = {}
    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
            if i != 1: pf_cnt[i] = cnt

    if temp != 1: pf_cnt[temp] = 1
    if not pf_cnt and n != 1: pf_cnt[n] = 1

    return pf_cnt

a,b = map(int, input().split())
ab_gcd = gcd(a,b)
fac = factorization(ab_gcd)
print(len(fac)+1)

Submission status: Accepted

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


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

g = gcd(a, b)
num = g

ans = 1

for i in range(2, int(g ** 0.5) + 1):

    if num % i == 0:
        ans += 1
        while num % i == 0:
            num = num // i

if num != 1:
    ans += 1

print(ans)

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())

setA = set(prime_factorize(A))
setB = set(prime_factorize(B))
print(len(setA & setB)+1)

Submission status: Accepted

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

def prime_factorize(n):
    a = set({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
print(len(prime_factorize(a) & prime_factorize(b)))

Submission status: Accepted

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


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


print(len(list(set(prime_factorize(math.gcd(A, B))))))

Submission status: Accepted

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


def prime_fact(g):
    s = {1}
    i = 2
    # N=p x qとした時、(p < q)
    # 必ず p <= root(N)
    # そのためp**2までを調べればok
    while i*i <= g:
        while g % i == 0:
            g //= i
            s.add(i)
        i += 1
    s.add(g)
    return s


a, b = map(int, input().split())
G = gcd(a, b)
print(len(prime_fact(G)))

Submission status: Accepted

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

import sys

input = sys.stdin.buffer.readline

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

def lcm(a,b):
    return a*b // gcd(a,b)

def prime_factorize(n):
    pf={}
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            pf[i] = pf.get(i, 0) + 1
            n //= i
    if n > 1: pf[n] = 1
    return pf

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

pf = prime_factorize(gcd(A,B))
print(len(pf) + 1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

def lcm(a, b):
    return a * b // gcd(a, b)

def prime_factorize(m):
    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
    return pf

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

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

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

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

    return arr
def main3():
    n,m=map(int, input().split())
    k = factorization(n)
    k1 = factorization(m)

    y1 = set()
    y2 = set()

    for i in k:
        y1.add(i[0])
    for i in k1:
        y2.add(i[0])
    y1.add(1)
    y2.add(1)

    kouyaku = y1&y2
    print(len(kouyaku))



if __name__ == '__main__':
    main3()

Submission status: Accepted

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

def prime_factor(n):
    res = set([1])
    for i in range(2, n + 1):
        if i * i > n:
            break
            
        while n % i == 0:
            res.add(i)
            n //= i
            
    if n != 1:
        res.add(n)
        
    return res

print(len(prime_factor(A) & prime_factor(B)))

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
pfa={}
m=a
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pfa[i]=pfa.get(i,0)+1
        m//=i
if m>1:pfa[m]=1
pfb={}
m=b
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pfb[i]=pfb.get(i,0)+1
        m//=i
if m>1:pfb[m]=1
aa=set()
bb=set()
for i in pfa.keys():
    aa.add(i)
for i in pfb.keys():
    bb.add(i)
print(len(aa&bb)+1)

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
import math
c= math.gcd(a,b)
c2=c
l=[]
i=2
while i<=c:
  if c % i==0:
    c=c//i
   
    l.append(i)
  else:
    i+=1
  if i*i-1>c:
    l.append(c)
    break
  
print(len(set(l))+1)

Submission status: Accepted

Solution code:
#  A, B のGCFの約数の、素因数はいくつか
import math

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


def factorization(n):
    arr = [1]
    tmp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if tmp % i == 0:
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            arr.append(i)
    if tmp != 1:
        arr.append(tmp)
    if not arr:
        arr.append(n)
    return arr


factors = factorization(gcf)
print(len(factors))

Submission status: Accepted

Solution code:
import sys,fractions
input = sys.stdin.readline

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

if g == 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:
            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 len(arr)+1


print(factorization(g))

Submission status: Accepted

Solution code:
A,B = map(int,input().split())
from fractions import gcd
C = gcd(A,B)
num = []
for i in range(2,int(C**0.5)+1):
    while C%i==0:
        num.append(i)
        C //= i
if C != 1:
    num.append(C)
from collections import Counter
CC = Counter(num)
print(len(CC)+1)

Submission status: Accepted

Solution code:
a, b = map(int,input().split())
#素因数分解
def prime(n):
    i = 2
    table = set()
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.add(i)
        i += 1
    if n > 1:
        table.add(n)
    return table

print(len(prime(a).intersection(prime(b))) + 1)

Submission status: Accepted

Solution code:
#1は含まれない
def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = set(table)
    return table

def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1


A,B=map(int,input().split())
AL = divisor(A)
BL = divisor(B)
AB = list(AL & BL)
cnt = 1
for l in AB:
    if is_prime(l):
        cnt+=1

print(cnt)

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())
div_A = set(prime_factorize(A))
div_B = set(prime_factorize(B))
A_and_B = div_A & div_B
print(len(A_and_B))