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

n=list(map(int, input().split()))
a=fractions.gcd(n[0], n[1])
c = collections.Counter(prime_factorize(a))
b=list(c.keys())
d=len(b)+1
print(d)

Submission status: Accepted

Solution code:
import math
def euqlid(x,y):
    while x % y != 0:
        tmp = x % y
        x = y
        y = tmp
    return y
a, b = map(int, input().split())
if a < b:
    tmp = a
    a = b
    b = tmp
k = euqlid(a, b)
sum = 0
i = 2
if k == 1:
    print(1)
    exit()
while i <= math.sqrt(k):
    flag = False
    while k % i == 0:
        k = k // i
        flag = True
    if flag:
        sum += 1
    i += 1
if i <= k:
    sum += 1
print(sum + 1)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import chain


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


def fast_prime_set(n):
    # nまでの素数リスト高速版 setで返す
    # chainの読み込みが必要！
    if n < 4:
        return ({}, {}, {2}, {2, 3})[n]
    n_sqrt = int(n ** 0.5) + 1
    primes = {2, 3} | set(chain(range(5, n + 1, 6), range(7, n + 1, 6)))
    for i in range(5, n_sqrt, 2):
        if i in primes:
            primes.difference_update(range(i * i, n, i * 2))
    return primes


def prime_factorization(x):
    # 素因数分解
    # 事前に素数のセットが必要
    primes = fast_prime_set(10 ** 6)

    fact = defaultdict(int)
    for prime in primes:
        while x % prime == 0:
            fact[prime] += 1
            x //= prime
        if x == 1:
            break
        if x in primes:
            fact[x] += 1
            break
    if x!= 1:
        fact[x] = 1
    return fact


if __name__ == '__main__':
    a, b = map(int, input().split())
    gcd_a_b = gcd(a, b)
    prime_fact = prime_factorization(gcd_a_b)
    print(1 + len(prime_fact))

Submission status: Accepted

Solution code:
A,B=(map(int,input().split()))
import fractions
c=fractions.gcd(A,B)

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

Submission status: Accepted

Solution code:
a, b = list(map(int,input().split(' ')))
 
def gcd(x,y):
 
  while y!=0:
    x,y=y,x%y
  return x
 
gcd = 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:
  print(len(factorization(gcd)) + 1)

Submission status: Accepted

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

def devisors(value):
    if value == 1:
        return [1]
    devisors = []
    root = int(math.sqrt(value))
    for a in range(1, root+1):
        if a == root and a * a == value:
            devisors.append(root)
            continue
        if value % a == 0:
            devisors.append(a)
            devisors.append(value // a)
    return devisors

def prime_devisors(value):
    ret_devisors = []
    devs = devisors(value)
    for devisor in devs:
        prime_flag = True
        root = int(math.sqrt(devisor))
        for a in range(2, root + 1):
            if devisor % a == 0:
                prime_flag = False
                break
        if prime_flag and devisor != 1:
            ret_devisors.append(devisor)
    return ret_devisors


if __name__ == "__main__":
    val = gcd(a, b)
    primes = prime_devisors(val)
    if len(primes) == 0: #公約数が1しかない場合
        print(1)
    else:
        print(1 + len(primes))

Submission status: Accepted

Solution code:
a, b = map(int, input().split())
def gcd(p, q):
    if p < q:
        p, q = q, p
    while q > 0:
        p, q = q, p%q
    return p

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

divisors = make_divisors(gcd(a, b))
ans = []
while divisors:
    key = divisors[0]
    ans.append(key)
    divisors.remove(key)
    notans = []
    for value in divisors:
        if gcd(key, value) != 1:
            notans.append(value)
    for i in notans:
        divisors.remove(i)
            
print(len(ans))

Submission status: Accepted

Solution code:
from collections import defaultdict

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

def prime_factorization(n):
    '''
    Trial division.
    Input: 
        n : a positive integer
    Output:
        a dictionary of #(each prime factors) of n,
    '''
    result = defaultdict(int)
    if n < 2:
        return result
    while n % 2 == 0:
        result[2] += 1
        n //= 2
    p = 3
    while p*p <= n:
        while n % p == 0:
            n //= p
            result[p] += 1
        p += 2
    if n > 1:
        result[n] += 1
    return result

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

Submission status: Accepted

Solution code:
import math

line = input()
a, b = [int(item) for item in line.strip().split(' ')]
g = max(a, b)
m = min(a, b)
m_sqrt = int(math.sqrt(m)) + 1

# 小さい方の数字の約数を見つける
m_divisors = []
for i in range(1, m_sqrt):
    if m % i == 0:
        m_divisors.append(i)
        if not i ** 2 == m:
            m_divisors.append(m // i)
m_divisors = sorted(m_divisors)

# 2つの数の公約数を見つける
common_divisors = []
for i in m_divisors:
    if g % i == 0:
        common_divisors.append(i)

# 互いに素なものだけを残す
disjoint_common_divisors = []
for c in common_divisors:
    # 1と2個目の要素は無条件で加えてよい
    if c == 1:
        disjoint_common_divisors.append(1)
        continue
    if disjoint_common_divisors == [1]:
        disjoint_common_divisors.append(c)
        continue
    # それ以外は判定が必要
    flag = True
    for d in disjoint_common_divisors[1:]:
        if c % d == 0:
            flag = False
            break
    if flag:
        disjoint_common_divisors.append(c)

print(len(disjoint_common_divisors))

Submission status: Accepted

Solution code:
# start 21:14
a, b = [int(item) for item in input().split()]

# 素因数リスト
import math
def factor(num):
    divisor_list = [1]
    divisor = 2
    max_prime = int(math.sqrt(num))
    while max_prime >= divisor:
        if num % divisor == 0:
            divisor_list.append(divisor)
            num //= divisor

        else:
            divisor += 1
    divisor_list.append(num)
    return divisor_list

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

cd_list = set(factor(gcd(a, b)))

print(len(cd_list))

Submission status: Accepted

Solution code:
import fractions
import math

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

gcd = fractions.gcd(A, B)


ans = 1

max_N = int(math.sqrt(gcd))

for p in range(2, max_N+1):
    if gcd % p == 0:
        ans += 1
        gcd = gcd / p
        while gcd % p == 0:
            gcd = gcd / p
    if p > gcd:
        break
if gcd != 1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
def gcd(x, y):
    """
    ユークリッドの互除法を用いてxとyの最大公約数を求める。
    """
    while True:
        r = x % y
        if r == 0:
            break
        x = y
        y = r
    return y


def prime_factorize(x):
    """
    素因数分解
    """
    res = []
    while x % 2 == 0:
        res.append(2)
        x = x // 2
    p = 3
    while p * p <= x:#　このやり方だと複数出てくる。2,2,2など。だから最後にset
        while x % p == 0:
            res.append(p)
            x = x // p
        p += 2
    if x != 1:
        res.append(x)
    return res


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

Submission status: Accepted

Solution code:
import collections

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

# 素因数分解
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

n = gcd(a, b)
pf = factorization(n)
if pf == [[1, 1]]:
    print("{}".format(len(pf)))
else:
    print("{}".format(len(pf)+1))

Submission status: Accepted

Solution code:
def gcd(x, y):
    """
    ユークリッドの互除法を用いてxとyの最大公約数を求める。
    """
    while True:
        r = x%y
        if r == 0:
            break
        x = y
        y = r
    return y
    
def prime_factorize(x):
    """
    素因数分解
    """
    res = []
    while x%2 == 0:
        res.append(2)
        x = x//2
    p = 3
    while p*p <= x:
        while x%p == 0:
            res.append(p)
            x = x//p
        p += 2
    if x != 1:
        res.append(x)
    return res

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

Submission status: Accepted

Solution code:
def gcd(x, y):
    """
    ユークリッドの互除法を用いてxとyの最大公約数を求める。
    """
    while True:
        r = x%y
        if r == 0:
            break
        x = y
        y = r
    return y
    
def prime_factorize(x):
    """
    素因数分解
    """
    res = []
    while x%2 == 0:
        res.append(2)
        x = x//2
    p = 3
    while p*p <= x:
        while x%p == 0:
            res.append(p)
            x = x//p
        p += 2
    if x != 1:
        res.append(x)
    return res


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

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from fractions import gcd


def main():
  A,B = map(int, input().split())
  AB = gcd(A,B)
  divs = set([])
  for i in range(1,int(AB**0.5)+1):
    if AB % i == 0:
      divs.add(i)
      divs.add(AB//i)
  divs = sorted(list(divs))

  rets = set([])
  for d in divs[1:]:
    chk = True
    for r in rets:
      if d%r == 0:
        chk = False
        continue
    if chk:
      rets.add(d)
  return len(rets)+1

if __name__ == "__main__":
  ret = main()
  print(ret)

Submission status: Accepted

Solution code:
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 common_divisors(k,j):
  c = make_divisors(k) + make_divisors(j)
  return [x for x in set(c) if c.count(x) > 1]

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

aa=factorize(a)
bb=factorize(b)
l = list(set(aa))+list(set(bb))
ll = [x for x in set(l) if l.count(x) > 1]

print(len(ll)+1)

Submission status: Accepted

Solution code:
#D
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 set(a)
print(len(prime_factorize(A) & prime_factorize(B)) + 1)

Submission status: Accepted

Solution code:
def primes(n):
    res = [1]
    a = 2
    while n > 1 and a < (10**6):
        if n % a == 0:
            res.append(a)
            while n % a == 0:
                n //= a
        a += 1
    if a == 10**6:
        res.append(n)
    return set(res)


if __name__ == '__main__':
    a, b = map(int, input().split(' '))
    print(len(primes(a) & primes(b)))

Submission status: Accepted

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

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

#List of divisors

def divisor(n):
    i = 1
    num = []
    while i * i <= n:
        if n%i == 0:
            num.append(i)
            num.append(n//i)
        i += 1
    num = list(set(num))
    return num


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

n = gcd(A, B)
x = divisor(n)
count = 0
for i in x:
    prim_list = factrization(i)
    if len(prim_list) == 1:
        count += 1
print(count)

Submission status: Accepted

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

c=fractions.gcd(A,B)

Cnt=[]

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

Cnt=prime_decomposition(c)
Cnt=list(Cnt)
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

ans=1


for i in range(0,len(Cnt)):
    if is_prime(int(Cnt[i])):
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


def LI(): return list(map(int, input().split()))


def LF(): return list(map(float, input().split()))


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(list, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


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


def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]


mod = 1000000007
inf = float('INF')


def A():
    a = II()
    b = a//2
    p = b/a
    if a % 2:
        print(1-p)
    else:
        print(p)

    return

# B


def B():
    N, K = map(int, input().split())
    h = LI()
    count = 0

    for i in h:
        if i >= K:
            count += 1
        else:
            continue
    print(count)
    return

# C


def C():
    N = II()
    A = LI()
    J = [0] * N
    for i, n in enumerate(A):
        J[n-1] = i+1
    for s in J:
        print(s, end=" ")

    return

# D


def D():
    A, B = map(int, input().split())
    g = gcd(A, B)
    # go = g
    # myset = set([1])
    sq = int(sqrt(g)) + 3
    ans = 1

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

            # myset.add(i)
        if g == 1:
            break
        if i == sq - 1:
            # myset.add(go)
            ans += 1

    print(ans)

    return

# E


def E():
    N, M = LI()
    bit_max = 1 << N
    dp = [[inf for i in range(bit_max)] for j in range(M+1)]
    dp[0][0] = 0

    for i in range(M):
        a, b = LI()

        c = LI()
        bit = 0

        for d in c:
            bit += 1 << (d-1)

        for w in range(bit_max):

            t = w | bit
            cost = dp[i][w] + a

            dp[i+1][t] = min(dp[i+1][t], cost)

            dp[i+1][w] = min(dp[i][w], dp[i+1][w])

    print(-1) if dp[-1][-1] == inf else print(dp[-1][-1])

    return

# F


def F():
    S = input()
    print(solution(S))

    # you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")


def solution(S):
    # write your code in Python 3.6
    import math

    vowels = "AIUEO"
    count = 0
    consonants = 0
    newC = []
    newV = []

    for i in S[:-1]:
        if i in vowels:
            count += 1
            newV.append(i)
        else:
            consonants += 1
            newC.append(i)

    if consonants < count or consonants - 2 > count:
        return 0

    a = math.factorial(len(set(newC))) * math.factorial(len(set(newV)))
    return a

    pass


# Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import math


A, B = list(map(int, input().split()))
# A, B = [12, 18]
# A, B = [420, 660]
# A, B = [1, 2019]


# 1. A,B の gcd を取得して C とする
# 2. C を素因数分解する
# 3. 「素因数分解の数 + 1」を返す

def gcd(a, b):
    # a の方が大きいと仮定
    def _gcd(a, b):
        # print(a, b)
        if a % b == 0:
            return b
        else:
            return gcd(b, a % b)

    if a < b:
        return _gcd(b, a)
    else:
        return _gcd(a, b)


def factorize(x):
    res = {}
    for i in range(2, int(math.sqrt(x) + 1)):  # x まで行かずともよさそう
        if x % i == 0:
            while x % i == 0:
                x //= i
                res[i] = res.get(i, 0) + 1

    if x != 1:
        res[x] = 1

    return res

C = gcd(A, B)
factors = factorize(C)
print(len(factors) + 1)

Submission status: Accepted

Solution code:
import collections

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)
    
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 = list(map(int,(input().split())))
d = gcd(a, b)
c = collections.Counter(prime_factorize(d))
print(len(c)+1)

Submission status: Accepted

Solution code:
#%%
a = input()
#b = "2 3 1"
#%%
A = [int(x) for x in a.split()]

import math

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

import fractions
gcb = fractions.gcd(A[0], A[1])  # 最大公約数

#%%
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

so_gcb = prime_factorize(gcb)


#%%
new_num = []
for num in so_gcb:
    if num not in new_num:
        new_num.append(num)

print(len(new_num))

Submission status: Accepted

Solution code:
def gcd(m, n):
    while n:
        m, n = n, m % n
    return m


def prime_factorize(n):
    b = 2
    fct = []
    while n >= b ** 2:
        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())

print(len(set(prime_factorize(gcd(A, B)))) + 1)

Submission status: Accepted

Solution code:
import fractions
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())
GCD = fractions.gcd(A,B)
pf = prime_factorize(GCD)
print(len(set(pf))+1)

Submission status: Accepted

Solution code:
import array


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


a, b = map(int, input().split())
c = gcd(a, b)
if c != 1:
    prime = array.array('b', [1] * (10 ** 6 + 1))
    index = 2
    while index * index <= 10 ** 6:
        if prime[index] == 1:
            for i in range(index * index, 10 ** 6 + 1, index):
                prime[i] = 0
        index += 1
    prime_list = []
    for i in range(2, 10 ** 6 + 1):
        if prime[i]:
            prime_list.append(i)
    index = 0
    count = 1
    while index < len(prime_list) and c != 1:
        if c % prime_list[index] == 0:
            count += 1
            while c % prime_list[index] == 0:
                c = c // prime_list[index]
        index += 1
    if c != 1:
        count += 1
    print(count)
else:
    print(1)

Submission status: Accepted

Solution code:
a,b=[int(x) for x in input().split()]
i=1
def gcd(a,b):
  a,b=max(a,b),min(a,b)
  if a%b==0:
    return b
  else:
    return gcd(b,a%b)
g=gcd(a,b)
l=[]
while(i*i<=g):
    if g%i==0 and i*i!=g:
        l.append(i)
        l.append(g//i)
    if i*i==g:
        l.append(i)
    i=i+1
l=sorted(l)
i=1
while(i<len(l)):
    if l[i]!=0:
        j=i+1
        while(j<len(l)):
            if l[j]%l[i]==0:
                l[j] = 0
            j=j+1
    i=i+1
l=list(filter ( lambda x:x!=0,l))
print(len(l))

Submission status: Accepted

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


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


cnt = list(set(prime_factorize(a)) & set(prime_factorize(b)))
print(len(cnt)+1)

Submission status: Accepted

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

Submission status: Accepted

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

# 最大公約数
def gcd(x, y):
    while y != 0:
        x, y = y, x % y
    return x

GCD = gcd(A, B)

# 最大公約数の素因数を求める
prime_factor = []

# 素因数で可能な限り割る
def divide_by_prime_factor(GCD, p):
    if GCD%p == 0:
        prime_factor.append(p)
        while GCD%p == 0:
            GCD /= p
    return GCD, prime_factor

GCD, prime_factor = divide_by_prime_factor(GCD, 2)

for i in range(3, int(GCD**0.5)+1, 2):
    GCD, prime_factor = divide_by_prime_factor(GCD, i)

# GCDそれ自身が素数の場合を考慮。GCD==1の場合を除くことに注意
if GCD > 2:
    GCD, prime_factor = divide_by_prime_factor(GCD, GCD)

# 素因数の数+1を出力
print(len(prime_factor)+1)

Submission status: Accepted

Solution code:
A, B = map(int, input().split())
max_num = 10**12
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

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

r = gcd(A, B)
ans = len(set(prime_factorize(r)))+1
print(ans)

Submission status: Accepted

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

a,b=map(int,input().split())
c=gcd(a,b)
ans=1
cnt=2
while(cnt*cnt<=c):
	bo=False
	while(c%cnt==0):
		if not bo:
			ans+=1
			bo=True
		c//=cnt
	cnt+=1
if c!=1:
	ans+=1

print(ans)

Submission status: Accepted

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

a,b=map(int,input().split())
c=gcd(a,b)
ans=1
cnt=2
while(cnt*cnt<c):
	bo=False
	while(c%cnt==0):
		if not bo:
			ans+=1
			bo=True
		c//=cnt
	cnt+=1
if c!=1:
	ans+=1
	
print(ans)

Submission status: Accepted

Solution code:
import math
def gcd(a, b):
  while b > 0:
    a, b = b, a % b
  return a
def div(a):
  r = []
  i = 2
  k = int(math.sqrt(a))
  while i <= k:
    if a % i == 0:
      r.append(i)
      while a % i == 0:
        a //= i
      k = math.sqrt(a)
    i += 1
  if a > 1:
    r.append(a)
  return r

a, b = map(int, input().split())
if a > b:
  a, b = b, a
c = gcd(a,b)
print(len(div(c))+1)

Submission status: Accepted

Solution code:
from math import sqrt
def get_divisor(num):
	arr = [i for i in range(1,int(sqrt(num))+1) if num % i == 0]
	arr += [num // i for i in reversed(arr) if num // i not in arr]
	return arr

def get_common(num1, num2):
	list_a = get_divisor(num1)
	list_b = get_divisor(num2)
	return [i for i in list_a if i in list_b]

def prime_ch(num):
	if num == 1:
		return False
	for i in list(range(2,int(sqrt(num))+1)):
		if num % i == 0:
			return False
	return True


A,B = list(map(int,input().split()))[:2]
common = get_common(A,B)
c_prime = [p for p in common if prime_ch(p)]
print((len(c_prime)+1))

Submission status: Accepted

Solution code:
import fractions
import math

def devide_num(num, p):
    if num % p == 0:
        return devide_num(num//p, p)
    else:
        return num

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

ab_gcd = fractions.gcd(a, b)

max_num =  math.ceil(math.sqrt(ab_gcd))
ans_list = []

for i in range(max_num):
    val = i+1
    if val == 1:
        ans_list.append(val)
    else:
        if ab_gcd % val == 0:
            ans_list.append(val)
            ab_gcd = devide_num(ab_gcd, val)
            
    if ab_gcd == 1:
        break
     
if ab_gcd != 1:
    ans_list.append(ab_gcd)

print(len(ans_list))

Submission status: Accepted

Solution code:
from fractions import gcd

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

m = gcd(A, B)
pf = []
for i in range(2, m+1):
    if i ** 2 > m:
        break
    if m % i == 0:
        pf.append(i)
    while m % i == 0:
        m //= i
if m != 1:
    pf.append(m)
    
print(len(pf) + 1)

Submission status: Accepted

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

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

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

while b:
    a, b = b, a % b

print(len(set(factorize(a)))+1)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

while b:
    a, b = b, a%b
ar = prime_factorize(a)
print(len(ar))

Submission status: Accepted

Solution code:

a,b = map(int,input().split())
def gcd(x,y):
    if y == 0:
        return x
    else:
        return gcd(y,x%y)
def waru(max_gcd,x):
    if max_gcd%x != 0:
        return max_gcd
    else:
        return waru(max_gcd//i,x)

count = 0
max_gcd = gcd(a,b)

for i in range(2,max_gcd+1):
    if i*i > max_gcd:
        break
    if max_gcd%i == 0:
        count += 1
        max_gcd = waru(max_gcd,i)
if max_gcd == 1:
    print(count+1)
else:
    print(count+2)

Submission status: Accepted

Solution code:
import math
A, B = map(int, input().split())
numlist = []
def gcd(x, y):
    while y != 0:
        x, y = y, x%y

    return x

num = gcd(A, B)
numcpy = num
flag2 = 0
while(1):
    flag = 1
    for i in range(2, int(math.sqrt(num)) + 2):
        #print(i, numcpy, math.sqrt(num))
        if numcpy % i == 0:
            numcpy = numcpy // i
            flag = 0
            if i not in numlist:
                numlist.append(i)
            break
    if flag == 1:
        break

if numcpy != 1:
    flag2 = 1


print(len(numlist) + 1 + flag2)

Submission status: Accepted

Solution code:
import copy
import heapq
import math
import fractions

def j(n):
    if n:print("Yes")
    else:print("No")
    exit(0)
rem = 10 ** 9 + 7

"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def ipmultiplerow(n):
    a = []
    for i in range(n):
        a.append(ip())
    return a
def printrow(a):
    for i in a:
        print(i)

n,m = ips()
mv = fractions.gcd(n,m)
l = []
for i in range(1,int(math.sqrt(mv))+1):
    if mv%i==0:
        l.append(i)
        l.append(mv//i)
#print(l)
l.sort()
p = set(l)
l = copy.copy(list(p))
s = []
for target in l:
    flag = 1
    for i in range(2,int(math.sqrt(target))+1):
        #print(target,i,target%i)
        if target%i==0:
            flag = 0
            break
    if flag:s.append(target)
print(len(s))

Submission status: Accepted

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

def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0: # i で割り切れればiは素因数
            n /= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table


s = set(prime_decomposition(a))
t = set(prime_decomposition(b))
print(len(s&t) + 1)