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:
# -*- coding utf-8 -*-

MOD = 10 ** 9 + 7

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


def trial_division(n):
    ret = []
    for p in range(2, int(n**0.5) + 1):
        c = 0
        while n % p == 0:
            n //= p
            c += 1
        if c != 0:
            # ret.append([p, c])
            ret.append(p)

    if n > 1:
        # ret.append([n, 1])
        ret.append(n)

    return set(ret)


pa = trial_division(a)
pb = trial_division(b)
p = pa & pb

ans = len(p) + 1

print(ans)

Submission status: Accepted

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

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

G = gcd(A, B)

ans = 1
d = 2
while d * d <= G:
  if G % d == 0:
    ans += 1
    while G % d == 0:
      G = (G // d)
  d += 1
if G > 1:
  ans += 1
print(ans)

Submission status: Accepted

Solution code:
import fractions

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

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

G = fractions.gcd(A,B)

F = prime_factorize(G)

print(len(F) + 1)

Submission status: Accepted

Solution code:
def main():
  import fractions
  import math

  a,b = map(int,input().split())
  g = fractions.gcd(a,b)
  
  d = [1]
  num = 2

  while num**2 <= g:
    #print("num",num)
    if g%num == 0:
      d.append(num)
    while g%num == 0 and g>1:
      g = g//num
      #print(g)
    num += 1
  
  print(len(d) + (g > 1))

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
A,B=map(int,input().split())
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
print(len(set(prime_factorize(A))&set(prime_factorize(B)))+1)

Submission status: Accepted

Solution code:
from fractions import gcd

if __name__ == '__main__':
    n = gcd(*map(int, input().split()))
    a = i = 1
    while i * i < n:
        i += 1
        a += n % i < 1
        while n % i < 1:
            n /= i
    print(a + (n > 1))

Submission status: Accepted

Solution code:
import math
a, b = map(int,input().split())
c = int(math.sqrt(min(a,b)) +1)
e = max(a,b)
d = min(a,b) 
def pn(x,y):
    isprime = [1 for _ in range(x+1)]
    primes = []
    y = y
    for i in range(2,x+1):
        if isprime[i]:
            s = 2*i
            primes.append(i)
            while s <= x:
                isprime[s] = 0
                s += i
            while y%i==0:
                y = y//i
    if y!=1:
        primes.append(y)
    return primes
    
def pf(x,y,primes):
    pfs = []
    for i in primes:
        fx = x%i
        fy = y%i
        if fx==0 and fy==0:
            pfs.append(i)
            
    return pfs
primes = pn(c,d)
print(len(pf(a,b,primes))+1)

Submission status: Accepted

Solution code:
#gcd
from fractions import gcd

#素因数分解
def primefact(x0):
    tmp_l = [1]
    if x0 == 1:
        return tmp_l
    i = 2
    while 1:
        if i > pow(x0,1/2):
            if x0 == 1:
                break
            tmp_l.append(x0)
            break
        if x0 % i == 0:
            tmp_l.append(i)
            while x0 % i == 0:
                x0 //= i   
        i+=1
    return tmp_l


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

g = gcd(a,b)
print(len(primefact(g)))

Submission status: Accepted

Solution code:
#素因数分解
def primefact(x0):
    tmp_l = [1]
    if x0 == 1:
        return tmp_l
    i = 2
    while 1:
        if i > pow(x0,1/2):
            if x0 == 1:
                break
            tmp_l.append(x0)
            break
        if x0 % i == 0:
            tmp_l.append(i)
            while x0 % i == 0:
                x0 //= i   
        i+=1
    return tmp_l

#最大公約数
def gcd(x0, y0):
    if x0<y0:
        tmp0 = x0
        x0 = y0
        y0 = tmp0
    if y0 == 0:
        return x0
    else:
        return gcd(y0, x0 % y0)
        
a,b=map(int,input().split())

g = gcd(a,b)
print(len(primefact(g)))

Submission status: Accepted

Solution code:
def primeFac(n):
	res = {1}
	for i in range(2, int(n**0.5) + 1):
		while n % i == 0:
			n //= i
			res.add(i)
		if n <= 1:
			break
	if n > 1:
		res.add(n)
	return res

a, b = map(int, input().split())
res = primeFac(a) & primeFac(b)
print(len(res))

Submission status: Accepted

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

def gcd(x, y):
    return gcd(y, x%y) if y else x

def factorize(n):
    res = []
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
            continue
        res.append([i, n])
        while n % i == 0:
            n //= i
            res[-1][1] += 1
        i += 1
    if n != 1:
        res.append([n,1])
    return res

g = gcd(A, B)
f = factorize(g)
ans = len(f) + 1
print(ans)

Submission status: Accepted

Solution code:
def gcd(m, n):
    while n:
        m, n = n, m % n
    return m
a, b = map(int, input().split())
g = gcd(a, b)

ans = 1
x = 2
while x*x <= g:
    if g % x == 0:
        while g % x == 0:
            g //= x
        ans += 1
    x += 1
if g > 1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
# 再帰関数の最大回数を増やす
import sys
sys.setrecursionlimit(1000000)

import math

def gcd(i, j):
    """
    2値 i, j の最大公約数を求める。
    """

    if j == 0:
        return i
    else:
        return gcd(j, i % j)

def factorize(n):
    """
    素因数分解した個数を返す
    """
    count = 1
    rep = math.ceil(math.sqrt(n))
    for i in range(2, rep + 1):
        if n % i != 0:
            continue
        else:
            count += 1
            while n % i == 0:
                n /= i
        if n == 1:
            return count
    if n != 1:
        count += 1
    return count

def main():
    a, b = map(int, input().split())

    #最大公約数を求める
    x = gcd(a, b)

    #最大公約数を素因数分解する
    count = factorize(x)

    #結果を出力する
    print(count)

main()

Submission status: Accepted

Solution code:
def f(n):
    res = set()
    for i in range(2, int(n ** 0.5)):
        if n % i: continue
        while not n % i: n //= i
        res.add(i)
    return res | {n}
 
a, b = map(int,input().split())
print(len(f(a) & f(b) | {1}))

Submission status: Accepted

Solution code:
# from math import *
from fractions import *

def next_int():
    return int(input())

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

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

Submission status: Accepted

Solution code:
A,B=map(int,input().split())
import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000000)
def gcd(a,b):#最大公約数を返す。Euclid
    if a<b:
        a,b=b,a
    if b==0:
        return a
    return gcd(b,a%b)
c=gcd(A,B)
#print(c)
sqrtc=int(c**(1/2))
vc=c
ans=1
for i in range(2,sqrtc+1):
    if vc%i==0:
        ans+=1
        vc/=i
        while vc%i==0:
            vc/=i
if vc!=1:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
import math
import fractions
from collections import defaultdict
def trial_division(n):
    #素因数を格納するリスト
    factor = defaultdict(int)
    factor[1] += 1
    #2から√n以下の数字で割っていく
    tmp = int(math.sqrt(n)) + 1
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor[num] += 1
    #リストが空ならそれは素数
    factor[n] += 1
    return factor
#%%
A,B = [int(x) for x in input().split()]
divisions = trial_division(fractions.gcd(A,B))
print(len(divisions))

Submission status: Accepted

Solution code:
def f(n):
    res = set()
    for i in range(2, int(n ** 0.5)):
        if n % i: continue
        while not n % i: n //= i
        res.add(i)
    return res | {n}

a, b = map(int,input().split())
print(len(f(a) & f(b) | {1}))

Submission status: Accepted

Solution code:
from fractions import gcd
from math import sqrt
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


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

    return arr


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def f(n):
    res = set()
    for i in range(2, int(n ** 0.5) // 1):
        if n % i: continue
        while not n % i: n //= i
        res.add(i)
    return res | {n}

a, b = map(int,input().split())
print(len(f(a) & f(b) | {1}))

Submission status: Accepted

Solution code:
def factorization(n):
    res = set()
    tmp = n
    for i in range(2, int(n ** 0.5) // 1):
        if tmp % i == 0:
            while tmp % i == 0:
                tmp //= i
            res.add(i)
    res.add(tmp)
    return res

a, b = map(int,input().split())
ans = factorization(a) & factorization(b) | {1}
print(len(ans))

Submission status: Accepted

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

#output
import math

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors
A1 = prime_factors(A)
B1 = prime_factors(B)        
C = set(A1) & set(B1)

print(len(C)+1)

Submission status: Accepted

Solution code:
def factorization(n):
    res = set()
    tmp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if tmp % i == 0:
            while tmp % i == 0:
                tmp //= i
            res.add(i)
    res.add(tmp)
    return res

a, b = map(int,input().split())
ans = factorization(a) & factorization(b) | {1}
print(len(ans))

Submission status: Accepted

Solution code:
def factorization(n):
    res = set()
    tmp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if tmp % i == 0:
            while tmp % i == 0:
                tmp //= i
            res.add(i)
    res.add(tmp)
    if not res:
        res.add(n)
    return res

a, b = map(int,input().split())
ans = factorization(a) & factorization(b) | {1}
print(len(ans))

Submission status: Accepted

Solution code:
def factorization(n):
    res = set()
    tmp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if tmp % i == 0:
            while tmp % i == 0:
                tmp //= i
            res.add(i)
    if tmp != 1:
        res.add(tmp)
    if not res:
        res.add(n)
    return res

a, b = map(int,input().split())
ans = factorization(a) & factorization(b) | {1}
print(len(ans))

Submission status: Accepted

Solution code:
def factorization(n):
    res = set()
    tmp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if tmp % i == 0:
            cnt = 0
            while tmp % i== 0:
                cnt += 1
                tmp //= i
            res.add(i)
    if tmp != 1:
        res.add(tmp)
    if not res:
        res.add(n)
    return res

a, b = map(int,input().split())
ans = factorization(a) & factorization(b) | {1}
print(len(ans))

Submission status: Accepted

Solution code:
def prime_facorize(N):
    res = {1}
    for i in range(2, int(N ** 0.5) + 1):
        while N % i == 0:
            res.add(i)
            N /= i

        if N <= 1:
            break
    if N > 1:
        res.add(N)
    return res


A, B = map(int, input().split())
commons = prime_facorize(A) & prime_facorize(B)
print(len(commons))

Submission status: Accepted

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

a, b = map(int,input().split())
a_list = [x[0] for x in factorization(a)]
b_list = [x[0] for x in factorization(b)]
ans = set(a_list) & set(b_list) | {1}
print(len(ans))

Submission status: Accepted

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

a, b = map(int,input().split())
a_list = [x[0] for x in factorization(a)]
b_list = [x[0] for x in factorization(b)]
ans = set(a_list) & set(b_list) | {1}
print(len(ans))

Submission status: Accepted

Solution code:
from fractions import gcd


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


def main():
    A, B = map(int, input().split())
    g = gcd(A, B)
    lst_prime_numbers = prime_factorize(g)
    ans = 1 + len(set(lst_prime_numbers))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
from math import sqrt
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

A, B = map(int, input().split(" "))
if A >= B:
  C = gcd(A,B)
else:
  C = gcd(B,A)

c = math.ceil(math.sqrt(C)) + 1
l = [1]
f = [1] + [0]*c

for i in range(2,c+1):
  if f[i-1] == 0:
    f[i-1] = 1
    if C % i == 0:
      l.append(i)
      while C % i == 0:
        C //= i
    for j in range(i+i, c+1, i):
      f[j-1] = 1

if C > 1:
  l.append(C)

print(len(l))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def run_prime_factorization(max_number: int) -> dict:
    '''Run prime factorization.
    Args:
        max_number: Int of number (greater than 1).
    Returns:
        A dictionary's items ((base, exponent) pairs).
    Landau notation: O(log n)
    '''

    from math import sqrt

    ans = dict()
    remain = max_number

    for base in range(2, int(sqrt(max_number)) + 1):
        if remain % base == 0:
            exponent_count = 0

            while remain % base == 0:
                exponent_count += 1
                remain //= base

            ans[base] = exponent_count

    if remain != 1:
        ans[remain] = 1

    return ans


def main():
    a, b = map(int, input().split())

    # KeyInsight:
    # x, yが互いに素であることと，x, yの最大公約数が1であることは同値
    # 素因数分解して，共通の素因数をすべて選ぶ
    count = 1
    result_a = run_prime_factorization(a)
    result_b = run_prime_factorization(b)
    count += len(result_a.keys() & result_b.keys())
    print(count)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


class Prime(object):
    '''Represents a snippet for prime numbers.
    '''

    def __init__(self, number):
        self.number = number
        self._values = []

    def is_included(self) -> bool:
        '''Determine whether it is a prime number.
        Args:
            number: Int of number (greater than 0).
        Returns:
            True if the input number was prime.
            False if the input number was not prime.
        See:
            https://qiita.com/srtk86/items/874639e361917e5016d4
            https://docs.python.org/ja/3/library/2to3.html?highlight=isinstance#2to3fixer-isinstance
        '''

        from math import sqrt

        if (self.number <= 1) or (isinstance(self.number, float)):
            return False

        for i in range(2, int(sqrt(self.number)) + 1):
            if self.number % i == 0:
                return False

        return True

    def generate(self) -> list:
        '''Generate a list of prime numbers using sieve of Eratosthenes.
        Returns:
            A list of prime numbers that is eqaul to or less than the input
            number.
        Landau notation: O(n log log n)
        See:
            https://beta.atcoder.jp/contests/abc110/submissions/3254947
        '''

        if self._values:
            return self._values

        is_met = [True for _ in range(self.number + 1)]
        is_met[0] = False
        is_met[1] = False

        for i in range(2, self.number + 1):
            if is_met[i]:
                self._values.append(i)

                for j in range(2 * i, self.number + 1, i):
                    is_met[j] = False
        return self._values


def main():
    a, b = map(int, input().split())
    set_a = set()
    set_b = set()

    # a, bの約数を計算
    for i in range(1, int(a ** 0.5) + 1):
        if a % i == 0:
            set_a.add(i)
            set_a.add(a // i)

    for i in range(1, int(b ** 0.5) + 1):
        if b % i == 0:
            set_b.add(i)
            set_b.add(b // i)

    # aとbの公約数を求める
    set_ab = set_a & set_b
    count = 1

    # 素数を計算
    for s in set_ab:
        p = Prime(s)

        if p.is_included():
            count += 1

    print(count)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math


def main():
    inputs = input().split()
    inputs = [int(i) for i in inputs]

    a = inputs[0]
    b = inputs[1]

    g = n = gcd(a, b)
    d = {}

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

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

    print(len(d) + 1)


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
a,b = map(int,input().split())
gcdab = gcd(a, b)
d = {}
j = 2
while j*j<=gcdab:
  while gcdab%j==0:
    gcdab //= j
    if j in d:
      d[j] += 1
    else:
      d[j] = 1
  j += 1
if gcdab>1:
  d[gcdab] = 1
print(len(d)+1)

Submission status: Accepted

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

while b!=0:
  a,b=b,a%b

n=a
s=set()
s.add(1)

while n%2==0:
  n //= 2
  s.add(2)

f=3
while f*f<=n:
  if n%f==0:
    n //= f
    s.add(f)
  else:
    f += 2

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

print(len(s))

Submission status: Accepted

Solution code:
#################################
#ここからcode
import fractions
A,B = map(int,input().split())

gcd = fractions.gcd(A,B)
if gcd == 1:
    print(1)
else:
    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

    soinsulist=factorization(gcd)
    print(len(soinsulist)+1)

Submission status: Accepted

Solution code:
from sys import stdin
A, B = [int(_) for _ in stdin.readline().rstrip().split()]
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
print(len(set(prime_factorize(A)) & set(prime_factorize(B)))+1)

Submission status: Accepted

Solution code:
import numpy as np
a, b = map(int, input().split())
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
n = gcd(a, b)

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

print(len(set(table))+1)

Submission status: Accepted

Solution code:
from math import sqrt


def get_divisors(n):
    """
    約数の個数を数える
    :param n: 自然数
    :return: 約数の個数, 約数の set
    """
    res = {1}
    cnt = 1
    for i in range(2, int(sqrt(n)) + 1):
        if n % i == 0:
            cnt += 1

        while n % i == 0:
            res.add(i)
            n /= i
        if (n <= 1): break

    if n > 1:  # 素数の場合
        res.add(n)
    return cnt, res


A, B = [int(_) for _ in input().split()]
print(len(get_divisors(A)[1] & get_divisors(B)[1]))

Submission status: Accepted

Solution code:
def prime_decomposition(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

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

A_prime = set(prime_decomposition(A))
B_prime = set(prime_decomposition(B))
union = A_prime & B_prime
print(len(union)+1)

Submission status: Accepted

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

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

yaku_A = dfs(A)
yaku_B = dfs(B)
count = 1

for i in yaku_A:
  if i in yaku_B:
    count += 1

print(count)

Submission status: Accepted

Solution code:
#coding: utf-8
from fractions import gcd
import math

# GCDの約数を素因数分解する
def primeFactor(n):
    flg = 0
    count = 0
    tmp = math.sqrt(n)
    i = 2

    if n == 1:
        return 1

    while i <= tmp:
        # print(str(i)+str(',')+str(gcd_cnt))
        if n % i == 0:
            if flg == 0:
                flg = 1
                count += 1
            n = n // i
        else:
            flg = 0
            i += 1
    # if flg == 1:
    #     count += 1
    # print(str('素数=')+str(count)+str(' n=')+str(n)+str(' i=')+str(i))
    if n > 1:
        count += 1
    # 1を足す
    count += 1
    return count


# # print(len(div))
m,n = map(int,input().split())
p = gcd(m,n)
# print(str('gcd=')+ str(p))
ans = primeFactor(p)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

d = defaultdict(int)
g = gcd(A,B)
tmp = g
for i in range(2, int(g ** 0.5) + 1):
    if tmp % i == 0:
        while tmp % i == 0:
            d[i] += 1
            tmp //= i
if tmp != 1:
    d[tmp] += 1

print(len(d)+1)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+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())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

#約数列挙
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 True

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

    return True

a,b = inpl()
res = 0
gc = fractions.gcd(a,b)
div = make_divisors(gc)
# print(div)
for i in div:
    if is_prime(i):
        res += 1
print(res)

Submission status: Accepted

Solution code:
import fractions as fc

A, B = [int(x) for x in input().split()]
C = fc.gcd(A, B)
b = 2
ans =  1
while b * b <= C:
  if C % b == 0:
    ans += 1
    while C % b == 0:
      C //= b
  if C == 1:
    break
  b += 1
if C > 1:
  ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from fractions import gcd
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

a,b=map(int,input().split())
g=gcd(a,b)
ass=prime_factor(g)
print(len(ass)+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import numpy as np


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

def seachPrimeNum(N):
    max = int(np.sqrt(N))
    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 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 primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


def prime3(n):
    counter = 0
    primes = [2, 3]

    for n in range(5, n, 2):
        isprime = True
        for i in range(1, len(primes)):
            counter += 1
            if primes[i] ** 2 > n:
                break
            counter += 1
            if n % primes[i] == 0:
                isprime = False
                break
        if isprime:
            primes.append(n)
    return primes

a,b=map(int,input().split())
# a=b=10**10
count=0
ad=set(make_divisors(a))
bd=set(make_divisors(b))
# print(ad)
common=ad & bd
# print(common)
l=[]
for s in common:
    if is_prime(s):
        count+=1
print(count+1)
# pr=set(seachPrimeNum(max(common)))
# ans=common & pr 
# print(ans)
# print(len(ans)+1)

Submission status: Accepted

Solution code:
def GCD(a, b):
  if a < b:
    a = a+b
    b = a-b
    a -= b
  q = a//b
  r = a%b
  if r == 0:
    return b
  else:
    return GCD(b, r)

A, B = map(int, input().split())
g = GCD(A, B)
tmp = g
m = 1
ps = []
while m**2 <= g:
  if tmp % m == 0:
    ps.append(m)
    tmp //= m
    m = 2
  else:
    m += 1
ps.append(tmp)
ps = list(set(ps))
print(len(ps))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(12345678)
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def primes(n):
    pl = [1]
    if n == 2:
        pl.append(2)
        return pl
    if n == 3:
        pl.append(3)
        return pl

    i = 2
    while i * i <= n:
        if n % i == 0:
            pl.append(i)
            while n % i == 0:
                n //= i
        i += 1
    if n > 1:
        pl.append(n)
    return pl


def main():
    a, b = map(int, input().split())
    ap = set(primes(a))
    bp = set(primes(b))
    # print(ap)
    # print(bp)
    # print(ap & bp)
    print(len(ap & bp))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions
import collections
   
A,B = map(int,input().split())
gcd = 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

c = prime_factorize(gcd)
d = set(c)
print(len(d)+1)

Submission status: Accepted

Solution code:
import fractions
import collections
   
A,B = map(int,input().split())
gcd = 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

c = collections.Counter(prime_factorize(gcd))
print(len(list(c.keys()))+1)

Submission status: Accepted

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

Submission status: Accepted

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

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

n = gcd(a, b)

if n == 1:
    print(1)
    exit()

m = 2
ans = 1
while m <= (n ** 0.5):
    if n % m == 0:
        ans += 1
        while n % m == 0:
            n //= m
    if n == 1:
        break
    m += 1

if n > 1:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
t=min(a,b)
t1=t
s=max(a,b)
c=1
i=2
while t > 1 and i <=int(t1**(0.5)+1):
  frag=0
  while t%i ==0:
    t=t/i
    if frag==0 and s%i ==0:
      c=c+1
    frag=1
  if i==2:
    i=3
  else:
    i= i+2
if s%t==0 and t > int(t1**(0.5)+1):
  c=c+1
print(c)

Submission status: Accepted

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

def factorization(n):
	lista=[]
	temp=n
	
	i=2
	while i<=int(n**0.5//1):
		if temp%i==0:
			lista.append(i)
			temp=temp//i
		else:
			i=i+1
	if temp!=1:
		lista.append(temp)
#	if lista==[]:
#		lista.append(n)
	
	#lista.append(1)
	return lista
	
#print(factorization(a))
#print(factorization(b))
seta=set(factorization(a))
setb=set(factorization(b))
setc=seta&setb

ans=len(setc)+1
print(ans)