Problem:


Score : 400 points

Problem Statement

Given are positive integers A and B.

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

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

At most, how many divisors can we choose?

Definition of common divisor

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

Definition of being coprime

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

Definition of dividing

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

Constraints

All values in input are integers.

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

Input

Input is given from Standard Input in the following format:

A B

Output

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

Sample Input 1

12 18

Sample Output 1

3

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

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

Sample Input 2

420 660

Sample Output 2

4

Sample Input 3

1 2019

Sample Output 3

1

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



Sample input:
12 18


Sample output:
3

Submission status: Accepted

Solution code:
import math

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

def factorize(n):
    res = []
    for i in range(2, int(math.sqrt(n))+1):
        if n%i: continue
        res.append([i,0])
        while n%i == 0:
            n /= i
            res[-1][1] += 1
    if n != 1: res.append([n,1])
    return res

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

Submission status: Accepted

Solution code:
from collections import Counter
def get_primes(targ):
    '''
    素因数分解
    '''
    primes = Counter()

    target = targ
    i = 2
    cnt = 0

    while (i * i) <= target:
        while(target % i) == 0:
            target //= i
            primes[i] += 1
        i += 1

    if target > 1:
        primes[target] += 1

    return primes;

def ABC142D_DisjointSetOf():
    A, B = list(map(int, input().strip().split()))

    prA = get_primes(A)
    prB = get_primes(B)

    ans = 0
    for i in prA.keys():
        if i in prB.keys():
            ans += 1

    print(ans + 1)



def main():
    ABC142D_DisjointSetOf()

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

def get_primes(targ):
    '''
    素因数分解
    '''
    primes = []

    target = targ
    i = 2
    cnt = 0

    while (i * i) <= target:
        if(target % i) == 0:
            while(target % i) == 0:
                target //= i
                cnt += 1
            primes.append([i, cnt])
            cnt = 0
        else:
            i += 1

    if target != 1:
        primes.append([target, 1])

    return primes;

def ABC142D_DisjointSetOf():
    A, B = list(map(int, input().strip().split()))

    prA = get_primes(A)
    prB = get_primes(B)

    prAlist = [num[0] for num in prA]
    ans = 0
    for num in prB:
        if(num[0] in prAlist):
            ans += 1

    print(ans + 1)

def main():
    ABC142D_DisjointSetOf()

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def gcm(a, b):
    if a == 0 or b == 0:
        return max(a,b)
    elif a == b:
        return a
    else:
        a2,b2 = min(a,b), max(a,b)
        return gcm(b2 % a2, a2)

g = gcm(a,b)

cnt = 1
while g > 1:
    for i in range(2, int(math.sqrt(g))+1):
        if g % i == 0:
            while g % i == 0:
                g = g // i
            
            cnt += 1
            break
    else:
        g = 1
        
        cnt += 1

print(cnt)

Submission status: Accepted

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


def prime_factor(n):
    ret, p = [], 2

    while p*p <= n:
        if n % p != 0:
            p += 1
            continue

        exp_v = 0
        while n%p == 0:
            exp_v += 1
            n //= p
        ret.append( [p, exp_v] )

        p += 1

    if n != 1: ret.append( [n, 1] )

    return ret


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

print(len(prime_factor(g)) + 1)

Submission status: Accepted

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


def prime_factor(n):
    ret, p = [], 2

    while p*p <= n:
        if n % p != 0:
            p += 1
            continue

        exp_v = 0
        while n%p == 0:
            exp_v += 1
            n //= p
        ret.append( [ret, exp_v] )

        p += 1

    if n != 1: ret.append( [n, 1] )

    return ret


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

print(len(prime_factor(g)) + 1)

Submission status: Accepted

Solution code:
import fractions

a,b=map(int,input().split())
g=fractions.gcd(a,b)
#print(g)
ans=1
i=2
while i*i<=g:
    if(g%i==0):
        ans+=1
        while g%i==0:
            g/=i
    i=i+1
if(g!=1):ans+=1
print(ans)

Submission status: Accepted

Solution code:
def number(a):
    MAX=int(a**0.5)+1
    l=[]
    for i in range(1,MAX):
        if(a%i==0):
            l.append(i)
            if(i != a//i):
                l.append(a//i)
    l=sorted(l)
    return l

def check(c,t):
    for i in c:
        if(t%i==0):
            if(i!=1):
                return False
    
    return True


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

listA=number(A)
listB=number(B)
a=0
b=0
c=[]
while(True):
    if(listA[a]==listB[b]):
        if(check(c,listA[a])):
            c.append(listA[a])
        a+=1
        b+=1
    elif(listA[a]>listB[b]):
        b+=1
    else:
        a+=1
    if(len(listA)==a or len(listB)==b):
        print(len(c))
        exit()

Submission status: Accepted

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

a,b = map(lambda x : int(x),input().split())
ko = gcd(a,b)
if ko == 1 :
    print(1)
else :
    list = factorize(ko)
    print(len(set(list)) + 1)

Submission status: Accepted

Solution code:
A,B = map(int, input().split())
import fractions
f=fractions.gcd(A,B)#最大公約数
def factorization(n):
  primen = []
  degree = []
  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
      primen.append(i)
      degree.append(cnt)
  if temp!=1:
    primen.append(temp)
    degree.append(1)
  if primen==[]:
    primen.append(n)
    degree.append(1)
  return primen,degree
if f != 1:
  ans = factorization(f)
  print(len(ans[1])+1)
else:
  print(1)

Submission status: Accepted

Solution code:
from fractions import gcd
def result(n):
    lists = list()
    num = n
    for i in range(2, int((n**0.5//1))+1):
        if num%i==0:
            time=0
            while num%i==0:
                num //= i
                time+=1
            if not i in lists:
                lists.append(i)
    if num!=1:
        if not num in lists:
                lists.append(num)
    return lists
A , B = list(map(int,input().split()))
print(len(result(gcd(A,B)))+1)

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
            if not i in arr:
                arr.append(i)

    if temp!=1:
        if not temp in arr:
                arr.append(temp)

    return arr

from fractions import gcd
A,B = map(int,input().split())
print(len(factorization(gcd(A,B)))+1)

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
            if not i in arr:
                arr.append(i)

    if temp!=1:
        if not temp in arr:
                arr.append(temp)

    return arr

A,B = map(int,input().split())
common = len(set(factorization(A)) & set(factorization(B)))
print(common+1)

Submission status: Accepted

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

a,b=map(int,input().split())
x=gcd(a,b)
s=set()
for i in range(2, min(x+1,int(math.sqrt(x))+2) ):
    while x%i==0:
        x=x//i
        s.add(i)
    if x==1: break
if x>1: s.add(x)
print(len(s)+1)

Submission status: Accepted

Solution code:
from math import sqrt, ceil

def main():

    ab = input().split(' ')
    a = int(ab[0])
    b = int(ab[1])

    tmp = b
    if a<b:
        tmp = a
        a = b
        b = tmp

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

    count = 1

    if a == 1:
        return count

    if a%2 == 0:
        count += 1
        while a%2 == 0:
            a //= 2
        if a == 1:
            return count
    
    i = 3
    while i*i <= a:
        if a%i == 0:
            count += 1
            while a%i == 0:
                a //= i
            if a == 1:
                return count
        i += 2
        
    return count+1

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

Submission status: Accepted

Solution code:
a,b = map(int,input().split())
import fractions
import collections
import copy
def prime_factorization(n):
    a = [1]
    n1 = copy.deepcopy(n)
    while n % 2 == 0:
        n //= 2
    if n1 != n:
        a.append(2)
    f = 3
    while f * f <= n:
        if n % f == 0:
            n //= f
            if a[-1] != f:
                a.append(f)
        else:
            f += 2
    if a[-1] != n and n != 1:
        a.append(n)
    return a
print(len(prime_factorization(fractions.gcd(a,b))))

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):
    factors = []
    if n == 1: return factors
    i = 2
    while i ** 2 <= n:
        while n % i == 0:
            n //= i
            factors.append(i)
        i += 1
    if n > 1: factors.append(n)
    return factors


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

Submission status: Accepted

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


def prime_factor(n):
    ret, p = [], 2

    while p*p <= n:
        if n % p != 0:
            p += 1
            continue

        exp = 0
        while n%p == 0:
            exp += 1
            n //= p
        ret.append( [ret, exp] )

        p += 1

    if n != 1: ret.append( [n, 1] )

    return ret


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

print( len(prime_factor(g)) + 1)

Submission status: Accepted

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


def prime_factor(n):
    ret = {}
    p = 2
    while p*p <= n:
        while n % p == 0:
            ret[p] = ret.get(p, 0) + 1
            n //= p
        p += 1

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

    return ret


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

print( len(prime_factor(g)) + 1)

Submission status: Accepted

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

import fractions
import math
C=fractions.gcd(A,B)
c=C
arr=[]
for j in range(int(math.sqrt(C)//1-1)):
  i=j+2
  while c%i==0:
    c=c//i
    arr.append(i)
  if c==1:
    break
if c!=1:
  arr.append(c)
import collections

D=collections.Counter(arr)
print(len(D.keys())+1)

Submission status: Accepted

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

def prime_factorize(n):#素因数分解
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
A,B = map(int,input().split())
X=gcd(A,B)
P=prime_factorize(X)

answer=len(set(P))+1
print(answer)

Submission status: Accepted

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

def gcd(x, y):
  x, y = max(x, y), min(x, y) # x >= y
  r = x % y
  if r==0:
    return y
  while r!=0:
    r = x % y
    x, y = y, r #shift
  return x

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

Submission status: Accepted

Solution code:
a, b = map(int, input().split())
def gcd(x, y):
  if x < y:
    tmp = y
    y = x
    x = tmp
  r = x % y
  if r==0:
    return y
  while r!=0:
    r = x % y
    x = y
    y = r
  return x

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

Submission status: Accepted

Solution code:

import fractions

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

a,b=map(int,input().split())
g=fractions.gcd(a,b)
#print(g)
ans=1
i=2
while i*i<=g:
    if(g%i==0):
        ans+=1
        while g%i==0:
            g/=i
    i=i+1
if(g!=1):ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def is_prime(N):
    prime = set()
    
    if not N % 2: prime.add(2)
    while not N % 2: N //= 2
    
    x = 3
    
    while x ** 2 <= N:
        if not N % x: prime.add(x)
        while not N % x: N //= x
        x += 2
        
    if N > 1: prime.add(N)
    
    return prime


def main():
    A, B = map(int, input().split())
    
    a = is_prime(A)
    b = is_prime(B)
    
    print(len(a & b) + 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

a, b = map(int, input().split())
n = gcd(a, b)
i=2
j = 1
while i*i <= n:
    up = True
    while n%i==0:
        if up:
            j+=1
            up=False
        n/=i
    i+=1
if n!=1:j+=1
print(j)

Submission status: Accepted

Solution code:
from fractions import gcd

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

a, b = map(int, input().split())
d = gcd(a, b)
p = factrize(d)
p_unique = set(p)
print(len(p_unique) + 1)

Submission status: Accepted

Solution code:
import sys
import fractions
if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline

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

# nの素数判定
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

N=(fractions.gcd(A, B))
#print(N)
div = make_divisors(N)
#print(div)

ans = 1 # divに1が含まれているため（互いに素の中で必ず1は選べる）
for d in div:
	ans += 1 if is_prime(d) else 0

print(ans)

Submission status: Accepted

Solution code:
import fractions
a,b = map(int,input().split())
longer = max(a,b)
lcm = fractions.gcd(a,b)
i = 1
ans = 1
while True:
  i += 1
  if i * i >= longer:
    if lcm != 1:
      ans += 1
    break
  elif lcm == 1:
    break

  if lcm % i == 0:
    # print(i)
    ans += 1
    while lcm % i == 0:
      lcm //= i
# print(lcm)
print(ans)

Submission status: Accepted

Solution code:
#a,b = (int(i) for i in input().split())
def kouyaku(a,b):
    if a<b:
        temp = a
        a = b
        b = temp
    if b == 0:
        return a
    r = a%b
    if r == 0:
        return b
    else:
        return kouyaku(b,r)

if __name__ == "__main__":
    a,b = (int(i) for i in input().split())
    s = kouyaku(a,b)
    if s == 1:
        print(1)
        exit()
    ans = 1
    t = s
    for i in range(2, int(t**0.5)+1):
        if s == 1: 
            break
        if s%i == 0:
            ans += 1
            while s%i == 0:
                s = s/i
    if s>int(t**0.5):
        ans += 1
    print(ans)

Submission status: Accepted

Solution code:
#a,b = (int(i) for i in input().split())
def kouyaku(a,b):
    if a<b:
        temp = a
        a = b
        b = temp
    if b == 0:
        return a
    r = a%b
    if r == 0:
        return b
    else:
        return kouyaku(b,r)

if __name__ == "__main__":
    a,b = (int(i) for i in input().split())
    s = kouyaku(a,b)
    if s == 1:
        print(1)
        exit()
    ans = 1
    for i in range(2, int(s**0.5)+1):
        if s == 1: 
            break
        if s%i == 0:
            ans += 1
            while s%i == 0:
                s = s/i
    if s>int(s**0.5):
        ans += 1
    print(ans)

Submission status: Accepted

Solution code:
import fractions

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

ans = 0
g = fractions.gcd(a, b)

i = 2
table = []

while i * i <= g:
    while g % i == 0:
        g //= i
        table.append(i)
    i += 1
if g > 1:
    table.append(g)

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

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq
import bisect

MOD = 10**9+7

def gcd(A,B):
    if B>A:
        A,B = B,A

    if(A%B==0):
        return B
    else:
        return gcd(B,A%B)

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

ans = 1
for i in range(2,math.ceil(math.sqrt(G))+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:
import math

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

def gcd(a, b):
    if a % b == 0 or b % a == 0:
        return min(a, b)
    else:
        if a // b >= b // a:
            c = abs(a - b * (a // b))
        else:
            c = abs(b - a * (b // a))
        d = min(a, b)
        return gcd(c, d)

gcd_ = gcd(a, b)
d = []
for i in range(1, max(4, int(math.sqrt(gcd_))+1)):
    if not gcd_ % i:
        d.extend([i, gcd_ // i])

d.sort()
while d != [] and d[0] == 1:
    del d[0]
ans = [1]

for i in d:
    for j in ans:
        if gcd(i, j) == 1 and j == ans[-1]:
            ans.append(i)
        elif gcd(i, j) != 1:
            break

print(len(ans))

Submission status: Accepted

Solution code:
A,B=map(int,input().split())
lst=set()
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

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

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

    return arr

if A==B==1:
    print(1)
else:
    print(len(set([i[0] for i in factorization(A)])&set([i[0] for i in factorization(B)]))+1)

Submission status: Accepted

Solution code:
#[正の約数]の1次元リスト

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


#[素因数]の1次元リスト

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


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

D_A = divisors(A)
D_B = divisors(B)

common_div = []
for _ in D_B:
	if _ in D_A:
		common_div.append(_)

m = max(common_div)
f = factorize(m)
print(len(f))

Submission status: Accepted

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

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

def 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

G = gcd(A,B)
if G == 1:
    print(1)
else:
    H = factorization(G)
    print(len(H)+1)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from math import sqrt

a,b = map(int,input().split())
 
L = []
 
if a < b: a,b = b,a
while b!=0:
    r = a%b
    a,b = b,r
 
G = a
 
for i in range(2,int(sqrt(G))+1):
    if G%i==0:
        L.append(i)
        while G%i==0:
            G/=i

if G!=1:
    L.append(G)

print(len(L)+1)

Submission status: Accepted

Solution code:
import fractions
import math
A,B=map(int, input().split())
n=fractions.gcd(A, B)
divisors = []
for i in range(1, int(n**0.5)+1):
    flag=-1
    lag=-1
    if n % i == 0:
      flag=0
      for j in range(2, int(i**0.5)+1):
        if i%j==0 and i!=j:
          flag=1
          break
      if i != n // i :
        lag=0
        for j in range(2, int((n // i)**0.5)+1):
          if (n // i)%j==0 and i!=j:
            lag=1
            break
    if flag==0:
      divisors.append(i)
    if lag==0:
      divisors.append(n//i)
#flag=0
#print(divisors)
#for j in range(2, int(n**0.5)+1):
#    if n%j==0:
#     flag=1
 #     break
#if flag==0:
 #     divisors.append(n)
print(len(divisors))

Submission status: Accepted

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

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

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

    elif n == 1:
        arr = []

    return arr


A,B = map(int,input().split())
a = factorization(A)
b = factorization(B)
check = 1
for i in range(0,len(a)):
    for j in range(0,len(b)):
        if a[i][0] == b[j][0]:
            check += 1
print(check)

Submission status: Accepted

Solution code:
# 2019-11-18 23:58:23(JST)
import sys
# import collections
import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# import re
# import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
# import numpy as np 


def primeFactorize(n):
    from math import floor, sqrt
    res = set()
    before = n
    while n % 2 == 0:
        n //= 2
    if n < before:
        res.add(2)
    if n == 1:
        return res
    for i in range(3, floor(sqrt(n))+1, 2):
        before = n
        while n % i == 0:
            n //= i
        if n < before:
            res.add(i)
        if n == 1:
            return res
    res.add(n)
    return res

def main():
    a, b = [int(x) for x in sys.stdin.readline().split()]
    ans = len(primeFactorize(a) & primeFactorize(b)) + 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from fractions import gcd

def prime_factors(n):
    lst = []
    while n % 2 == 0:
        lst.append(2)
        n //= 2
    while n % 3 == 0:
        lst.append(3)
        n //= 3
    f = 5
    limit = int(n ** .5)
    while f <= limit:
        while n % f == 0:
            lst.append(f)
            n //= f
        f += 2
    if n != 1:
        lst.append(n)
    return lst

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

Submission status: Accepted

Solution code:
import fractions
a,b = map(int,input().split())
g = fractions.gcd(a,b)
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
fac = factorization(g)
ans = len(fac)
if fac[0][0] != 1: ans += 1
print(ans)

Submission status: Accepted

Solution code:
import math
import fractions

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())
k=fractions.gcd(a,b)

F=factorization(k)
if F==[[1,1]]:
  print(1)
else:
  print(len(F)+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

LA = set(prime_factorize(A))
LB = set(prime_factorize(B))
ans = list(LA & LB)
print(len(ans)+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

# nの約数のlist
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(q):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False
    return pow(2, q-1, q) == 1


a, b = map(int, input().split())
d_a = set(prime_factorize(a))
d_b = set(prime_factorize(b))
matched_list = list(d_a & d_b)
matched_list.sort()

count = 0

for i in matched_list:
    if is_prime(i):
        count += 1

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

    if temp!=1:
        arr.append(temp)

    if arr==[]:
        arr.append(n)

    return arr
aa,bb=factorization(a),factorization(b)
cnt=0
for i in aa:
  if i in bb:
    cnt+=1
if a==1 and b==1:
  print(1)
else:
  print(cnt+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
   
print(len(set(prime_factorize(a)) & set(prime_factorize(b))))

Submission status: Accepted

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

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


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

g = gcd(a, b)
ans = set(factorize(g))

print(len(ans)+1)

Submission status: Accepted

Solution code:
import fractions

def factor(x):
  t = x
  p = [1]
  for i in range(2, -int(-x**0.5//1)+1):
    if x % i == 0:
      p.append(i)
      while x % i == 0:
        x /= i
  if x != 1:
    p.append(x)
  if len(p) == 1 and t != 1:
    p.append(t)
  return p

A, B = list(map(int, input().split()))
d = fractions.gcd(A, B)
p = factor(d)
print(len(p))
#p = factorization(d)
#print(p)
#print(len(p) + (0 if p[0][0] == 1 else 1))

Submission status: Accepted

Solution code:
import fractions

def factor(x):
  t = x
  p = [1]
  for i in range(2, -int(-x**0.5//1)+1):
    if x % i == 0:
      p += [i]
      while x % i == 0:
        x /= i
  if x != 1:
    p += [x]
  if len(p) == 1 and t != 1:
    p += [t]
  return p

A, B = list(map(int, input().split()))
d = fractions.gcd(A, B)
p = factor(d)
print(len(p))
#p = factorization(d)
#print(p)
#print(len(p) + (0 if p[0][0] == 1 else 1))

Submission status: Accepted

Solution code:
import fractions

def factor(x):
  t = x
  p = [1]
  for i in range(2, -int(-x**0.5//1)+1):
    if x % i == 0:
      p += [i]
      while x % i == 0:
        x /= i
  if len(p) == 1 and t != 1:
    p += [t]
  return p

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 = list(map(int, input().split()))
d = fractions.gcd(A, B)
#p = factor(d)
p = factorization(d)
#print(p)
print(len(p) + (0 if p[0][0] == 1 else 1))

Submission status: Accepted

Solution code:
def prime_factorize(x, n):
    while n % 2 == 0:
        x.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            x.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        x.append(n)

A, B = map(int, input().split())
a = []
b = []
prime_factorize(a, A)
prime_factorize(b, B)
k = set(a) & set(b)
print(len(k) + 1)

Submission status: Accepted

Solution code:
import fractions

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
  
a,b = map(int, input().split())
GCD = fractions.gcd(a,b)
print(len(factorize(GCD)) + 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())

C=prime_decomposition(A)
D=prime_decomposition(B)
E=list(set(C)&set(D))
print(len(E)+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(i) for i in input().split()]
a,b = prime_factorize(A),prime_factorize(B)

data = set(a) & set(b)
data.add(1)

print(len(data))

Submission status: Accepted

Solution code:
from fractions import gcd
from collections import Counter

def prime_factorize(n):
    a=[]
    while n%2 == 0:
        a.append(2)
        n//=2
    f=3
    while f*f <= n:
        if n%f ==0:
            a.append(f)
            n//=f
        else:
            f+=2 # +1だと2の倍数にもなっちゃうからね
    if n!=1:
        a.append(n)
    return a

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

ab = gcd(a,b)
soinsu = prime_factorize(ab)
sosu = Counter(soinsu).keys()

print(len(sosu)+1)