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:
def gcd(a,b):
    if a<b:
        tmp = a
        a = b
        b = tmp
    while a!=b and b!= 0:
        c = a%b
        a = b
        b = c
    return a

a,b = list(map(int,input().split()))
g = gcd(a,b)
ans = 1
d = []
p = []
for i in range(1,int(g**0.5)+1): #因数リスト
    if g%i==0:
        if i!=1:
            d.append(i)
        if g//i!=1:
            d.append(g//i)
d = list(dict.fromkeys(d))
        
f = [True]*len(d)
for i in range(len(d)):
    for j in range(i):
        if d[i]>d[j] and d[i]%d[j]==0:
            f[i] = False
        if d[i]<d[j] and d[j]%d[i]==0:
            f[j] = False
print(f.count(True)+1)

Submission status: Accepted

Solution code:
import math

divisor=[1]
stack=[]
#eiclidean algorithm
A,B=map(int,input().split())
p=max(A,B)
q=min(A,B)
int2=0
gcd=0
while True:
    int2=p%q
    if int2==0:
        gcd=q
        break
    else:
        p=q
        q=int2

if gcd!=1:
    stack.append(gcd)
    
for i in range(2,math.ceil(math.sqrt(gcd))+1):
    if gcd%i==0:
        p=gcd//i
        stack.append(p)
        for x in divisor:
            if i%x==0 and x!=1:
                break
        else:
            divisor+=[i]

while len(stack)!=0:
    p=stack.pop()
    for x in divisor:
        if p%x==0 and x!=1:
            break
    else:
        divisor+=[p]


print(len(divisor))

Submission status: Accepted

Solution code:
from fractions import gcd
 
d = gcd(*map(int, input().split()))
r = 1
i = 2
while i * i <= d:
    c = 0
    while d % i == 0:
        c += 1
        d //= i
    if c: r += 1
    i += 1
print(r + (d > 1))

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)
scr = gcd(A, B)
import collections
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
b= prime_factorize(scr)
c = collections.Counter(b)
b_se = set(b)
b_li = list(b_se)
d = len(b_se)
print(d+1)

Submission status: Accepted

Solution code:
import math

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

# 試し割り法(2以外の偶数は捨てる方法を追加)
def check_prime(n):
    flag = True

    # n:evenかつ2でないならば素数でない
    # n=1は素数でない,n=0も実装しやすいように入れておく
    if (n % 2 == 0 and n != 2) or n == 0 or n == 1:
        flag = False
        return(flag)

    # n:oddまたは2のときは考える
    else:
        # 2からrootnまでに約数は存在しうる
        for i in range(2, math.floor(math.sqrt(n))+1):
            if n % i == 0:
                flag = False
                break
        return(flag)

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

div = make_divisors(min(A, B))

div2 = []
for n in div:
    if check_prime(n):
        div2.append(n)

cnt = 1
for n in div2:
    if max(A, B) % n == 0:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import fractions
import math
a,b = [int(i) for i in input().split()]

gcd = fractions.gcd(a,b)

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

l = make_divisors(gcd)

print(len([i for i in l if is_prime(i)]) +1)

Submission status: Accepted

Solution code:
from fractions import gcd
 
d = gcd(*map(int, input().split()))
r = 1
i = 2
while i * i <= d:
    c = 0
    while d % i == 0:
        c += 1
        d //= i
    r += c > 0
    i += 1
print(r + (d > 1))

Submission status: Accepted

Solution code:
from fractions import gcd
 
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 isPrime(n):
  if n < 2:
    # 2未満は素数でない
    return False
  if n == 2:
    # 2は素数
    return True
  for p in range(2, int(n**0.5)+1):
      if n % p == 0:
        # nまでの数で割り切れたら素数ではない
        return False
  # nまでの数で割り切れなかったら素数
  return True
 
A,B = list(map(int,input().split()))
 
aaa = []
 
aaa = make_divisors(gcd(A,B))
        
count = 0
 
for i in range(len(aaa)):
    if isPrime(aaa[i]) == True:
        count += 1
        
print(count+1)

Submission status: Accepted

Solution code:
from fractions import gcd
d = gcd(*map(int, input().split()))
r = 1
i = 2
while i * i <= d:
    r += d % i == 0
    while d % i == 0:
        d //= i
    i += 1
print(r + (d > 1))

Submission status: Accepted

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


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

    return arr


af = factorization(A)
bf = factorization(B)
ans = 0
for afi in af:
    if afi in bf:
        ans += 1
print(ans)

Submission status: Accepted

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

if A>B:
    t=A
    A=B
    B=t

A_div=[]
AB_div=[]
front=[]
back=[]
for i in range(1, int(A**0.5)+1):
    if A % i == 0:
        front.append(i)
        if i != A // i:
            back.insert(0,A//i)
A_div=front+back
# print(A_div)
for n in A_div:
    if(B%n==0):
        AB_div.append(n)
# print(AB_div)

for i in AB_div:
    if i==1:
        continue
    # exit内にあるかどうか
    for j in reversed(AB_div):
        if j%i==0 and j>i:
            # print(j)
            AB_div.remove(j)
# print(AB_div)
print(len(AB_div))

Submission status: Accepted

Solution code:
def main():
    A,B = map(int,input().split())
    import fractions
    C = fractions.gcd(A,B)
    cnt = 0
    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
    def is_prime(n):
        if n == 1:
            return True
        for i in range(2,int(n**0.5)+1):
            if n % i == 0:
                return False
        return True
    
    C_2 = make_divisors(C)
    
    for i in C_2:
        if is_prime(i):
            cnt += 1
    print(cnt)
    
    


    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
c=[]
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
d=gcd(a,b)
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
e=make_divisors(d)
y=0
n=len(e)
for i in range(n):
    x=0
    for j in range(n):
        if e[i]%e[j]!=0:
            x+=1
        elif e[j]!=1 and i!=j:
            break
    if x==n-2:
        y+=1
print(y+1)

Submission status: Accepted

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

def getPrimeFactors(x):
    ans = []
    for d in range(2, int(x**0.5)+1):
        while x%d == 0:
            ans.append(d)
            x //= d
    if x != 1:
        ans.append(x)
    return ans

pfAs = [1] + getPrimeFactors(A)
pfBs = [1] + getPrimeFactors(B)

ans = len(set(pfAs) & set(pfBs))
print(ans)

Submission status: Accepted

Solution code:
import fractions

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

G = fractions.gcd(A, B)

res = 1

for i in [2] + list(range(3, int(G ** 0.5) + 1, 2)):
    if G % i == 0:
        res += 1
        while G % i == 0:
            G //= i

if G > 2:
    res += 1

print(res)

Submission status: Accepted

Solution code:
from fractions import gcd
 
d = gcd(*map(int, input().split()))
r = 1
i = 2
while i * i <= d:
    r += d % i == 0
    while d % i == 0:
        d //= i
    i += 1
print(r + (d > 1))

Submission status: Accepted

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

A,B=map(int,input().split())
a = divisor(A)
b = divisor(B)
ab = list(set(a) & set(b))
#print(ab)

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

ans = 0
for j in ab:
    if is_prime(j)==True:
        ans += 1
print(ans+1)

Submission status: Accepted

Solution code:
import collections
a, b = map(int, input().split())
def gcd(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

n = gcd(a, b)
c = collections.Counter(prime_factorize(n))
print(len(c.keys())+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
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

a, b = map(int,input().split())
a_set = set()
for num, _ in factorization(a):
    a_set.add(num)
b_set = set()
for num, _ in factorization(b):
    b_set.add(num)
ans = a_set & b_set
if 1 not in ans:
    ans.add(1)
print(len(ans))

Submission status: Accepted

Solution code:
import fractions
import math

def primefact(n):
    facts = []
    prime = True
    while n > 1:
        for d in xrange(2,int(math.sqrt(n))+1):
            if n%d == 0:
                facts.append(d)
                n /= d
                prime = False
                break
        if prime:
            facts.append(n)
            n = 1
        prime = True
    return facts

a,b = map(int,raw_input().split())
g = fractions.gcd(a,b)
facts = set(primefact(g))
print len(facts)+1

Submission status: Accepted

Solution code:
n,k = 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

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

n_set=set(factorize(n))
k_set=set(factorize(k))
c_set=n_set&k_set
c=list(c_set)
print(len(c)+1)

Submission status: Accepted

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

listA = make_divisors(A)
listB = make_divisors(B)
lst = list(set(listA) & set(listB))

lst.sort()

if len(lst) == 1:
    print(1)
else:
    check = [lst[1]]
    for i in range(1, len(lst)):
        for c in check:
            if lst[i] % c == 0:
                break
        else:
            check.append(lst[i])
    print(len(check)+1)

Submission status: Accepted

Solution code:
import sys
def divisor(a,b): #nの約数を全て求める
  if a>b:
  	a,b = b,a
  i = 2
  table = []
  table2 = []
  table3 = []
  
  while i * i <= min(a**2,b):
    if a%i==0:
      table2.append(a//i)
      if b%i==0:
        table.append(i)
        table3.append(b//i)
    else:
      if b%i==0:
        table3.append(b//i)
    i += 1
    
  table2.append(a)
  table3.append(b)
  #print(table)
  #print(table2)
  #print(table3)
  s_inter = set(table) | (set(table2) & set(table3))
  table = list(s_inter)
  return table

 
a,b = map(int, input().split())
if a==1 and b==1:
  print(1)
  sys.exit(0)
if a>b:
  a,b = b,a

ret = divisor(a,b)
#print(ret)
if 2 in ret:
  ret = [2] + [t1 for t1 in ret if t1%2!=0]
elif 3 in ret:
  ret = [3] + [t1 for t1 in ret if t1%3!=0]
elif 5 in ret:
  ret = [5] + [t1 for t1 in ret if t1%5!=0]
elif 7 in ret:
  ret = [7] + [t1 for t1 in ret if t1%7!=0]
elif 11 in ret:
  ret = [11] + [t1 for t1 in ret if t1%11!=0]
elif 13 in ret:
  ret = [13] + [t1 for t1 in ret if t1%13!=0]

ret = [t1 for t1 in ret if sum([t1%t2==0 for t2 in ret])==1]
#print(ret)
print(1+len(ret))

Submission status: Accepted

Solution code:
import math

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

def common_divisor(n):
  if n == 1:
    return [1]
  ret = []
  for i in range(1,math.ceil(math.sqrt(n))+1):
    if n%i==0:
      ret.append(i)
      ret.append(n//i)      
  return list(set(ret))

def trial_division(n):
    if n == 2:
        return True
    if n < 2 or n % 2 == 0:
        return False
    for i in range(3, int(math.ceil(math.sqrt(n))) + 1, 2):
        if n % i == 0:
            return False
    return True

ca = common_divisor(a)
cb = common_divisor(b)

sa = set(ca)
c = sa.intersection(cb)

count = 1
for ci in c:
  if trial_division(ci):
    count+=1

print(count)

Submission status: Accepted

Solution code:
import math

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

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

	return gcd(b, a%b)


G = gcd(A,B)


def sosuhantei(n):
	d = math.floor(n**(1/2))
	cond = True
	for i in range(2,d+1):
		if n % i == 0:
			cond = False
			break
	return cond 


sosu = []
g = math.ceil(G**(1/2)) 

yaku = []

for i in range(1,g+1):
	if G % i == 0:
		yaku.append(i)
		yaku.append(G//i)

yaku = list(set(yaku))

cnt = 0
for i in range(len(yaku)):
	if sosuhantei(yaku[i]):
		cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import random

def gcd(a,b):
        if b == 0:
                return a
        else:
                return gcd(b , a%b) 
def is_prime(q,k=50):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1

    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        while t != q-1 and y != 1 and y != q-1:
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

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

c = 1
m = gcd(a,b)

i = 1
while i * i <=m:
        if a%i == 0 and b%i == 0:
                if is_prime(i):
                        c+=1
                if is_prime(m//i):
                        c+=1
        i+=1
print(c)

Submission status: Accepted

Solution code:
A, B = [int(v) for v in input().split()]

def prime_factorize(n):
    a = set([1])
    while n % 2 == 0:
        a.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.add(n)
    return a
s1 = prime_factorize(A)
s2 = prime_factorize(B)
s3 = s1 & s2
print(len(s3))

Submission status: Accepted

Solution code:
from fractions import gcd
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())
a_d = make_divisors(a)
b_d = make_divisors(b)

yakusu = []

for i in a_d:
    if i in b_d:
        yakusu.append(i)

ans = [yakusu.pop(0)]
for i in yakusu:
    flg=0
    tmp = 0
    for j,num in enumerate(ans):
        if gcd(num,i) != 1:
            ans[j] = min(i,num)
            flg = 1
            break
    if flg == 0:
        ans.append(i)

print(len(ans))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math


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


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(int, input().split())
c = gcd(a, b)
d = factorize(c)
print(len(set(d))+1)

Submission status: Accepted

Solution code:
import math
def prime(n):
    set1 = set()
    while n % 2 == 0: 
        set1.add(2) 
        n = n / 2
    for i in range(3,int(math.sqrt(n))+1,2): 
        while n % i== 0: 
            set1.add(i)
            n = n / i 
    if n > 2: 
        set1.add(n)
    return set1

a,b = map(int, input().split())
ans1 = prime(a)
ans2 = prime(b)
ans3 = ans1.intersection(ans2)
print(len(ans3)+1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import os

import math
import random


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

#素因数分解
ap = list(set(prime_factorize(a)))
bp = list(set(prime_factorize(b)))

#print(ap, bp)

al = []
bl = []

al = ap
bl = bp

#for i in ap:
#    al.append(i)
#for i in bp:
#    bl.append(i)

if len(al) == 0 or len(bl) == 0:
    print(1)
else:
    print(len(list(set(al) & set(bl))) + 1)

Submission status: Accepted

Solution code:
from math import sqrt
def gcd(a,b):
	if a==0:
		return(b)
	return(gcd(b%a,a))
a,b=map(int,input().split())
g=gcd(a,b)
ans=1
if g%2==0:
	ans+=1
	while(g%2==0):
		g//=2
for divide in range(3,int(sqrt(g))+1,2):
	if g%divide==0:
		ans+=1
		while(g%divide==0):
			g//=divide
if g>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

x = gcd(A, B)

res = 1
temp = x
for i in range(2, int(-(-x**0.5//1))+1):
    if temp%i==0:
        cnt=0
        while temp%i==0:
            cnt+=1
            temp //= i
        res += 1

if temp!=1:
    res += 1

print(res)

Submission status: Accepted

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

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
D = factorize(C)

X = list(set(D))
print(len(X)+1)

Submission status: Accepted

Solution code:
import fractions

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

new_a = a//new_gcd
new_b = b//new_gcd

tmp = make_divisors(new_gcd)
tmp = list(set(tmp))
tmp.sort()

new_tmp = []
for i in range(len(tmp)):
    flg = 0
    for j in range(1,len(tmp)-i):
        if tmp[-i]%tmp[j]==0:
            flg = 1
            break
    if flg == 0:
        new_tmp.append(tmp[-i])
        
print(len(new_tmp))

Submission status: Accepted

Solution code:
from fractions import gcd

def answer():
    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())
    g = gcd(a, b)
    divisors = make_divisors(g)

    length = len(divisors)
    removed = 1

    for i in range(1, length):
        d1 = divisors[i]
        for d2 in divisors[i:-1]:
            if d1 * d2 in divisors:
                divisors.remove(d1*d2)
                removed += 1
        if i + removed >= length:
            break

    print(length - removed + 1)


if __name__ == '__main__':
    answer()

Submission status: Accepted

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

def main():
    r = input().split()
    a = int(r[0])
    b = int(r[1])
    dd = set(make_divisors(a)) & set(make_divisors(b))
    dd = sorted(list(dd))
    res = 0
    #print(dd)
    for i in dd:
        if i == 1:
            res += 1
            continue
        else:
            flag = True
            for j in dd:
                if j == 1:
                    continue
                if j < i and i % j == 0:
                    flag = False
                    break
            if flag:
                res += 1
    print(res)

main()

Submission status: Accepted

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

def common_divisors(a, b):
    cd = []
    n = min(a, b)
    m = max(a, b)
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if m % i == 0:
                cd.append(i)
            if i != n // i and m % (n//i) == 0:
                cd.append(n//i)
    return cd

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

def sieve(n):
    prime = []
    is_prime = [True]*(n+1)
    is_prime[0] = False
    is_prime[1] = False

    for i in range(2, n+1):
        if is_prime[i]:
            prime.append(i)
            for j in range(2*i, n+1, i):
                is_prime[j] = False
    return prime


cd = common_divisors(A, B)
#prime = sieve(max(cd))

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

#print(cd)
#print(max(cd))
#print(prime)

ans = 1 # 1は絶対入る
for a in cd:
    if is_prime(a):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
a, b = [int(i) for i in input().split(' ')]
gcd = gcd(a, b)

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

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

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

    return arr

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

Submission status: Accepted

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


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


ans = 1

tmp = make_divisors(fractions.gcd(A, B))

for x in tmp:
    if is_prime(x):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import fractions, math

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

def is_prime3(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True
  
A, B = map(int, input().split()) 
ans = set(make_divisors(A)) &  set(make_divisors(B))
print(sum([is_prime3(i) for i in ans])+1)

Submission status: Accepted

Solution code:

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

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

C = gcd(A,B)
E = make_divisors(C)
E.sort()

sosuu = []
ans = 0
for e in E:
    if e == 1:continue
    for s in sosuu:
        if e%s == 0:
            break
    else:
        sosuu.append(e)

print(len(sosuu)+1)

Submission status: Accepted

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

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

a, b = map(int, input().split())
p = primes(10 ** 6 +1)
ans = 1
g = gcd(a, b)
for pp in p:
    f = False
    while g % pp == 0:
        g = (g // pp)
        f = True
    if f:
        ans += 1
if g > 1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

a, b = [int(x) for x in stdin.readline().split()]

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

c = 1
lim = a ** 0.5 + 2
n = 0
i = 2
while a > 1 and i <= lim:
    n = 0
    while a % i == 0:
        a //= i
        n += 1
    if n > 0:
        c += 1
    i += 1
if a > 1:
    c += 1

print(c)

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 = [int(x) for x in input().split()]

max_gcd = fractions.gcd(A,B)
list_n = factorization(max_gcd)
if list_n == [[1,1]]:
    print(len(list_n))
else:
    print(len(list_n) + 1)

Submission status: Accepted

Solution code:
import math

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

    # divisors.sort()
    return divisors

def is_prime(n):
    if n == 1: return True

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

    return True

A, B = map(int, input().split())
AY = make_divisors(A)
BY = make_divisors(B)
AB = set(AY) & set(BY)
AB = list(AB)
cnt = [i for i in range(len(AB)) if is_prime(AB[i])]
print(len(cnt))

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())
la = prime_decomposition(a)
lb = prime_decomposition(b)
la_lb_and = list(set(la) & set(lb))
    
print(len(la_lb_and) + 1)

Submission status: Accepted

Solution code:
from fractions import gcd
a,b=map(int,input().split())
c=gcd(a,b)
d=1
for i in range(2, int(-(-gcd(a,b)**0.5//1))+1):
  if c%i==0:
    d+=1
    while c%i==0:
      c//=i
  if c==1:
    break
if c!=1:
  d+=1
print(d)

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:
            while temp%i==0:
                temp //= i
            arr.append(i)
    if temp!=1:
        arr.append(temp)

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

    return arr
aa=factorization(a)
bb=factorization(b)
n=len(aa)
ans=[]
if n>len(bb):
    n=len(bb)
    for i in range(n):
        if bb[i] in aa:
            ans.append(bb[i])
else:
    for i in range(n):
        if aa[i] in bb:
            ans.append(aa[i])
ans.append(1)
ans=set(ans)
print(len(ans))

Submission status: Accepted

Solution code:
from sys import stdin

a, b = [int(x) for x in stdin.readline().split()]

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

c = 1
lim = a ** 0.5 + 10
n = 0
i = 2
while a > 1 and i <= lim:
    n = 0
    while a % i == 0:
        a //= i
        n += 1
    if n > 0:
        c += 1
    i += 1
if a > 1:
    c += 1

print(c)

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
c=set(prime_factorize(A))
d=set(prime_factorize(B))
ans=len(c.intersection(d))
print(ans+1)

Submission status: Accepted

Solution code:
a,s=map(int,input().split())
def c(d,f):
  if d==0:return f
  else:return c(f%d,d)
  
j=c(a,s)
if j==1:print(1);exit()
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

print(len(factorization(j))+1)