Problem:


Score : 400 points

Problem Statement

Given are positive integers A and B.

Let us choose some number of positive common divisors of A and B.

Here, any two of the chosen divisors must be coprime.

At most, how many divisors can we choose?

Definition of common divisor

An integer d is said to be a common divisor of integers x and y when d divides both x and y.

Definition of being coprime

Integers x and y are said to be coprime when x and y have no positive common divisors other than 1.

Definition of dividing

An integer x is said to divide another integer y when there exists an integer \alpha such that y = \alpha x.

Constraints

All values in input are integers.

1 \leq A, B \leq 10^{12}

Input

Input is given from Standard Input in the following format:

A B

Output

Print the maximum number of divisors that can be chosen to satisfy the condition.

Sample Input 1

12 18

Sample Output 1

3

12 and 18 have the following positive common divisors: 1, 2, 3, and 6.

1 and 2 are coprime, 2 and 3 are coprime, and 3 and 1 are coprime, so we can choose 1, 2, and 3, which achieve the maximum result.

Sample Input 2

420 660

Sample Output 2

4

Sample Input 3

1 2019

Sample Output 3

1

1 and 2019 have no positive common divisors other than 1.



Sample input:
12 18


Sample output:
3

Submission status: Accepted

Solution code:
from fractions import gcd
A, B = map(int,input().split())
C = gcd(A,B)
C0 = C
 
p = {}
for i in range(2,10**6):
    if C % i == 0:
        p[i] = 0
        while C % i == 0:
            C //= i
            p[i] += 1
    if i * i > C0:
        break
if C != 1:
  p[C] = 1
 
print(len(p) + 1)

Submission status: Accepted

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

a,b=map(int,input().split())
g=gcd(a,b)
m=g
c=1
i=2
while i*i<=g:
    if m%i==0:
        c+=1
    while m%i==0:
        m=m//i
    i+=1
if m>1:
    c+=1
print(c)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())

NL=[]
ML=[]
for i in range(1, int(N**0.5)+1):
    if N%i==0:
        NL.append(i)
        if i != N//i:
            NL.append(N//i)
for i in range(1, int(M**0.5)+1):
    if M%i==0:
        ML.append(i)
        if i != M//i:
            ML.append(M//i)
NL.remove(1)
NL.sort()
L=[]
for i in NL:
    if i in ML:
        for j in L:
            if i%j==0:
                break
        else:
            L.append(i)
print(len(L)+1)

Submission status: Accepted

Solution code:
import math

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

def gcd(x, y):
  z = x % y
  if z == 0:
    return y
  else:
    return gcd(y, z)
  
def common_divisors(x, y):
  xd = make_divisors(x)
  xd.append(1)
  xd.append(x)
  yd = make_divisors(y)
  yd.append(1)
  yd.append(y)
  return set(xd).intersection(yd)

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

divisors = common_divisors(a, b)
divisors_set = frozenset(divisors)

res = []

for n in divisors:
  if n == 1 or n == 2 or n == 3:
    res.append(n)
  elif n % 2 == 0:
    continue
  else:
    dvs = set(make_divisors(n))
    if len(dvs) == 0 or not dvs <= divisors_set:
      res.append(n)

print("{}".format(len(res)))

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

if m > 1:
    c += 1
print(c)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import collections
A,B = map(int,input().split())

#最大公約数を求める
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)
    
G = gcd(A, B)

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


#print(factorize(G))
print(len(factorize(G)) + 1)

Submission status: Accepted

Solution code:
import math
import fractions
gcd = math.gcd if hasattr(math, "gcd") else fractions.gcd

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

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

g = gcd(A, B)

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

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):
    factor=[]
    sqrt=int(n**.5) # sqrt=ceil(sqrt(n))
    for d in range(2,sqrt+1):
        while(n%d==0):
            n//=d
            factor.append(d)
    if n!=1: factor.append(n)
    return factor

def resolve():
    a,b=map(int,input().split())
    from fractions import gcd
    g=gcd(a,b)
    factor=prime_factorization(g)
    print(len(set(factor))+1)
resolve()

Submission status: Accepted

Solution code:
import collections

def div_calculation(a, b):
    while b > 0:
        a, b = b, a%b
    return a

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())
div_ab = div_calculation(A, B)
c_dict = collections.Counter(prime_factorize(div_ab))
ans = len(c_dict.keys()) + 1
print(ans)

Submission status: Accepted

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

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


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

g=gcd(A,B)

if g == 1:
  print("1")
else:
  print(len(prime_factorize(g))+1)

Submission status: Accepted

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

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

A,B=map(int,input().split())
g=gcd(A,B)
if(g==1):
    print("1")
else:
    print(len(factorize(g))+1)

Submission status: Accepted

Solution code:
def main():

    a, b = map(int, input().split())
    dividers = makeDividers(a, b)
    ans = []

    for p in dividers:
        flg = True
        for q in dividers:
            if q == 1 or p == q:
                continue
            if p % q == 0:
                flg = False
                break
        if flg:
            ans.append(p)
    print(len(ans))

def makeDividers(x, y):
    listX = []
    listY = []
    for j in range(1, int(max(x, y) ** 0.5) + 1):
        if x % j == 0:
            listX.append(j)
            if j != x // j:
                listX.append(x // j)
        if y % j == 0:
            listY.append(j)
            if j != y // j:
                listY.append(y // j)
    return list(set(listX) & set(listY))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
def trial_division(n):
	factor = []
	while n%2 == 0:
		factor.append(2)
		n //= 2
	f = 3
	while f <= math.sqrt(n):
		if n%f == 0:
			factor.append(f)
			n //= f
		else :
			f += 2
	if n!= 1:
		factor.append(n)
	return factor

def main():
	cds = set()
	cds.add(1)
	a,b = map(int,input().split())
	primes_a = trial_division(a)
	primes_b = trial_division(b)
	if primes_a != None and primes_b != None :
		for prime in primes_a:
			if prime in primes_b:
				cds.add(prime)
	print(len(cds))
main()

Submission status: Accepted

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

         
def nfac(n):
    if n % 2 == 0:
        while n % 2 == 0:
            n //= 2
        r = 2
    else:
        r = 1

    p = 3
    while p*p <= n:
        if n % p == 0:
            n //= p
            r += 1
            while n % p == 0:
                n //= p
        p += 2
    if n > 1:
        r += 1
    return r

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

Submission status: Accepted

Solution code:
s = input().split()
A=int(s[0])
B=int(s[1])

def factorization(n):
    p=[]
    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])
            p.append(i)

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

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

    return p
A_fact=[]
B_fact=[]
answer=[]
count=0

A_fact=factorization(A)
B_fact=factorization(B)

for p in A_fact:
    if p in B_fact:
            answer.append(p)
            count+=1
if A==1 and B==1:
    print(count)
else:
    print(count+1)

Submission status: Accepted

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

i = 2
primes = []
while True:
    if i > 10**6 + 1:
        break
    if n % i == 0:
        n //= i
        primes.append(i)
    else:
        i += 1
print(len(set(primes)) + (n != 1) + 1)

Submission status: Accepted

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


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

    divisors.append(n)
    return divisors


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

C = gcd(A, B)

d = prime_factorize(C)
d.append(1)

print(len(list(set(d))))

Submission status: Accepted

Solution code:
x, y  = map(int, input().split())
 
def prime_factorize(n):
    a = [1]
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
  
prime_x = prime_factorize(x)
prime_y = prime_factorize(y)
 
num_x = len(prime_x)
num_y = len(prime_y)
 
num = min(num_x, num_y)
co = list(set(prime_x) & set(prime_y))

ans = 0
for i in range(len(co)):
  if co == [1]:
    ans = 1
    break
  else:
    if len(prime_factorize(co[i])) == 1 or len(prime_factorize(co[i])) == 2:
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
a,b=map(int, input().split())
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a

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

c = gcd(a,b)

if c == 1:
	print(1)
else:
	print(len(factorization(c))+1)

Submission status: Accepted

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

a,b = map(int, input().split())
g = gcd(a,b)
N = int(g**0.5)
ans = 1
for i in range(2, N+1):
  if g%i==0:
    ans += 1
  while(g%i==0):
    g /= i
if g != 1:
  ans += 1
print(ans)

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

Submission status: Accepted

Solution code:
def factorize(a):
    x=2
    ret=[]
    rt_a=a**0.5
    while x<=a:
        if(x>=rt_a):
            ret.append(a)
            break
        if(a%x==0):
            ret.append(x)
        while a%x==0:
            a//=x
        x+=1
    return ret

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

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

Submission status: Accepted

Solution code:
def divisors(n):
    divs = set()
    for i in range(1,int(n**0.5)+1):
        if n % i == 0:
            divs |= {i, n//i}
    return sorted(divs)

def gcd(n,m):
    if m == 0:
        return n
    else:
        return gcd(m, n%m)

def is_disjoint(n,m):
    return gcd(n,m) == 1

def appendable(list, n):
    return all(is_disjoint(l, n) for l in list)

#O(n**2)!
def filter_disjoint(divisors):
    list = []
    for d in divisors:
        if appendable(list, d):
            list.append(d) 
    return list


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

filterd = filter_disjoint(divisors(gcd(a,b)))
print(len(filterd))

Submission status: Accepted

Solution code:
from fractions import gcd
from collections import Counter


def prime_factor(n):
    c = Counter()
    i = 2
    while i * i <= n:
        while (n % i == 0):
            c[i] += 1
            n = n//i
        i += 1
    if n != 1:
        c[n] += 1

    return c


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

print(len(c) + 1)

Submission status: Accepted

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

A = set(prime_factorize(a))
B = set(prime_factorize(b))
ans = A&B
print(len(ans)+1)

Submission status: Accepted

Solution code:
import sys 
input = sys.stdin.readline
a, b = map(int, input().split())
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

A = set(prime_factorize(a))
B = set(prime_factorize(b))
ans = A&B
print(len(ans)+1)

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の素因数
          n /= i
          table.append(i)
      i += 1
  if n > 1:
      table.append(n)
  return table

x = set(prime_decomposition(A))
y = set(prime_decomposition(B))
print(len(x & y) + 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

from fractions import gcd
import math
A, B = [int(x) for x in input().split()]
N = gcd(A, B)
a = prime_factorize(N)
print(len(set(a))+1)

Submission status: Accepted

Solution code:
import fractions
import math
A, B = map(int,input().split())
cf=fractions.gcd(A,B)
a =[1]
tmp = int(math.sqrt(cf)) + 1
for i in range(2,tmp):
    while cf% i ==0:
        cf//=i
        a.append(i)
a.append(cf)
#print(a)
print(len(set(a)))

Submission status: Accepted

Solution code:
def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return ass 

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 main():
    A, B = map(int, input().split())
    div_A = set(divisor(A))
    div_B = set(divisor(B))
    div_list = list(div_A & div_B)
    cnt = 1
    for n in div_list:
        if is_prime(n):
            cnt += 1

    print(cnt)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def slove():
    import sys
    import fractions
    input = sys.stdin.readline
    a, b = list(map(int, input().rstrip('\n').split()))
    gcd = fractions.gcd(a, b)
    cnt = 1
    for i in range(2, int(gcd ** 0.5) + 1):
        if gcd % i == 0:
            cnt += 1
            while True:
                if gcd % i == 0:
                    gcd //= i
                else:
                    break
    cnt += 0 if gcd == 1 else 1
    print(cnt)


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
def calcDiv(n):
    d_list = []
    for i in range(1, int(n**(1/2))+1):
        if n%i == 0:
            d_list.append(i)
            d_list.append(int(n/i))
    return d_list


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


if __name__ == "__main__":    
    a, b = map(int, input().split())
    a_list = calcDiv(a)
    b_list = calcDiv(b)
    d_list = set(a_list) & set(b_list)
    cnt = 0
    for d in d_list:
        if isPrime(d):
            cnt += 1
    print(cnt)

Submission status: Accepted

Solution code:
import math

def pf(n):
    ans=[1]
    i=2
    if(n%i==0):
        while(n%2==0):
            n = n/i
        ans.append(i)
    i+=1
    while(i<math.sqrt(n) and n!=1):
        if (n%i==0):
            while(n%i==0):
                n=n/i
            ans.append(i)
        i+=2
    if(n!=1):
        ans.append(n)
    return set(ans)

a,b = map(int,input().split())
pfa=pf(a)
a=0
for i in pfa:
    if(b%i==0):
        a+=1
print(a)

Submission status: Accepted

Solution code:
temp = input().split(" ")
a = min(int(temp[0]), int(temp[1]))
b = max(int(temp[0]), int(temp[1]))

def divisors(n):
  i = 2
  ret = [1]
  while True:
    while n % i == 0:
      if not i in ret:
        ret.append(i)
      n = n // i
    if n == 1 : break
    if i * i > n:
      ret.append(n)
      break
    i += 1
  return ret

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

print(len(divisors(gcd(a, b))))

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
  
def gcd(x, y):
  if y == 0:
    return x
  else:
    return gcd(y, x % y) #再帰定義

max_kou = gcd(A, B)

print(len(set(prime_factorize(max_kou)))+1)

Submission status: Accepted

Solution code:
A, B = map(int, input().split())
 
def gcd(a, b):  # a,bの最大公約数
    while b:
        a, b = b, a % b
    return a

def factorization(n):  # 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 == []: # ｎが1のとき
        arr.append([n, 1])
    return arr
 
g = gcd(A, B) 
ans = len(factorization(g))

if g != 1:
    ans += 1
print(ans)

Submission status: Accepted

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

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

    # divisors.sort()
    return divisors

a,b = map(int,input().split())
c = fractions.gcd(a,b)
lis = make_divisors(c)
cnt=0
for i in lis:
    if(is_prime(i)):
        cnt+=1
print(cnt+1)

Submission status: Accepted

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

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

def yakusu(x,X):
    for i in range(1,int(x**0.5)+1):
        if x%i==0:
            X.append(i)
            if x!=i:
                X.append(x//i)
    
A=[]
B=[]
yakusu(a,A)
yakusu(b,B)
A.sort()
B.sort()
#print(A,B)
kouyakusu=[]
i=0
j=0
while i<len(A) and j<len(B):
    if A[i]==B[j]:
        kouyakusu.append(A[i])
        i+=1
        j+=1
    elif A[i]>B[j]:
        j+=1
    else:
        i+=1

ans=0
for i in range(1,len(kouyakusu)):
    if not(kouyakusu[i]): continue
    ans+=1
    for j in range(i+1,len(kouyakusu)):
        if kouyakusu[j]%kouyakusu[i]==0:
            kouyakusu[j]=False
#print(kouyakusu)
print(ans+1)

Submission status: Accepted

Solution code:
a, b = [int(i) for i in 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

  
import math

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
ad = make_divisors(a)
bd = make_divisors(b)
ans = 0
for i in ad:
  if i in bd:
    if is_prime(i):
      ans += 1
print(ans)

Submission status: Accepted

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

A, B = map(int, input().split())
g = gcd(A, B)
a = 1
for n in range(2, g+1):
  if g % n == 0:
    a += 1
    while g % n == 0:
      g //= n
  if n*n > g:
    break
if g > 1:
  a += 1
print(a)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

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

soin_a = np.array([], dtype='int')
for i in range(2, int(np.sqrt(a)) + 1):
    if a % i == 0:
        soin_a = np.append(soin_a, i)
        while a % i == 0:
            a //= i
if a != 1:
    soin_a = np.append(soin_a, a)

soin_b = np.array([], dtype='int')
for i in range(2, int(np.sqrt(b)) + 1):
    if b % i == 0:
        soin_b = np.append(soin_b, i)
        while b % i == 0:
            b //= i
if b != 1:
    soin_b = np.append(soin_b, b)

ans = 1
for j in soin_a:
    if soin_b[soin_b == j].size != 0:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd


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


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

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

Submission status: Accepted

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

""" return a list of the prime factors for a nutural numbers"""
def prime_factorization(k):
  if k < 2:
    return []
  r = math.ceil(math.sqrt(k))
  ans = []
  i = 2
  while i <= r:
    if k % i == 0:
      ans.append(i)
      k //= i
    else:
      i += 1
  if k > 1:
    ans.append(k) 
  return ans

if __name__ == "__main__":
  n,k = map(int,input().split())
  #print(gcd(n,k))
  l = prime_factorization(gcd(n,k))
  print(len(set(l))+1)

Submission status: Accepted

Solution code:
from fractions import*
from collections import*
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())
c = Counter(prime_factorize(gcd(a,b)))
print(len(c.keys())+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 = [int(x) for x in input().split()]
from fractions import gcd

x = gcd(a,b)

x = prime_factorize(x)
print(len(set(x)) + 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())
a_lst = set(prime_factorize(a))
b_lst = set(prime_factorize(b))
print(len(a_lst & b_lst)+1)

Submission status: Accepted

Solution code:
import fractions

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

set_fact={1}
for i in range(2,gcd_AB+1):
  if i**2>gcd_AB:
    break
  
  while(True):
    if gcd_AB%i==0:
      gcd_AB//=i
      set_fact.add(i)
    else:
      break
      
if gcd_AB!=1:
  set_fact.add(gcd_AB)

print(len(set_fact))

Submission status: Accepted

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

l_m = prime_factorize(m)
if len(l_m) >= 1:
    ans = 2
else:
    print("1")
    exit()
for i in range(1,len(l_m)):
    if not l_m[i] == l_m[i-1]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# ABC142D - Disjoint Set of Common Divisors
from fractions import gcd


def prime_factors(x: int) -> list:
    if x % 2:
        max_prime, factors = 0, []
    else:
        max_prime, factors = 2, [2]
        while x % 2 == 0:
            x //= 2
    for i in range(3, int(x ** 0.5) + 1, 2):
        if x % i == 0:
            max_prime = i
            factors.append(i)
            while x % i == 0:
                x //= i
    if x > 2:  # when x is prime greater than 2
        factors.append(x)
    return factors


def main():
    # compute the number of prime factors of gcd(A, B)
    A, B = map(int, input().split())
    g = gcd(A, B)
    ans = len(prime_factors(g)) + 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def factorization(n):
    ret=[]
    if n==1:
        ret.append(1)
    else:
        for l in range(1,int(n**0.5)+1):
            if n%l==0:
                ret.append(l)
                ret.append(n//l)
    return ret

a,b=map(int,input().split())
A,B=factorization(a),factorization(b)
disjoint=[]
ans=0
A.sort()
for i in A:
    flag=True
    if i not in B:
        flag=False
    for j in disjoint:
        if i%j==0 and j!=1:
            flag=False
    if flag:
        disjoint.append(i)
        ans+=1
        
print(ans)

Submission status: Accepted

Solution code:
import sys,fractions,math
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split()) 
DBG = True # and False

def ddprint(x):
  if DBG:
    print(x)

def prime_division(x):
    q = int(math.sqrt(x))
    a = []
    for i in range(2,q+1):
        ex = 0
        while x%i == 0:
            ex += 1
            x //= i
        if ex>0:
            a.append([i,ex])
    if x>q:
        a.append([x,1])
    return a

a,b = inm()
g = fractions.gcd(a,b)
p = prime_division(g)
print(len(p)+1)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))


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

gcd = fractions.gcd(A,B)
ans = 1
for facter in factorization(gcd):
    if facter[0] == 1:
        pass
    else:
        ans += 1
print(ans)


'''
12 18
1 2 3 6
1 2 3

6 9
1 3
1 2 3

420 660
210 330
105 165
35 55
7 11

2**2*3
1 2 3 5
'''

Submission status: Accepted

Solution code:
import sys,os,math
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat


# sys.stdin = open('input')
# n, k = map(int, raw_input().split())
# da = map(int, raw_input().split())
# db = map(int, raw_input().split())


def solve():

    pass

def main():
    a, b = map(int, raw_input().split())
    def gcd(a, b):
        if b:
            return gcd(b, a%b)
        return a

    def div(n):
        c = 0
        for i in range(2, int(math.sqrt(n)+1)):
            if n%i==0:
                c += 1
                while n%i==0:
                    n /= i
        if n>1:
            c+=1
        return c+1
    print div(gcd(a,b))





main()

Submission status: Accepted

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

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

    return divisors

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

common_divisors = make_divisors(A) & make_divisors(B)
counter = 0
for cd in common_divisors:
    if is_prime(cd):
        counter += 1
print(counter + 1)

Submission status: Accepted

Solution code:
import math
from fractions import gcd


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


s = int(math.sqrt(g))

f = {}
for i in range(2, s+1):
    while g % i == 0:
        f[i] = f.get(i, 0) + 1
        g = g/i
if g != 1:
    f[g] = f.get(g, 0) + 1

print(len(f)+1)

Submission status: Accepted

Solution code:
import math

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


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


s = int(math.sqrt(g))

f = {}
for i in range(2, s+1):  
    while g % i == 0:  
        f[i] = f.get(i, 0) + 1  
        g = g/i  
if g != 1:
    f[g] = f.get(g, 0) + 1

print(len(f)+1)

Submission status: Accepted

Solution code:
#素因数分解をする
from fractions import gcd
import numpy as np
a,b = [int(i) for i in input().split()]
g = gcd(a,b)

primes = []
n=1

#約数に関して、常に、これが言える。
while n**2 <=g:
    n += 1
    q,r = divmod(g,n)
    if r!=0:
        continue
    while r==0:
        g = q
        q,r = divmod(g,n)
    primes.append(n)

#最後に素数が余るケース    
if g != 1:
    primes.append(g)
    
print(len(primes)+1)