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 math
import fractions

A, B = map(int,input().split())
gcd = fractions.gcd(A,B)
N = int(math.ceil(math.sqrt(gcd)))
cd = []

for i in range(1,N):
    if A%i==0 and B%i==0:
        cd.append(i)
        cd.append(gcd//i)
if N==1:
    cd.append(N)

ans=0
cd.sort()


for i in range(len(cd)):
    tr=1
    for j in range(1,i):
        if cd[i]%cd[j]==0:
            tr=0
            break
    if tr==1:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from math import sqrt
a,b = map(int, input().split())
xa,xb = a,b

sa = set([1])
i = 2
while a>1:
    if i>sqrt(xa):
        sa.add(a)
        break
    while a%i==0:
        sa.add(i)
        a //= i
    i += 1

sb = set([1])
i = 2
while b>1:
    if i>sqrt(xb):
        sb.add(b)
        break
    while b%i==0:
        sb.add(i)
        b //= i
    i += 1

print(len(sa & sb))

Submission status: Accepted

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

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

#[[素因数,数]]を出力
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.append([i,c])
            c=0
    if n!=1:
        f.append([n,1])
    return f

g = gcd(A,B)

print(len(fctr1(g))+1)

Submission status: Accepted

Solution code:
def is_prime(n):
    assert n >= 1,  'Argument Error! n is "1 <= n".'
    for i in range(2, n + 1):
        if i ** 2 > n:
            break
        if n % i == 0:
            return False
    return n != 1

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

a, b = sorted(list(map(int, input().split())))
divisors_ = set(divisors(a)) & set(divisors(b))

prime_divisors = [x for x in divisors_ if is_prime(x)]
print(len(prime_divisors) + 1)

Submission status: Accepted

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

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

print(len(prime_factorize(gc)) + 1)

Submission status: Accepted

Solution code:
def gcd(x, y):
    a, b = x, y
    r = a % b
    while r != 0:
        a, b = b, r
        r = a % b
    return b

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

def isprime(x):
    t = 1
    for i in range(2, int(x**0.5) + 1):
        if x % i == 0:
            t = 0
            break
    if t == 1 and x != 1:
        return True
    else:
        return False


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

CD = divisors(gcd(a, b))

ans = 1
for cd in CD:
    if isprime(cd):
        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 = [int(_) for _ in input().split()]
a_l = list(set(prime_factorize(a)))
b_l = list(set(prime_factorize(b)))
ans_l = []
for n in a_l:
    if n in b_l:
        ans_l.append(n)

print(len(ans_l) + 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())

s1 = set(prime_factorize(a))
s2 = set(prime_factorize(b))

ans = len(s1 & s2) + 1
print(ans)

Submission status: Accepted

Solution code:
def prime_factorize(N): 
    exponent = 0
    while N%2 == 0:
        exponent += 1
        N //= 2
    if exponent: factorization = [[2,exponent]]
    else: factorization = []
    i=1
    while i*i <=N:
        i += 2
        if N%i: continue
        exponent = 0
        while N%i == 0:
            exponent += 1
            N //= i
        factorization.append([i,exponent])
    if N!= 1: factorization.append([N,1])
    assert N != 0, "zero"
    return factorization

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

A=list(set(prime_decomposition(a)))
B=list(set(prime_decomposition(b)))


ans=0
for i in A:
    if i in B:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y
def primes(n):
    P=[2]
    for L in range(3, n):
        isP = True
        for L2 in P: isP = isP and L%L2
        if isP: P.append(L)
    return P

A,B=LI()
gd = gcd(A,B)
if gd == 1:
    print(1)
    exit()

# print("gcd: {}".format(gd))
cands = []
prs = []

for i in range(2, math.ceil(math.sqrt(gd))+1):
    if gd%i == 0:
        cands.append(i)
        cands.append(gd//i)

cands.sort()
cands.append(gd)

for i in range(0, len(cands)):
    ok = True
    for prime in prs:
        if cands[i]%prime == 0:
            ok = False
            break
    if ok:
        prs.append(cands[i])

# print(prs)
print(len(prs)+ 1)

Submission status: Accepted

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


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

    divisors.sort()
    return divisors


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


ans = 1
divs = make_divisors(fractions.gcd(a, b))
for num in divs:
    if is_prime(num):
        ans += 1
print(ans)

Submission status: Accepted

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

ans = 1
for i in range(2, int(min(a, b)**0.5)+1):
    if a%i == 0 and b%i == 0:
        ans += 1
    while a%i==0:
        a //= i
    while b%i==0:
        b //= i

if (a==b) and (a!=1):
    ans += 1
print(ans)

Submission status: Accepted

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


A, B = map(int, input().split())
As = set(prime_decomp(A))
Bs = set(prime_decomp(B))
cnt = 1
for a in As:
    if a in Bs:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
ans=1
for i in range(2,int(min(a,b)**0.5)+1):
  if a%i==0 and b%i==0:
    ans+=1
  while a%i==0:
    a//=i
  while b%i==0:
    b//=i
if a!=1 and b!=1 and (a%b==0 or b%a==0):
  ans+=1
print(ans)

Submission status: Accepted

Solution code:
A, B = map(int, input().split())
ans = 1
for i in range(2, 1+int(min(A**.5, B**.5))):
    if A % i == 0 and B % i == 0:
        ans += 1
    while A % i == 0:
        A //= i
    while B % i == 0:
        B //= i
if A != 1 and B != 1 and (A % B == 0 or B % A == 0):
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    from fractions import gcd
    from collections import Counter
    a,b=map(int,input().split())
    c=len(Counter(soinsuu(gcd(a,b))))+1
    print(c)
    
def soinsuu(a):
    yy,j=[],2
    y=yy.append
    while(a>1):
        for i in range(j,int(a**0.5)+1):
            if a%i==0:
                y(i)
                a,j=a//i,i
                break
        else:
            y(a)
            break
    yy.sort()
    return yy
    
if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import fractions
import math

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

g = fractions.gcd(a,b)
ans = 0
sqrtg = math.ceil(math.sqrt(g))
for i in range(2,sqrtg):
    #割り切れるなら割り切れなくなるまでiで割り続ける
    if (g%i == 0):
        ans += 1
        while (g % i == 0):
            g //= i
            
if (g != 1):
    ans += 1
print(ans+1)

Submission status: Accepted

Solution code:
import collections
import math
import operator as op
from functools import reduce

import numpy as np
import math
import bisect


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 = list(map(int, input().split()))

    # common_divisors = []
    # if A > B:
    #     A, B = B, A
    # for i in range(1, int(A**0.5)+1):
    #     if A % i == 0 and B % i == 0:
    #         common_divisors.append(i)
    #         j = A // i
    #         if j != i and B % j == 0:
    #             common_divisors.append(j)
    # common_divisors
    # print(common_divisors)

    fact_A = {i: cnt for i, cnt in factorization(A)}
    fact_B = {i: cnt for i, cnt in factorization(B)}
    fact_A.update({1:1})
    fact_B.update({1:1})

    ans = 0
    for k in fact_A.keys():
        if k in fact_B:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()

def prime_factorization(n):
    assert(n>1)
    factor=[]
    for d in range(2,int(n**.5)+1):
        while(n%d==0):
            n//=d
            factor.append(d)
    if n!=1: factor.append(n)
    return factor

from fractions import gcd
def resolve():
    a,b=map(int,input().split())
    g=gcd(a,b)

    if(g==1):
        print(1)
        return

    S=set(prime_factorization(g))
    print(len(S)+1)
resolve()

Submission status: Accepted

Solution code:
import fractions
import math
import itertools
A,B=map(int,input().split())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def combinations_count(n, r):
   return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
  
def prime_factorize(n):
    a = {}
    while n % 2 == 0:
        a[2]=1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a[f]=1
            n //= f
        else:
            f += 2
    if n != 1:
        a[n]=1
    return a
  
C=fractions.gcd(A,B)
d_C=prime_factorize(C)
print(len(d_C)+1)

Submission status: Accepted

Solution code:
import math
from fractions import gcd

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

def pf(x):
  x2=x
  y = int(math.sqrt(x))+1
  l=[1]
  if x%2==0:
    l.append(2)
    while x%2==0:
      x=x//2
  for i in range(3,y,2):
    if x%i==0:
      l.append(i)
    while x%i==0:
      x=x//i
    if x==1:
      break
  if x>=y:
    if x!=1:
      l.append(x)
  return(l)

count=0
n=gcd(a,b)

l=pf(n)

len=len(l)
for i in range(len):
  if  a%l[i]==0:
        count+=1
print(count)

Submission status: Accepted

Solution code:
#方針...gcd(A,B)の約数の中で素数or1となるものの個数を調べれば良い(O(route N))
import fractions
import math

def prime_fac(N):
    primes = {1:1}
    n = int(math.sqrt(N))
    for i in range(2,n+1):
        if N%i==0:
            primes[i] = 0
            while N%i==0:
                primes[i] += 1
                N = N//i
    if (N!=1):
        primes[N] = 1
    return primes

A,B = list(map(int,input().split()))
C = fractions.gcd(A,B)
primes = prime_fac(C)

print(len(primes))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect, string
from fractions import gcd
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf')
mod = 10**9+7
ans = 0 ;count = 0 ;pro = 1

a,b=map(int,input().split())
g=gcd(a,b)
def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        count=0
        while n % i==0:
            count+=1
            n = n//i
        if count!=0:
            ass.append((i,count))
    if n != 1:
        ass.append((n,1))
    return ass

pr = prime_factor(g)
print(len(pr)+1)
# print(pr)

Submission status: Accepted

Solution code:
from collections import Counter


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

AP = Counter(prime_factorize(A))
BP = Counter(prime_factorize(B))
comm = AP + BP - (AP - BP) - (BP - AP)

for key in comm.keys():
    comm[key] //= 2

print(len(list(comm.keys())) + 1)

Submission status: Accepted

Solution code:
import math
def gcd(a,b):
    while a > 0 and b > 0:
        if a > b:
            a = a % b
        elif a < b:
            b = b % a
        else:
            b = 0
    return max(a,b)

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

def trial(k):
    factor = []
    m = int(math.sqrt(k)) + 1
    for i in range(2,m):
        while k % i == 0:
            k = k // i
            factor.append(i)
    if not factor:
        return [1,k]
    else:
        factor.append(k)
        factor.append(1)
        return factor

k = gcd(a,b)

ps = trial(k)

count = 1
for i in range(len(ps)-1):
    if ps[i] != ps[i + 1]:
        count += 1

print(count)

Submission status: Accepted

Solution code:
import collections


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


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


def main():
    a, b = map(int, input().split())
    gcd_num = gcd(a, b)
    c = collections.Counter(prime_factorize(gcd_num))
    # print(prime_factorize(gcd_num))
    # cには１が含まれていないので、その分カウントを増やす
    print(len(c) + 1)


if __name__ == '__main__':
    main()

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

A,B = map(int,input().split())
import fractions
gcd = fractions.gcd(A,B)
ans = 1 + len(factorization(gcd))
if factorization(gcd)[0][0] == 1:
    ans -= 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
from itertools import combinations
from collections import defaultdict

# from math import gcd
import fractions

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

def make_prime_list(num):
    if num < 2:
        return []

    # 0のものは素数じゃないとする
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0 # 1は素数ではない
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]

def prime_factorization(num):
    if num <= 1:
        return False
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list(num_sqrt)

        dict_counter = defaultdict(int)
        for prime in prime_list:
            while num % prime == 0:
                dict_counter[prime] += 1
                num //= prime
        if num != 1:
            dict_counter[num] += 1

        dict_counter = dict(dict_counter)

        return dict_counter

if A >= B:
    A, B = B, A

# # 小さい方の約数リストを計算
# divA = []
# for i in range(1, A // 2 + 1):
#     if A % i == 0:
#         divA.append(i)
# divA.append(A)
# div = [n for n in divA if B % n == 0]
# Ndiv = len(div)

# print(div)
# for n in div:
#     for m in div:
#         if n < m and fractions.gcd(n, m) == 1:
#             print(n, m)

# 深さ優先探索
# def dfs(i, S, d):
#     selected = div[i]
#     S.add(selected)
#     depth = d
#     for j in range(i + 1, Ndiv):
#         if fractions.gcd(div[i], div[j]) == 1:
#             flag = True
#             for k in S:
#                 if fractions.gcd(k, div[j]) != 1:
#                     flag = False
#                     break
#             if flag:
#                 dj = dfs(j, S, d + 1)
#                 depth = max(depth, dj)
#     return depth

# ans = dfs(0, set({}), 1)
# print(Ndiv + 1)

lA = prime_factorization(A)
lB = prime_factorization(B)

if not lA or not lB:
    print(1)
    exit()

count = 0
for key in lA:
    if key in lB:
        count += 1
print(count + 1)

Submission status: Accepted

Solution code:
#最大公約数を求めたあとに
#素因数分解？して、素因数の種類？
p,q=map(int,input().split())

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

def soin(n):
    ans={1:1}
    for i in range(2,int(pow(n,1/2))+1):
        while n%i==0:
            ans[i]=ans.get(i,0)+1
            n//=i
    if n>1:
        ans[n]=1
    return(ans)
  
r=gcd(p,q)
print(len(soin(r)))

Submission status: Accepted

Solution code:
from fractions import gcd

A, B = map(int, input().split())
C = gcd(A, B)
ans = 1
i = 2
for i in range(2, int(-(-C**0.5//1))+1):
    if C % i == 0:
        ans += 1
        while C % i == 0:
            C //= i
    i += 1
if C != 1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
#AとBの最大公約数を素因数分解してから考える。
from fractions import gcd
a,b = map(int,input().split())
g = gcd(a,b)
#gを素因数分解し、素因数のセットを作る。
s = set([1])
for i in range(2,int(-(-g**0.5//1)+1)):
  flag = True
  while flag:
    if g%i==0:
      s.add(i)
      g=g//i
    else:
      flag = False
s.add(g)
print(len(s))

Submission status: Accepted

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

def num_prime_factor(n):
    
    if n == 1: return 1
    
    ret = 1
    cursor = 2
    if n % cursor == 0: 
        ret += 1
    while n % cursor == 0: 
        n = n // cursor
    
    cursor = 3
    while cursor**2 <= n:
        if n == 1: 
            return ret
        if n % cursor == 0: 
            ret += 1
        while n % cursor == 0: 
            n = n // cursor
        cursor += 2

    if n != 1: 
        ret += 1
        
    return ret

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def num_prime_factor(n):
    
    if n == 1: return 1
    
    ret = 1
    cursor = 2
    if n % cursor == 0: ret += 1
    while n % cursor == 0: n = n // cursor
    
    cursor = 3
    while cursor**2 <= n:
        if n == 1: return ret
        if n % cursor == 0: ret += 1
        while n % cursor == 0: n = n // cursor
        cursor += 2

    if n != 1: ret += 1
        
    return ret

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import fractions


def main():
    A, B = map(int, input().split())
    n = fractions.gcd(A, B)
    print(num_prime_factor(n))

def num_prime_factor(n):
    
    if n == 1: return 1
    
    ret = 1
    cursor = 2
    if n % cursor == 0: ret += 1
    while n % cursor == 0: n = n // cursor
    
    cursor = 3
    while cursor**2 <= n:
        if n == 1: return ret
        if n % cursor == 0: ret += 1
        while n % cursor == 0: n = n // cursor
        cursor += 2

    if n != 1: ret += 1
        
    return ret

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import fractions


def main():
    A, B = map(int, input().split())
    n = fractions.gcd(A, B)
    print(num_prime_factor(n))

def num_prime_factor(n):
    
    if n == 1:
        return 1
    
    ret = 1
    cursor = 2
    if n % cursor == 0:
        ret += 1
        n = n // cursor
        while n % cursor == 0:
            n = n // cursor
    
    cursor = 3
    while cursor**2 <= n:
        if n == 1:
            break
        if n % cursor == 0:
            ret += 1
            while n % cursor == 0:
                n = n // cursor
        cursor += 2

    if n != 1:
        ret += 1
        
    return ret

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math, fractions


def main():
    A, B = map(int, input().split())
    n = fractions.gcd(A, B)
    print(num_prime_factor(n))

def num_prime_factor(n):
    
    ret = 0

    for i in range(1, int(math.sqrt(n)) + 2):

        composite = False

        if n % i == 0:
            ret += 1
            n = n / i

            if i != 1:
                while n % i == 0:
                    n = n / i

            if n == 1:
                break

            for j in range(2, int(math.sqrt(n)) + 2):
                if n % j == 0:
                    composite = True
                    break

            if not composite:
                ret += 1
                break

    return ret

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math, fractions


def num_prime_factor(n):
    
    ret = 0
    
    for i in range(1, 3):

        composite = False

        if n % i == 0:
            ret += 1
            n = n / i

            if i != 1:
                while n % i == 0:
                    n = n / i

            if n == 1:
                break

            for j in range(2, int(math.sqrt(n)) + 2):
                if n % j == 0:
                    composite = True
                    break

            if not composite:
                ret += 1
                break
    
    for i in range(3, int(math.sqrt(n)) + 2, 2):
        
        composite = False

        if n % i == 0:
            ret += 1
            n = n / i

            if i != 1:
                while n % i == 0:
                    n = n / i

            if n == 1:
                break

            for j in range(2, int(math.sqrt(n)) + 2):
                if n % j == 0:
                    composite = True
                    break

            if not composite:
                ret += 1
                break
                
    return ret

if __name__ == "__main__":
    A, B = map(int, input().split())
    n = fractions.gcd(A, B)
    if n == 1:
        print(1)
    else:
        print(num_prime_factor(n))

Submission status: Accepted

Solution code:
import math, fractions


def num_prime_factor(n):
    
    ret = 0

    for i in range(1, int(math.sqrt(n)) + 2):

        composite = False

        if n % i == 0:
            ret += 1
            n = n / i

            if i != 1:
                while n % i == 0:
                    n = n / i

            if n == 1:
                break

            for j in range(2, int(math.sqrt(n)) + 2):
                if n % j == 0:
                    composite = True
                    break

            if not composite:
                ret += 1
                break

    return ret

if __name__ == "__main__":
    A, B = map(int, input().split())
    n = fractions.gcd(A, B)
    print(num_prime_factor(n))

Submission status: Accepted

Solution code:
import fractions

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

def make_divisors(n):
    count = 0
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            # print(i)
            flag = 1
            for j in range(2, int(i**0.5)+1):
                if i%j == 0:
                    flag = 0
                    break
            if flag == 1:
                count += 1
            if i != n // i:
                flag = 1
                for j in range(2, int((n // i)**0.5)+1):
                    if (n // i) %j == 0:
                        flag = 0
                        break
                if flag == 1:
                    count += 1
    return count

print(make_divisors(g))

Submission status: Accepted

Solution code:
from fractions import gcd
A, B = map(int, input().split())
M = gcd(A, B)
primes = {}
i = 2
while(M >= i ** 2):
  if(M % i == 0):
    primes[i] = primes.get(i, 0) + 1
    M //= i
  else:
    i += 2 - (i + 1) % 2
if M > 1: primes[M] = 1

print(len(primes) + 1)

Submission status: Accepted

Solution code:
# なんとなく薄目でみていると素因数分解したやつの底の共通するうちから2つ選ぶのが浮かんでくる
# と思ったけど共通するやつの数でいいのか？サンプルケース2おかしないか
# 素因数分解の方法が間違っていた

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


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


def f(x):
    ret = []
    i = 1
    while i * i <= x:
        if x % i == 0:
            if ff(i):
                ret.append(i)
            # 最初と最後が重複しないか確認
            if i != 1 and i * i != x:
                if ff(x // i):
                    ret.append(x // i)
        i += 1
    if ff(x):
        ret.append(x)
    return set(ret)


a_lis, b_lis = f(a), f(b)
common_lis = a_lis & b_lis
print(len(common_lis))

Submission status: Accepted

Solution code:
# ABC 142 D - Disjoint Set of Common Divisors
def divisor(n): 
    """
    xの約数を列挙する。

    Parameters
    ----------
    x: int
        約数を求めたい自然数

    Returns
    -------
    retlist：list
        約数のリスト

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

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

a,b = map(int,input().split())
A =[]
B =[]
C =[]
AB = []
ans = 0
A = divisor(a)
B = divisor(b)
for aa in A:
    if aa in B:
        AB.append(aa)

for ab in AB:
    if isPrime(ab):
        ans+=1
        C.append(ab)

print(ans)

Submission status: Accepted

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

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

def prime_decomposition(n):
  i = 2
  c = 0
  while i * i <= n:
      flag=0
      while n % i == 0:
          n /= i
          if flag==0:
              c+=1
              flag=1
      i += 1
  if n > 1:
    c+=1
  return c

GCD=gcd(A,B)
print(prime_decomposition(GCD)+1)

Submission status: Accepted

Solution code:
import math

a, b = map(int, input().split())
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)
ab_gcd = gcd(a, b)

gcd_sq = int(math.sqrt(ab_gcd) + 1)

ans = []
curr_num = ab_gcd
for i in range(2, gcd_sq):
    if curr_num % i != 0:
        continue
    cnt = 0
    while curr_num % i == 0:
        curr_num = curr_num // i
        cnt += 1
    ans.append([i, cnt])
if curr_num != 1:
    ans.append([curr_num, 1])
print(len(ans) + 1)

Submission status: Accepted

Solution code:

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

#素数列挙
def searchPrimeNum(N):
    max = int(N**0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum



#素因数分解(素数列挙が必要)
def pfact(N):
    plis = searchPrimeNum(int(N**0.5+1))
    ans = 1
    for p in plis:
        if N%p == 0:
            ans += 1
            N = N//p
        while N%p == 0:
            N = N//p
        if N == 1:
            break
    if N != 1:
        ans += 1
    return ans

#互除法(最大公約数)
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)

print(pfact(gcd(A,B)))

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

[A,B] = inpl()

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

ans_dq = deque([1])

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

ans = len(ans_dq)
print(ans)