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

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

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

a = prime_factorize(GCD)

print(len(a))

Submission status: Accepted

Solution code:
from fractions import gcd
def Comon_divisor(a,b):
    GCD=gcd(a,b)
    num=int(GCD**0.5)
    Cd=[1]
    for i in range(2,num+2):
        if GCD%i == 0:
            Cd.append(i)
        while True:
            if GCD%i == 0:
                GCD //= i
            else:break

    if GCD != 1:
        Cd.append(GCD)
    return Cd
a,b = map(int, input().split())
Divisor = Comon_divisor(a, b)
print(len(Divisor))
#print(Divisor)

Submission status: Accepted

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

def lcm(a, b):
    return a // gcd (a, b) * 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

n, m = map(int, input().split())
g = gcd(n,m)
if g == 1:
    print(1)
else:
    print(len(factorization(g))+1)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

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

#a,bの最小公倍数
def lcm(a, b):
    return a * b // gcd(a, b)

# 素因数分解
def prime_factorization(n):
    arr = []
    tmp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if tmp % i == 0:
            while tmp % i == 0:
                arr.append(i)
                tmp //= i
    if(tmp != 1):
        arr.append(tmp)
    if not arr:
        arr.append(n)
    return arr 

def main():
    A, B = map(int, input().split())
    tmp = gcd(A, B)
    if tmp == 1:
        print(1)
    else:
        print(1 + len(set(prime_factorization(tmp))))

if __name__ == "__main__":
    main()

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
l=[]
a,b=map(int,input().split())
import fractions
g=fractions.gcd(a,b)
for i in range(len(prime_decomposition(g))):
  if prime_decomposition(g)[i] not in l:
    l.append(prime_decomposition(g)[i])
print(len(l)+1)

Submission status: Accepted

Solution code:
A, B = 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

d=set(prime_factorize(A)) & set(prime_factorize(B))

print(len(d))

Submission status: Accepted

Solution code:
A,B=map(int,input().split())
a=[1]
con=True
while con:
    con=False
    for i in range(2,int(A**0.5)+1):
        if A%i==0:
            con=True
            a.append(i)
            A=A//i
            break
a.append(A)
b=[1]
con=True
while con:
    con=False
    for i in range(2,int(B**0.5)+1):
        if B%i==0:
            con=True
            b.append(i)
            B=B//i
            break
b.append(B)
a=set(a)
b=set(b)
c=list(a&b)
from copy import copy
d=copy(c)
for i in range(len(d)):
    for j in range(len(c)):
        if i!=j:
            for k in range(2 ,min(d[i],c[j])):
                if d[i]%k==0 and c[j]%k==0:
                    c[j]=0
ans=0
for i in range(len(c)):
    if c[i]!=0:
        ans+=1
print(ans)

Submission status: Accepted

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

import math
def findFactors(n):
    now=n
    f=[]
    while now%2==0:
        now//=2
        f.append(2)
    p=3
    while p<=math.sqrt(n):
        while now%p==0:
            now//=p
            f.append(p)
        p+=2
        if now==1:
            break
    if now>math.sqrt(n):
        f.append(now)
    return f

if g==1:
    print(1)
else:
    f=set(findFactors(g))
    print(len(f)+1)

Submission status: Accepted

Solution code:
def soin(N):
    res = [1]
    i = 2
    while i < round(N**(1/2)) + 3:
        if N%i == 0:
            res.append(i)
            N = N//i
            i = 2
        else:
            i += 1
    res.append(N)
    return set(res)

A, B =(int(i) for i in input().split())
print(len(soin(A)&soin(B)))

Submission status: Accepted

Solution code:
# import bisect
from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def factorization(n):
    #素因数分解

    factor = []

    for i in list(range(2,3)) + list(range(3, int(n**0.5)+ 1, 2)):
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                n //= i
                factor.append(i)
    if n != 1:
        factor.append(n)

    return factor

def main():
    a, b = list(map(int,ipti().split()))
    a_fac = set(factorization(a))
    b_fac = set(factorization(b))
    ab_common = a_fac & b_fac
    print(len(ab_common)+1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
m, n = map(int, input().split())
while True:
  if m < n:
    m, n = n, m
  if m%n:
    m, n = n, m%n
  else:
    break

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()
ans = [1]
notans = [False]*len(divisors)
for j in range(len(divisors)):
    if divisors[j] == 1 or notans[j] == True:
        continue
    ans.append(divisors[j])
    for i in range(j+1, len(divisors)):
        if divisors[i]%divisors[j] == 0:
            notans[i] = True

print(len(ans))

Submission status: Accepted

Solution code:
from fractions import gcd
import math
a,b = map(int,input().split())
n = gcd(a,b)
if n == 1:
    print(1)
    exit()
count = 1
for i in range(2,math.ceil(math.sqrt(n))+1):
    if n % i == 0:
        count += 1
        while n % i == 0:
            n //= i
if n > 1:
    count += 1
print(count)

Submission status: Accepted

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

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

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

g = gcd(a,b)
arr = factorization(g)
print(len(arr))

Submission status: Accepted

Solution code:
import math

a,b = map(int, input().split())
 
def gcd(a, b):
  while b:
      a, b = b, a % b
  return a
 
def prime(n):
    factor = {}
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            if not num in factor.keys():
                factor[num] = 1
            else:
                factor[num] += 1
    if n != 1:
        if not n in factor.keys():
            factor[n] = 1
        else:
            factor[n] += 1
    return factor

g = gcd(a,b)
fac = prime(g)
print(len(fac)+1)

Submission status: Accepted

Solution code:
from fractions import gcd


def main():
    A, B = map(int, input().split(" "))
    g = gcd(A, B)
    answer = [1]
    while not g % 2:
        g //= 2
        answer.append(2)
    i = 3
    while i * i <= g:
        if not g % i:
            g //= i
            answer.append(i)
        else:
            i += 2
    if not g == 1:
        answer.append(g)
    print(len(set(answer)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions
a,b = map(int,input().split())
g = 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
  
#1または素数が解
lis = prime_factorize(g)
lis = list(set(lis)) #重複を削除
print(len(lis)+1)    #1を追加

Submission status: Accepted

Solution code:
import sys
A,B = map(int,input().split())
def trial_division(n):
    if n < 2:
        return []

    prime_factors = []

    for i in range(2, int(n**0.5)+1):
        # nがi（の累乗）で割り切れるかを調べる
        while n % i == 0:
            # nがiで割り切れる場合、iを素因数としてリストに追加する
            prime_factors.append(i)
            # nをiで割った商で更新しておく
            n //= i
    # nの平方根より大きい素因数が存在する場合
    if n > 1:
        prime_factors.append(n)

    return prime_factors

A = set(trial_division(A))
B = set(trial_division(B))
print(len(A & B)+1)

Submission status: Accepted

Solution code:
import math
import fractions

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

a = fractions.gcd(a,b)

i = 2
ans = 1

while i <= a**0.5:
  tmp = a
  while a%i==0:
    a /= i
  if not a == tmp:
    ans += 1
  i += 1
if a >1 :
  ans += 1
  
print(ans)

Submission status: Accepted

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

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

s=gcd(a,b)
x=[]
while s%2==0:
    s//=2
    x.append(2)
f=3
while f*f<=s:
    if s%f==0:
        s//=f
        x.append(f)
    else:
        f+=2
if s!=1:
    x.append(s)
      
print(len(set(x))+1)

Submission status: Accepted

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

a, b = map(int, input().split())
max = gcd(a, b)
pf=[]

#print(max)
tmp=max
i=2
while tmp % 2 == 0:
    pf.append(2)
    tmp //= 2
f = 3
while f * f <= tmp:
    if tmp % f == 0:
        pf.append(f)
        tmp //= f
    else:
        f += 2
if tmp != 1:
    pf.append(tmp)


#print(pf)
spf = set(pf)
#print(spf)
print(len(spf)+1)

Submission status: Accepted

Solution code:
from math import sqrt
def gcd(a,b):
  if a<b:
    a,b=b,a
  if b==0:
    return a
  else:
    return gcd(b,a%b)
a,b=map(int,input().split())
n=gcd(a,b)
#print(n)
ans=1
r=int(sqrt(n)+1)
#print(r)
for i in range(2,r):
  # print(i)
  if n%i==0:
    cnt=0
    while n%i==0:
      #print(n,end=" inside \n")
      n//=i
      cnt=1
    if cnt:
      ans+=1

if n>1:
  ans+=1
#print(n)
print(ans)

Submission status: Accepted

Solution code:
a, b = map(int, input().split())
c = min(a,b)
s = [1]
i = 2
while i <= c**0.5+1:
  if a%i==0 and b%i==0:
    a //= i
    b //= i
    if not(i in s):
      s.append(i)
  else:
    if a%i==0: a//=i
    if b%i==0: b//=i
    i += 1
  c = min(a,b)
if c!=1 and max(a,b)%c==0 and all([i==1 or c%i>0 for i in s]):
  s.append(c)
print(len(s))

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)
    return divisors


A = set(make_divisors(A))
B = set(make_divisors(B))
C = A & B

cnt = 0
for i in C:
    if len(make_divisors(i)) == 1 or len(make_divisors(i)) == 2:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
def get_prime_dic(n):
    dic = {}
 
    i = 2
    while i * i <= n:
        while n % i == 0:
            n //= i
            if i in dic:
                dic[i] += 1
            else:
                dic[i] = 1
        i += 1
 
    if n > 1:
        dic[n] = 1
    return dic
c=get_prime_dic(a)
d=get_prime_dic(b)
ans=1

ans+=len(set(c)&set(d))

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)
d = set()
i = 2
while i * i <= c:
	while c % i == 0:
		c /= i
		d.add(i)
	i += 1
if c != 1:
	d.add(c)
print(len(d) + 1)

Submission status: Accepted

Solution code:
from math import sqrt

A, B = map(int, input().split())
rootA = int(sqrt(A))+1
rootB = int(sqrt(B))+1

PrimeFactorA = []
PrimeFactorB = []
for i in range(2, rootA+1):
	while A%i == 0:
		A //= i
		PrimeFactorA.append(i)
	if A == 1:
		break
else:
	PrimeFactorA.append(A)
PrimeFactorA = set(PrimeFactorA)

for i in range(2, rootB+1):
	while B%i == 0:
		B //= i
		PrimeFactorB.append(i)
	if B == 1:
		break
else:
	PrimeFactorB.append(B)
PrimeFactorB = set(PrimeFactorB)

count = 1
for a in PrimeFactorA:
	if a in PrimeFactorB:
		count += 1

print(count)

Submission status: Accepted

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

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

    # divisors.sort()
    return divisors
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
c = make_divisors(a)
d = make_divisors(b)

f = list(set(c) & set(d))
ans = []

for s in f:
    if is_prime(s):
        ans.append(s)
print(len(ans)+1)

Submission status: Accepted

Solution code:
a,b=map(int,input().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])
  return arr
def gcd(a,b):
  if b==0:
    return a
  return gcd(b,a%b)

g=gcd(a,b)
l=factorization(g)
print(len(l)+1)

Submission status: Accepted

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

g = gcd(a,b)
# print(g)
s = set()
for i in range(2,ceil(sqrt(g))+1):
    while g % i == 0:
        g //= i
        s.add(i)
if g != 1:
    s.add(g)
# print(g)
# print(s)
print(len(s)+1)

Submission status: Accepted

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

g = gcd(a,b)

s = set()
for i in range(2,ceil(sqrt(g))+1):
    while g % i == 0:
        g //= i
        s.add(i)
if g != 1:
    s.add(int(1e14))
#print(g)
#print(s)
print(len(s)+1)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1

a, b = MAP()
kouyaku = list(set(divisor(a)) & set(divisor(b)))

ans = 0
for k in kouyaku:
    if is_prime(k):
        ans += 1
print(ans+1)

Submission status: Accepted

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

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

a,b=map(int,input().split())
div_a=divisor(a)
div_b=divisor(b)
div_ab=[]
for aa in div_a:
    if aa in div_b:
        div_ab.append(aa)
ans=0
for ab in div_ab:
    if isPrime(ab):
        ans+=1
print(ans)

Submission status: Accepted

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

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

a = ssb(A)
b = ssb(B)

print(len(a&b))

Submission status: Accepted

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

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

def main():
  a, b = map(int, input().strip().split())
  g = gcd(a, b)
  
  count = 0
  for p in range(2, int(g ** 0.5 + 1)):
    if g % p == 0:
      count += 1
    while g % p == 0:
      g //= p
      
  if g != 1:
    count += 1
    
  print(count + 1)

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
A,B = map(int,input().split())
def gcd(a,b):
  if b == 0:
    return a
  else:
    return gcd(b,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

m = gcd(A,B)
r = factorization(m)

for row in r:
  if row[0] == 1:
    print(len(r))
    exit()
print(len(r)+1)

Submission status: Accepted

Solution code:
from fractions import gcd
from collections import Counter
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:
        g//=i
        L.append(i)
if L==[]:
    L.append(g)
else:
    if g!=1:
        L.append(g)
LC=Counter(L)
r=len(LC)
if 1 not in LC.keys():
   r+=1
print(r)

Submission status: Accepted

Solution code:
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 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 #sortされていない

def main():
    A, B = map(int, input().split())
    div_A = set(divisor(A))
    div_B = set(divisor(B))
    com_div = div_A & div_B
    cnt = 1
    for a in com_div:
        if is_prime(a):
            cnt += 1

    print(cnt)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
a,b = map(int,input().split())
while b!= 0:
  a,b = b,a%b
n = a
rn = int(math.sqrt(n))
cnt = 1
for i in range(2,rn+1):
    if n%i == 0:
        while n%i == 0:
            n = n//i
        cnt += 1
if n == 1:
    print(cnt)
else:
    print(cnt+1)

Submission status: Accepted

Solution code:
A, B = (int(i) for i in input().split())
def euclid(a, b):
    while b:
        a, b = b, a%b
    return a
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
try:
  print(len(list(set(prime_decomposition(euclid(A,B)))))+1)
except:
  print(1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

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


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


sys.setrecursionlimit(1000000)
MOD = int(1e09) + 7
INF = int(1e30)


def main():
    # sys.stdin = open("Sample.txt")
    A, B = Scanner.map_int()
    ans = 0
    for a in Math.divisor(Math.gcd(A, B)):
        if Math.isPrime(a):
            ans += 1
    ans += 1
    print(ans)
    return


if __name__ == "__main__":
    main()

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())
print(len(set(prime_factorize(a)) & set(prime_factorize(b))) + 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())
common_divisors = set(prime_factorize(a)) & set(prime_factorize(b)) | {1}
print(len(common_divisors))

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

Submission status: Accepted

Solution code:
from fractions import gcd
import math
 
def get_prime_numbers(n):
  prime_nums = {}
  for i in range(2, int(math.sqrt(n)) + 1):
    while n % i == 0:
      if i in prime_nums.keys():
        prime_nums[i] += 1
      else:
        prime_nums[i] = 1
      n //= i
  if n != 1:
    if n in prime_nums.keys():
      prime_nums[n] += 1
    else:
      prime_nums[n] = 1
  return prime_nums
 
a, b = map(int, input().split())
gcd_n = gcd(a, b)
prime_nums = get_prime_numbers(gcd_n)
print(len(prime_nums.keys())+1)

Submission status: Accepted

Solution code:
from fractions import gcd
import math
 
A, B = map(int, input().split())
 
N = gcd(A, B)
 
def prime(n):
    factor = {}
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            if not num in factor.keys():
                factor[num] = 1
            else:
                factor[num] += 1
    if n != 1:
        if not n in factor.keys():
            factor[n] = 1
        else:
            factor[n] += 1
    return factor

factor = prime(N)
print(len(factor) + 1)

Submission status: Accepted

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

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

print(len(list(set(prime(a)).intersection(set(prime(b)))))+1)

Submission status: Accepted

Solution code:
a,b = map(int,input().split())
def gcd(x,y):
  while y != 0:
    cur = x
    x = y
    y = cur%y
  return x
t = gcd(a,b)
L = []
for i in range(2,10**6+1):
  while t%i == 0:
    t = t//i
    if i not in L:
      L.append(i)
if t != 1:
  L.append(t)
print(len(L)+1)

Submission status: Accepted

Solution code:
a,b = map(int,input().split())
def gcd(x,y):
  while y != 0:
    cur = x
    x = y
    y = cur%y
  return x
t = gcd(a,b)
L = []
for i in range(2,int(t**0.5)+1):
  while t%i == 0:
    t = t//i
    if i not in L:
      L.append(i)
if t != 1:
  L.append(t)
print(len(L)+1)

Submission status: Accepted

Solution code:
import numpy as np
from sys import stdin
from copy import deepcopy
from functools import reduce
from fractions import gcd
import math
import itertools
from collections import Counter
from itertools import chain  ##list(chain.from_iterable(l)) ##flatten
from heapq import heappush, heappop

"""
N = int(input())
A, B = map(int,input().split())
A = list(map(int,input().split())) ## 横一列
A = [int(input()) for _ in range(N)] ## 縦一列
lst = [list(map(int,input().split())) for i in range(M)] ## 二次元
"""

# 最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)
  
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())

if min([A, B]) == 1:
  print(1)
  exit()
  
num = gcd_list([A, B])
lst = factorization(num)
ans = 1 + len(lst)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np


# ユークリッドの互除法
def ea(x, y):
    if x < y:
        x, y = y, x
    while x % y != 0:
        x = x % y
        x, y = y, x
    return y


# 素因数分解
def pf(x, p):
    for i in range(2, int(np.sqrt(x)) + 1):
        cnt = 0
        while x % i == 0:
            x /= i
            cnt += 1
        if cnt != 0:
            p.append([i, cnt])
    if x != 1:
        p.append([int(x), 1])


A, B = map(int, (input().split()))
p = []

gcd = ea(A, B)
pf(gcd, p)

ans = 0

p.insert(0, [1, 1])

for i in range(len(p)):
    ans += 1

# print(p)
print(ans)

Submission status: Accepted

Solution code:
def gcd(n,m):#n,mは正の整数、最大公約数　許容は？
    if n==0:
        return m
    elif m==0:
        return n
    elif n>m:
        n=n%m
        return gcd(n,m)
    else:
        m=m%n
        return gcd(n,m)

def ord(N,n):#N,nは正の整数、Nで割り切れる回数、許容はN^1000
    if n%N!=0:
        return 0
    else:
        return 1+ord(N,n//N)

def get_sieve_of_eratosthenes_new(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

primelist=get_sieve_of_eratosthenes_new(10**6)

A,B=map(int,input().split())
x=gcd(A,B)
count=1

for i in range(0,len(primelist)):
    if x%primelist[i]==0:
        count+=1
        x=x//primelist[i]**ord(primelist[i],x)
if x!=1:
    count+=1
print(count)

Submission status: Accepted

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

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

def factorization(n):
    arr=set([1])
    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.add(i)
    if temp!=1:
        arr.add(temp)
    if arr==[]:
        arr.add(n)
    return arr


print(len(factorization(A)&factorization(B)))

Submission status: Accepted

Solution code:
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda x: [ni() for _ in range(x)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda x: [na() for _ in range(x)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda x: [ns() for _ in range(x)]
nas = lambda: stdin.readline().split()

from collections import defaultdict

a, b = na()

def prime_fact(n):
    f = defaultdict(int)
    i = 2
    while i * i <= n:
        while n % i == 0:
            f[i] += 1
            n //= i
        i += 1
    if n != 1:
        f[n] += 1

    return f

c, d = prime_fact(a), prime_fact(b)
e = [i if i in d.keys() else 1 for i in c.keys()]
e.append(1)
f = set(e)
print(len(f))

Submission status: Accepted

Solution code:
import math
a,b=map(int,input().split())
aa,bb=[],[]
while 1<a:
    c=0
    for i in range(2,int(math.sqrt(a))+1):
        if a%i==0:
            a=a//i
            aa.append(i)
            c=1
            break
    if c==0:
        aa.append(a)
        a=1
while 1<b:
    c=0
    for i in range(2,int(math.sqrt(b))+1):
        if b%i==0:
            b=b//i
            bb.append(i)
            c=1
            break
    if c==0:
        bb.append(b)
        b=1
syu=set(aa)&set(bb)
print(len(list(syu))+1)