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:
import fractions
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 random

def is_prime(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True
  
A,B = map(int,input().split())

g = fractions.gcd(A,B)
l = make_divisors(g)
su = 1
for li in l:
  if is_prime(li):
    su+=1
    
print(su)

Submission status: Accepted

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

import sys
import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
                

    from fractions import gcd
    a, b = mi()
    g = gcd(a, b)
    # g = math.gcd(a, b)

    n = int(math.sqrt(g) + 1)
    table = [True for _ in range(n)]
    table[0] = False
    table[1] = False
    # 2 の倍数については特別扱いをして定数倍高速化
    primes = [2]
    for p in range(3, n, 2):
        if table[p]:
            primes.append(p)
            for i in range(p**2, n, p):
                table[i] = False
    
    def calc_prime(num):
        cnt = 0
        # print(table)
        # print(primes)
        for p in primes:
            if p > num:
                break
            if num % p == 0:
                cnt += 1
                while p <= num and num % p == 0:
                    num //= p
        if num != 1:
            cnt += 1    # sqrt(num) までわりまくってなおそれ以上の数が約数として残っている -> こいつも素数
        return cnt

    print(calc_prime(g)+1)    # 1 分をたす

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

def factorize(n):
    ## 素因数分解
    # arr = factorize(20)
    # arr == [[2, 2], [5, 1]]
    
    result = []
    tmp = n
    for k in range(2, int(n ** 0.5) + 1):
        cnt = 0
        while tmp % k == 0:
            cnt += 1
            tmp //= k
        if cnt > 0:
            result.append([k, cnt])
    if tmp != 1:
        result.append([tmp, 1])
    return result

def divisorize(n):
    ## 約数
    # arr = factorize(20)
    # arr == [2, 4, 5, 10, 20]
    f = factorize(n)
    divisors = [1]
    for k in range(len(f)):
        num_divisors = len(divisors)
        for i in range(1, f[k][1] + 1):
            for j in range(num_divisors):
                divisors.append(divisors[j] * f[k][0] ** i)
    return sorted(divisors)

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

da = factorize(a)
da = [1] + [k[0] for k in da]

db = factorize(b)
db = [1] + [k[0] for k in db]

i = set(da).intersection(db)

print(len(i))

Submission status: Accepted

Solution code:
# 初期入力
A,B = (int(x) for x in input().split())

#素因数分解
def soinsu_bunkai(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を素因数分解
A_soinsu =soinsu_bunkai(A)
B_soinsu =soinsu_bunkai(B)

#共通の素数を探す
kyotu_soinsu ={}
a_sosu ={i for i in A_soinsu.keys()}
b_sosu ={i for i in B_soinsu.keys()}
kotae = a_sosu & b_sosu

print(len(kotae)+1) # 素数「１」を足す

Submission status: Accepted

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

prime_count = Counter()
for i in range(2, math.ceil(math.sqrt(n))+1):
  while n % i == 0:
    n /= i
    prime_count[i] += 1
if n > 1:
  prime_count[int(n)] += 1

print(len(prime_count)+1)

Submission status: Accepted

Solution code:
def pf(n):
  a = []
  N = n
  for i in range(2, int(pow(N,0.5)//1+2)):
    if n%i==0:
      count=0
      while n%i==0:
        count+=1
        n//=i
      a.append(count)
  if n!=1:
    a.append(1)
  if a==[]:
    a.append(1)
  return a
import fractions
A,B=map(int,input().split())
c=fractions.gcd(A,B)
ans=len(pf(c))
print(ans+(1 if c>1 else 0))

Submission status: Accepted

Solution code:
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations

input = sys.stdin.readline

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

ans = 1

for num in sorted(list(set(prime_factorize(a)))):
    if num in set(prime_factorize(b)):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
A,B = map(int,input().split())
def gcd(x,y):
    if x<y:x,y = y,x
    if y==0:return x
    return gcd(y,x%y)
G = gcd(A,B)
S = set()
S.add(1)
n = G
for i in range(2,G+1):
    if i*i>n:
        S.add(n)
        break
    if n%i==0:
        S.add(i)
    while n%i==0:
        n//=i
print(len(S))

Submission status: Accepted

Solution code:
import math
def trial_division(n):
    a = [1]
    for i in range(2,int(math.sqrt(n)) + 1):
        while n % i == 0:
            n //= i
            a.append(i)
    a.append(n)
    return a

A, B = map(int, input().split())
print(len(set(trial_division(A))&set(trial_division(B))))

Submission status: Accepted

Solution code:
import math
from fractions import gcd

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

facs = [1]
i = 2
while i*i <= g:
    if g == 1:
        break
    if g % i == 0:
        facs.append(i)
        while g % i == 0:
            g //= i
    i += 1
if g != 1:
    facs.append(g)

print(len(facs))

Submission status: Accepted

Solution code:
from fractions  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):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i,cnt])
    # 上のループを通した後にtempが1じゃなかったら、だけど、nが素数以外にそんなケースある？
    if temp!=1:
        arr.append([temp, 1])
    
    # 素数だったときの処理
    if arr == []:
        arr.append([n,1])

    return arr
factors = factorization(g)
common_divide = [1] + [factor[0] for factor in factors]
total = len(common_divide)
if common_divide == [1,1]:
    total = 1
print(total)

Submission status: Accepted

Solution code:
import fractions
def factorization(n):
    arr=[]
    tmp=n
    for i in range(2,int(n**0.5)+1):
        if(tmp%i==0):
            cnt=0
            while tmp%i==0:
                cnt+=1
                tmp//=i
            arr.append([i,cnt])
    arr.append([1,1])
    if(tmp!=1):
        arr.append([tmp,1])
    return arr
A,B=map(int,input().split())
g=fractions.gcd(A,B)
li=factorization(g)
print(len(li))

Submission status: Accepted

Solution code:
from fractions import gcd
a,b=map(int,input().split())
num=gcd(a,b)
l=[1]
while num!=1:
    x=int(num**(1/2))
    for i in range(2,x+2):
        if num%i==0:
            num=num//i
            l.append(i)
            break
        elif i==x+1:
            l.append(num)
            num=1
            break
print(len(set(l)))

Submission status: Accepted

Solution code:
import fractions

def prime_function(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())
GCD=fractions.gcd(A,B)
print(len(set(prime_function(GCD)))+1)

Submission status: Accepted

Solution code:
from fractions import gcd
from collections import deque

a, b = map(int, input().split())
x = gcd(a, b)
y = int(x ** 0.5)
cd = deque([])
if x ** 0.5 % 1 == 0:
    cd.append(y)
    y -= 1
prime = []
for i in range(y, 0, -1):
    if x % i == 0:
        cd.appendleft(i)
        cd.append(x // i)

def prime_check(x, prime):
    for y in prime:
        if x % y == 0:
            return False
    return True

for x in cd:
    if prime_check(x, prime) and x != 1:
        prime.append(x)
print(len(prime) + 1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
D - Disjoint Set of Common Divisors
https://atcoder.jp/contests/abc142/tasks/abc142_d

"""
import sys


from collections import defaultdict

def prime_factor(N):
    factors = defaultdict(int)
    for i in range(2, int(N**0.5)+1):
        while N % i == 0:
            factors[i] += 1
            N //= i
    if N != 1:
        factors[N] = 1

    return factors

def solve(A, B):
    pA = prime_factor(A)
    pB = prime_factor(B)
    res = [1]
    for k in pA.keys():
        if k in pB:
            res.append(k)
    return len(res)


def main(args):
    A, B = map(int, input().split())
    ans = solve(A, B)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

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

def so(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
y = set(so(x))
print(len(y)+1)

Submission status: Accepted

Solution code:
import fractions
a,b=map(int,input().split())
g=fractions.gcd(a,b)
ans=1
i=2
while i*i<=g:
    if g%i==0:
        ans+=1
        while g%i==0:
            g//=i
    i+=1
if g>1:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
import random

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

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

a_divs = make_divisors(a)
b_divs = make_divisors(b)

a_b_divs = list(set(a_divs) & set(b_divs))
a_b_divs.sort()

# 素数判定
# https://pashango-p.hatenadiary.org/entry/20090704/1246692091
# ミラー・ラビン(Miller-Rabin)テスト
def is_prime3(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True
# 1を含むため
ans = 1
for j in a_b_divs:
    if is_prime3(j) == True:
        #print(j)
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from math import sqrt


def prime_factorize(n):
    result = []
    for i in range(2, int(sqrt(n)) + 1):
        if n % i != 0:
            continue
        t = 0
        while n % i == 0:
            n //= i
            t += 1
        result.append((i, t))
        if n == 1:
            break
    if n != 1:
        result.append((n, 1))
    return result


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

Submission status: Accepted

Solution code:
import math
from fractions import gcd

def factorization(n):
    arr = []
    tmp = n
    for div in range(2, int(math.sqrt(n)) + 2):
        if tmp % div == 0:
            cnt = 0
            while tmp % div == 0:
                cnt += 1
                tmp //= div
            arr.append([div, cnt])

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

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

    return arr

if __name__ == '__main__':
    A, B = map(int, input().split())
    g = gcd(A, B)
    if g == 1:
        print(1)
        exit()
    facts = factorization(g)
    print(len(facts) + 1)

Submission status: Accepted

Solution code:
import math

def divisors(n):
    s = set()
    for x in range(2, math.ceil(n ** 0.5) + 1):
        while n % x == 0:
            s.add(x)
            n /= x
            if n == 1:
                break
    if n > 1:
        s.add(n)
    return s
 
a, b = map(int, input().split())
d = divisors(a) & divisors(b)
print(len(d) + 1)

Submission status: Accepted

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

import fractions
gcd = fractions.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 gcd == 1:
    print(1)
else:
    fact = factorization(gcd) 
    print(len(fact) + 1)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import math
from functools import reduce
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm_base(a, b):
    return (a * b) // gcd(a, b)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

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 main():
  A, B = map(int, readline().split())
  g = gcd(A, B)
  L = factorization(g)
  if L[0][0] == 1:
    ans = 1
  else:  
    ans = len(L) +1
  
  print(ans)
  
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import fractions

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

g = fractions.gcd(a, b)

ans = 0
i = 2
while i * i <= g:
    if g % i == 0:
        ans += 1
        while g % i == 0:
            g //= i
    i += 1

if g > 1:
    ans += 1

print(ans + 1)

Submission status: Accepted

Solution code:
from fractions import gcd
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

gcd = gcd(A, B)
divisors = make_divisors(gcd)

def is_prime(n):
    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 range(len(divisors)):
    if is_prime(divisors[i]):
        count += 1

print(count)

Submission status: Accepted

Solution code:
from fractions import *;g=gcd(*map(int,input().split()));c=i=1
while i*i<=g and g>1:
  i+=1;c+=g%i<1
  while g%i<1:g/=i
print(c+(g>1))

Submission status: Accepted

Solution code:
import math
import collections

def trial_division(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(int(n))
    return a
A, B= map(int,input().split())

Adev = list(collections.Counter(trial_division(A)).keys())
Bdev = list(collections.Counter(trial_division(B)).keys())
print(len(list(set(Adev) & set(Bdev)))+1)

Submission status: Accepted

Solution code:
def main():
    a, b = map(int, input().split())
    common_divisors = set(get_divisors(a)) & set(get_divisors(b))
    number_of_prime_common_divisor = sum([is_prime(i) for i in common_divisors])
    print(number_of_prime_common_divisor+1)

def get_divisors(n):
    out = []
    if n < 1:
        return out
    m = int(n**0.5)
    for i in range(1, m+1):
        if not n%i:
            out.append(i)
            if n != i**2:
                out.append(n//i)
    return out

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
a, b = map(int, input().split())
work = gcd(a, b)
count = 1
for i in range(2, int(work**0.5)+1):
    flag = False
    while work%i == 0:
        work //= i
        if not flag:
            count += 1
        flag = True
if work > 2:
    count += 1
print(count)

Submission status: Accepted

Solution code:
from fractions import *
g=gcd(*map(int,input().split()))
c=i=1
while i*i<=g and g>1:
  i+=1; c+=g%i<1
  while g%i<1: g//=i
print(c+(g>1))

Submission status: Accepted

Solution code:
from fractions import *
g=gcd(*map(int,input().split()))
c=1
for i in range(2,int(g**.5)+1):
  if g<2: break
  if g%i<1: c+=1
  while g%i<1: g//=i
print(c+(g>1))

Submission status: Accepted

Solution code:
from fractions import *
a,b=map(int,input().split())
g=gcd(a,b)
l=[g]
for i in range(2,int(g**.5)+1):
  if g%i<1: l+=[i,g//i]
c=1
for i in sorted(l):
  if g<2: break
  if g%i<1: c+=1
  while g%i<1: g//=i
print(c)

Submission status: Accepted

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


def factorization(n):
    arr = set()
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            arr.add(i)
            while n % i == 0:
                n //= i

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

    if not arr:
        arr.add(n)

    arr.add(1)
    return arr


a = factorization(A)
b = factorization(B)
inter = a & b

print(len(inter))

Submission status: Accepted

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

def fctr1(n): 
    f = {}
    c = 0
    r = int(n ** 0.5)
    for i in range(2, r + 2):
        while n % i == 0:
            c += 1
            n = n // i
        if c != 0:
            f[i] = c
            c = 0
    if n != 1:
        f[n] = 1
    return f


a = fctr1(A)
b = fctr1(B)


cd_dic = {1: 1}
key_list = [1]

for k, v in a.items():
    if k in b:
        key_list.append(k)
        n = min(v, b[k])
        cd_dic[k] = n

print(len(cd_dic))

Submission status: Accepted

Solution code:
from fractions import gcd
from math import sqrt
A, B = map(int, input().split())
n = gcd(A,B)
ans = 0
i = 2
while i ** 2 <= n:
    if n%i == 0:
        ans += 1
        while n%i == 0:
            n //= i
    i += 1
if n > 1:
    ans += 1
print(ans+1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
# int(input()) # 入力が1つ
a, b = map(int, input().split()) # 入力が複数
# [int(i) for i in input().split()] # 配列で数字
# 公約数の中から、素数を選べばいいのかな。


def is_prime(num):
    if num == 2:
        return True
    if num < 2 or num % 2 == 0:
        return False
    sqrt_num = num ** 0.5
    i = 2
    while i <= sqrt_num:
        if num % i == 0:
            return False
        i += 1
    return True

def lc(n):
    l = set()
    i = 1
    while i ** 2 <= n:
        if n % i == 0:
            l.add(i)
            l.add(n // i)
        i += 1
    return l
A = lc(a)
B = lc(b)
LC = list(A & B)

primes = []
for n in LC:
    if n == 1:
        primes.append(n)
    elif is_prime(n):
        primes.append(n)
ans = len(primes)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import count


def prime_factors(n):
  counter = defaultdict(int)  
  for i in count(2):
    if i * i > n:
      break
    while n % i == 0:
      n //= i
      counter[i] += 1
  if n != 1:
    counter[n] = 1
  return counter


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

a = prime_factors(A)
b = prime_factors(B)

print(len({k for k in a} & {k for k in b}) + 1)

Submission status: Accepted

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

gcd = fractions.gcd(a,b)

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

ans = len(set(prime_factorize(gcd)))

print(ans+1)

Submission status: Accepted

Solution code:
def prime_decomposition(n):
    i = 2
    result = []
    while i ** 2 <= n:
        while not n % i:
            result.append(i)
            n //= i
        i += 1
    if n > 1:
        result.append(n)
    return result

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

Submission status: Accepted

Solution code:
import sys
from collections import Counter

input = sys.stdin.readline


def calc_prime_factors(n):
    """Trial division"""
    factors = []
    # factor: 2
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    # factor: 3, 5, 7, 11, ...
    f = 3
    while f ** 2 <= n:
        if n % f == 0:
            factors.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        factors.append(n)
    return Counter(factors).keys()


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

    A_keys = calc_prime_factors(A)
    B_keys = calc_prime_factors(B)
    ans = len(set(A_keys) & set(B_keys)) + 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def print_list(l): print(*l, sep='\n')
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def No(): print('No')

def sieves_of_e(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 is_prime


def prime_factorize(n):
    res = []
    for i in range(2, int(n**0.5)+1):
        if n % i != 0: continue
        ex = 0

        while (n % i == 0):
            ex += 1
            n //= i
        res.append((i, ex))
    if n != 1: res.append((n, 1))
    return res

A,B = imn()

pf = prime_factorize(gcd(A,B))

print(len(pf)+1)

Submission status: Accepted

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

a,b=map(int,input().split())
import collections
da = collections.Counter(factorize(a))
db = collections.Counter(factorize(b))
ans = 0
for num,cnt in da.items():
    if db[num]!=0:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from math import sqrt
a,s=map(int,input().split())
f=gcd(a,s)
ans=1
if f<=3:print(1+(f!=1));exit()
for i in range(2,int(sqrt(f))+1):

  if f%i==0:
    ans+=1
    while f%i==0:f//=i
print(ans+(f!=1))

Submission status: Accepted

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

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(n**0.5)+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 == [] and n != 1:
        arr.append([n, 1])
    return arr

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

Submission status: Accepted

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

#素因数分解した結果を2次元配列にして返す
def prime_factorize(n):
    primelist=[]
    a=2
    while a*a<=n:
        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 fractions
g=fractions.gcd(a,b)

pfs=prime_factorize(g)

print(1+len(pfs))

Submission status: Accepted

Solution code:
A,B = map(int,input().split())
divA = []
divB = []

for i in range(2,int(A**0.5)+2):
    if A % i == 0:
        divA.append(i)
    while(A % i == 0):
        A = A//i
if A != 1:
    divA.append(A)

for i in range(2,int(B**0.5)+2):
    if B % i == 0:
        divB.append(i)
    while(B % i == 0):
        B = B//i
if B != 1:
    divB.append(B)

print(len(set(divA)&set(divB))+1)

Submission status: Accepted

Solution code:
A,B = map(int,input().split())
c = 1
t = int(max(A,B)**0.5)

for i in range(2,t+2):
    k = 0
    while(A % i == 0 and B % i == 0):
        k = 1
        A = A//i
        B = B//i
    c += k

for i in range(2,int(A**0.5)+2):
    while(A % i == 0):
        A = A//i

for i in range(2,int(B**0.5)+2):
    while(B % i == 0):
        B = B//i

if A == B and A > t:
    c += 1

print(c)

Submission status: Accepted

Solution code:
import fractions
A,B=map(int,input().split())
gcdlist=[]
pf={}
m=fractions.gcd(A,B)
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(pf)
keys=list(pf.keys())
val=list(pf.values())
ans=1
for i in range(len(keys)):
    gcdlist.append([keys[i],val[i]])
#print(gcdlist)
print(len(gcdlist)+1)

Submission status: Accepted

Solution code:
#nの素因数分解(O(n**0.5)
def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        while n%i == 0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass

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

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

print(len(set(prime_factor(gcd(a,b))))+1)

Submission status: Accepted

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

def primes(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=list(primes(a).keys())
B=list(primes(b).keys())
ans=1
for i in A:
    if i in B:
        ans+=1
print(ans)