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:
#https://atcoder.jp/contests/abc142/tasks/abc142_d

def prime_factorize(n):
    a = []
    a.append(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)
    
    b = [[],[]]
    cnt = 1
    for i in range(len(a)+1):
        if i > 0 and i < len(a):
            if a[i] == a[i-1]:
                cnt += 1
            else:
                b[0].append(a[i-1])
                b[1].append(cnt)
                cnt = 1
        if i == len(a) and i > 0:
            b[0].append(a[i-1])
            b[1].append(cnt)
        elif i == len(a) and i == 0:
            b[0].append(a[i])
            b[1].append(cnt)
    return a, b


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

apa, ap = prime_factorize(a)
bpa, bp = prime_factorize(b)

c = [[],[]]

for i in range(len(ap[0])):
    for j in range(len(bp[0])):
        if ap[0][i] == bp[0][j]:
            c[0].append(ap[0][i])
            c[1].append(min(ap[1][i],bp[1][j]))
            break

print(len(c[0]))

Submission status: Accepted

Solution code:
import sys
from itertools import combinations
from fractions import gcd

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

input = sys.stdin.readline
A,B= map(int,input().split())
mem = {}
com_divs = list(set(get_divs(A)).intersection(get_divs(B)))
if len(com_divs) == 1:
  print(1)
  exit()

ans = 1
for div in com_divs:
  if len(get_divs(div)) == 2: ans += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

from math import sqrt

def gcd(x, y):
    while y > 0:
        x, y = y, x%y
    return x
a,b = [int(i) for i in input().split()]

x = gcd(a,b)
res = 0
if (x % 2 == 0):
    res += 1
    while (x % 2 == 0):
        x = x / 2

k = int(sqrt(x)) + 1
for i in range(3, k, 2):
    if (x % i == 0):

        res += 1
        while (x % i == 0):
            x = x / i

if (x > 2):
    res += 1
print(res+1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 28 18:51:59 2019
ABC142D
@author: maezawa
"""
import collections

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

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

# making a prime number list
np = int(10**6+1) # prime number list less than np
is_prime = [True]*(np+1)

is_prime[0] = False
is_prime[1] = False

for i in range(2, np//2+1): # Sieve of Eratosthenes
    if is_prime[i] == True:
        for j in range(2*i,np+1,i):
            is_prime[j] = False

prime_numbers = [i for i in range(np+1) if is_prime[i]]

# prime factorization
num = gcdab#10**9+7 # a number to be factorized. 
# The maximum number to factrize is np**2. 

facts = [] # list of prime factors
for prime in prime_numbers:
    if prime > num//2:
        break
    dnum = num
    while dnum%prime == 0: 
        facts.append(prime)
        dnum = dnum//prime

mul = 1
for i in facts:
    mul *= i
if mul != num: # if large prime number (> np) is missing
    facts.append(num//mul) # append it

pfs = collections.Counter(facts)
print(len(pfs)+1)

Submission status: Accepted

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


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


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

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

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

    return arr


print(len(factorization(gcd(A, B))) + 1)

Submission status: Accepted

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

lst = []
for i in range(1, int(n**0.5)+1):
    if n % i == 0:
        lst.append(i)
        if i != n // i:
            lst.append(n//i)
lst.sort()
cnt = []
for i in range(1, len(lst)):
    if lst[i] == 2:
        cnt.append(lst[i])
    flag = 0
    for j in cnt:
        if lst[i]%j == 0:
            flag = 1
            break
    if flag == 0:
        cnt.append(lst[i])
print(len(cnt) + 1)

Submission status: Accepted

Solution code:
import math


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


def f(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


def main():
    # return
    # N = int(input())
    # N,= [int(a) for a in input().split()]
    A, B = [int(a) for a in input().split()]

    gcd = gcdf(A, B)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from fractions import gcd as bltin_gcd

def coprime2(a, b):
    return bltin_gcd(a, b) == 1

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 main():
	[a,b]=[int(x) for x in input().split()]
	kouyakusuu=list(set(make_divisors(a))&set(make_divisors(b)))
	kouyakusuu.sort()
	ans=[1,]
	for item in kouyakusuu[1:]:
		if all([coprime2(item,x) for x in ans])==True:
			ans.append(item)
	#print(ans)
	print(len(ans))
    

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import fractions

def read():
    A, B = map(int, input().strip().split())
    return 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)
    return divisors

def solve(A, B):
    gcd = fractions.gcd(A, B)
    divisors = sorted(make_divisors(gcd))
    table = [True] * len(divisors)
    for i in range(1, len(divisors)):
        for j in range(i+1, len(divisors)):
            if table[j] and divisors[j] % divisors[i] == 0:
                table[j] = False
    divisors = [divisors[i] for i in range(len(divisors)) if table[i]]
    return len(divisors)

if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))

Submission status: Accepted

Solution code:
def main():
    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])
        arr = [(i,j) for i,j in arr]
        return arr
    
    a,b = map(int,input().split())
    fa = dict(factorization(a))
    fb = dict(factorization(b))
    fak = set(fa.keys())
    fbk = set(fb.keys())
    if a == 1 and b == 1:
        print(1)
    else:
        print(len(fak&fbk)+1)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#ABC142D
import sys
import math
import collections
#sys.setrecursionlimit(100000)

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

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

#n=int(input())
tmp = input().split()
a,b = list(map(lambda a: int(a), tmp))


tmp=gcd(a,b)
c = collections.Counter(prime_factorize(tmp))

#print(c.keys())
print(len(c.keys())+1)

Submission status: Accepted

Solution code:

from math import sqrt

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

def calc(a,b):
    x = gcd(a,b)
    res = 0
    if (x % 2 == 0):
        res += 1

        # Print the number of 2s that divide x
        while (x % 2 == 0):
            x = x / 2

    # x must be odd at this point. So we
    # can skip one element (Note i = i +2)
    k = int(sqrt(x)) + 1
    for i in range(3, k, 2):
        if (x % i == 0):

            # While i divides x, print i
            # and divide x
            res += 1
            while (x % i == 0):
                x = x / i

                # This condition is to handle the
    # case when x is a prime number
    # greater than 2
    if (x > 2):
        res += 1
    return res



# Driver code
if __name__ == '__main__':
    a,b = [int(i) for i in input().split()]
    print(calc(a, b)+1)

# This code is contributed by
# Surendra_Gangwar

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 tmp in factorization(a):
    num = tmp[0]
    if num not in a_set:
        a_set.add(num)
b_set = set()
for tmp in factorization(b):
    num = tmp[0]
    if num not in b_set:
        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:
from fractions import gcd

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

factors = []
while ab_gcd % 2 == 0:
  factors.append(2)
  ab_gcd //= 2
f = 3
while f * f <= ab_gcd:
  if ab_gcd % f == 0:
    factors.append(f)
    ab_gcd //= f
  else:
    f += 2
if ab_gcd != 1:
  factors.append(ab_gcd)
  
print(len(set(factors)) + 1)

Submission status: Accepted

Solution code:
A,B = (int(i) for i  in input().split())
from math import sqrt
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
divisors = make_divisors(gcd(A,B))
def is_prime(n):
    if n == 1: return True
    for k in range(2, int(sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True
ans = 0
for d in divisors:
    ans += is_prime(d)
print(ans)

Submission status: Accepted

Solution code:
import math

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

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

    return True

def divisor(n):
    yakusuu = set()
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            yakusuu.add(i)
            yakusuu.add(n//i)
    return yakusuu

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

Adiv = divisor(A)
Bdiv = divisor(B)

commondivisor = Adiv & Bdiv

count = 1
for a in commondivisor:
    if is_prime(a):
        count += 1

print(count)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

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

def divisor(a, b):
    if a < b:
        b, a = a, b
    res = []
    ra = int(a**0.5) + 1 
    for i in range(1, ra):
        if a % i == 0:
            if b % i == 0:
                res.append(i)
                if i != a / i and b % (a/i) == 0:
                    res.append(int(a / i))
            else:
                if i != a / i and b % (a/i) == 0:
                    res.append(int(a / i))
    return sorted(res)

Y = divisor(A, B)

ans = 0
for i in range(len(Y)):
    if is_prime(Y[i]):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import fractions
A,B=list(map(int,input().split()))
gcd=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
so=factorization(gcd)
ans=[i[0] for i in so]
#print(ans)
if 1 in ans:
    print(len(so))
else:
    print(len(so)+1)

Submission status: Accepted

Solution code:
import math
def factrial(n):
    factor = set()
    for i in range(1, int(math.sqrt(n)+1)):
        if n % i == 0:
            factor.add(i)
            factor.add(n//i)
    return factor

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

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

fact_a = factrial(a)
fact_b = factrial(b)
fact_int = sorted(list(fact_a & fact_b))

choice = []
for i in fact_int:
    prime = True
    for j in choice:
        if gcd(i, j) != 1:
            prime = False
            break
    if prime:
        choice.append(i)

print(len(choice))

Submission status: Accepted

Solution code:
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())
gcd = fractions.gcd(A,B)
tgt = factorization(gcd)
if tgt == [[1,1]]:
    print(1)
    exit()
print(len(tgt)+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)

    # divisors.sort()
    return divisors


def check_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if len(divisors) > 2:
                return False
            if i != n // i:
                divisors.append(n//i)
    return True


a, b = map(int, input().split())
a_list = make_divisors(a)
b_list = make_divisors(b)
div = set(a_list) & set(b_list)
count = 0

for i in div:
    if check_divisors(i):
        count += 1
print(count)

Submission status: Accepted

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

a,b=map(int,input().split())
A=set(z(a))
B=set(z(b))
c=[i for i in A if i in B]
print(len(c)+1)

Submission status: Accepted

Solution code:
import fractions

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

pf={}
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1
print(len(pf) + 1)

Submission status: Accepted

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

while a!=0 and b!=0:
    a,b = max(a,b),min(a,b)
    a %= b

# print(b)

bb = b

ans = 1
i = 2
end = int((b+1)**0.5)+2
while i < end:
    t = 0
    while b % i == 0:
        b //= i
        # print(b)
        t = 1
        end = int((b+1)**0.5)+2
        if b==1:
            break
    ans += t
    if b==1:
        break
    i += 1

if b != 1 and bb != 1:
    ans += 1
    
print(ans)

Submission status: Accepted

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

tmp_A = set(make_divisors(A))
tmp_B = set(make_divisors(B))

tmp_set = tmp_A & tmp_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

print(sum([is_prime(one) for one in tmp_set])+1)

Submission status: Accepted

Solution code:
def divisors(N):
    U = int(N ** 0.5) + 1
    L = [i for i in range(1, U) if N % i == 0]
    return L + [N // i for i in reversed(L) if N != i * i]

def is_prime(N):
    if N < 2 or N % 2 == 0:
        return (N == 2)
    i = 3
    while i * i <= N:
        if N % i == 0:
            return False
        i += 2
    return True

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

if A > B:
    A, B = B, A

D = divisors(A)

ans = 0
for d in D:
    if B % d == 0 and is_prime(d):
        ans += 1

print(ans + 1)

Submission status: Accepted

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

aa = set()
bb = set()

waru = 2
while waru ** 2 <= a:
    if a % waru == 0:
        aa.add(waru)
        a = a // waru
        continue
    waru += 1

aa.add(a)
aa.add(1)

waru = 2
while waru ** 2 <= b:
    if b % waru == 0:
        bb.add(waru)
        b = b // waru
        continue
    waru += 1

bb.add(b)
bb.add(1)


print(len(aa & bb))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
A, B = map(int, input().split())

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

def fac(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

gcdv = gcd(A, B)
l = fac(gcdv)
ans = len(l)

if ans == 1:
    if l[0][0] == 1:
        print(1)
    else:
        print(ans+1)
else:
    print(ans+1)

Submission status: Accepted

Solution code:
a, b = list(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

aset = set(prime_factorize(a))
bset = set(prime_factorize(b))

print(len(aset & bset) + 1)

Submission status: Accepted

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

a_list = [1, a]
c = 2
while c <= a**0.5:
    if a%c == 0:
        a_list.append(a//c)
        a_list.append(c)
    c += 1
        
b_list = [1, b]
d = 2
while d <= b**0.5:
    if b%d == 0:
        b_list.append(b//d)
        b_list.append(d)
    d += 1
        
a_set = set(a_list)
b_set = set(b_list)
ans_list = list(a_set & b_set)

def prime(n):
    i = 2
    jud = 0
    while i <= n**0.5:
        if n%i == 0:
            jud = 1
            break
        i += 1
    return jud

ans = 0
for i in range(len(ans_list)):
    if prime(ans_list[i]) == 0:
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
def gcd(x,y):
    r=x%y
    while r>0:
        r=x%y
        if r ==0: 
            return y
        else:
            q=y
            x=q
            y=r
    return y
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 = list(map(int, input().split()))
c = gcd(a,b)



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

Submission status: Accepted

Solution code:
import math
#試し割法
def trial_division(n):
    #素因数を格納するリスト
    factor = []
    #2から√n以下の数字で割っていく
    tmp = int(math.sqrt(n)) + 1
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    #リストが空ならそれは素数
    if not factor:
        return [-1]
    else:
        factor.append(n)
        return factor
    return [-1]

a,b = input().split(' ')
a = int(a)
b = int(b)
aSet = trial_division(a)+[1]
bSet = trial_division(b)+[1]
if aSet[0] == -1:
    aSet = [1,a]
if bSet[0] == -1:
    bSet = [1,b]
aSet= set(aSet)
bSet = set(bSet)
ngo = aSet&bSet
print(len(ngo))

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def divisor_set(N: int) -> set:
    """ 約数の列挙・個数 """
    from math import sqrt

    # 1とその数はデフォで入れとく
    s = {1, N}
    # 終点はルート切り捨て
    for i in range(2, int(sqrt(N))+1):
        # 割り切れるなら、iとN/iを追加
        if N % i == 0:
            s.add(i)
            s.add(N // i)
    return s

def is_prime(num):
    """ 素数判定 """
    from math import sqrt

    if num < 2: 
        return False
    if num in [2, 3, 5]: 
        return True
    if num % 2 == 0 or num % 3 == 0 or num % 5 == 0:
        return False
    # 疑似素数(2でも3でも割り切れない数字)で次々に割っていく
    prime = 7
    step = 4
    num_sqrt = sqrt(num)
    while prime <= num_sqrt:
        if num % prime == 0:
            return False
        prime += step
        step = 6 - step
    return True

A, B = MAP()

adivs = divisor_set(A)
bdivs = divisor_set(B)
divs = adivs & bdivs

ans = 1
for div in divs:
    if is_prime(div):
        ans += 1

print(ans)

Submission status: Accepted

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

N=gcd(a,b)
res = set()
x = N
y = 2
while y*y <= x:
    while x % y == 0:
        res.add(y)
        x //= y
    y += 1
if x > 1:
    res.add(x)


print(len(res)+1)

Submission status: Accepted

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

g = fractions.gcd(a, b)
l = defaultdict(int)
for i in range(2, int(g**0.5)+1):
    if g % i == 0:
        while g % i == 0:
            l[i] += 1
            g = g // i
if g != 1:
    l[g] += 1
print(len(l)+1)

Submission status: Accepted

Solution code:
from fractions import gcd
import collections

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

def factorization(n):
    arr = set()
    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

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

Submission status: Accepted

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

if A == 1 or B == 1:
    print(1)
    sys.exit()


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

lis_a = prime_factorize(A)
lis_b = prime_factorize(B)
lis_a.append(1)
lis_b.append(1)
ans = len(set(lis_a) & set(lis_b))
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import math


def make_prime_list(num):
    if num < 2:
        return []
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0
    num_sqrt = math.sqrt(num)
    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break
        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0
    return [prime for prime in prime_list if prime != 0]


def prime_factorization(num):
    if num <= 1:
        return {}
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list(num_sqrt)
        dict_counter = defaultdict(int)
        for prime in prime_list:
            while num % prime == 0:
                dict_counter[prime] += 1
                num //= prime
        if num != 1:
            dict_counter[num] += 1
        dict_counter = dict(dict_counter)
        return dict_counter


a, b = map(int, input().split())
buf = a
while buf!=0:
    a,b=b,buf
    buf=a%b
print(len(prime_factorization(b))+1)

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
GCD = 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
ps = prime_factorize(GCD)
ps_uniq = list(set(ps))
print(len(ps_uniq)+1)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
import heapq
import bisect
import itertools

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def LI_(): return([int(x)-1 for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

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

def LCM(a,b):
    return a * b // GCD(a,b)

def Eratosthenes(N):
    r = [True]*(N+1)
    r[0] = False
    r[1] = False
    i = 2
    while i*i<=N:
        if r[i]: 
            j = i
            while i*j<=N:
                prime[i*j]=False
                j+=1
        i+=1
    return(r)

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

def main():
    A,B = LI()
    GCD_AB = GCD(A,B)
    if GCD_AB == 1:
        return 1
    arr = factorization(GCD(A,B))
    return(len(arr)+1)

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

Submission status: Accepted

Solution code:
import fractions
import math

def isPrime(n):
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    m = math.floor(math.sqrt(n)) + 1
    for p in range(3, m, 2):
        if n % p == 0:
            return False
    return True


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


a, b = map(int, input().split())
n = set(divisor(a)) & set(divisor(b))
r = len(n)
cnt = 0
for i in n:
    if isPrime(i):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
a, b = [int(i) for i in input().split()]
l = [1]
if a%2==0:
  l.append(2)
while(a%2==0):
  a/=2

i = 3
while(a>i**2):
  if a%i==0:
    l.append(i)
  while(a%i==0):
    a/=i
  i+=2
if a not in l:
  l.append(a)
cnt = 0
for i in l:
  if b%i==0:
    cnt += 1
print(cnt)

Submission status: Accepted

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


def coprime(a, b):
    return gcd(a, b) == 1


ans = 0
P = make_divisors(a)
Q = make_divisors(b)

kou = list(set(P) & set(Q))
n = len(kou)


ans = []
kou.sort()
for k in kou:
    flag = True
    for i in range(len(ans)):
        if coprime(ans[i], k) is False:
            flag = False
    if flag is True:
        ans.append(k)
print(len(ans))

Submission status: Accepted

Solution code:
import math

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(math.sqrt(n))+3):
        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()]
import fractions
gcd = fractions.gcd(a,b)
factors = factorization(gcd)
if factors ==[[1,1]]:
    print(1)
else:
    print(len(factors)+1)

Submission status: Accepted

Solution code:
def gcm(a,b):
    if a < b:
        a,b = b,a
    while True:
        if a % b == 0:
            return b
        else:
            a,b = 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())
gcm1 = gcm(A,B)
prime = prime_factorize(gcm1)
primeset = set()
for p in prime:
    primeset.add(p)

print(len(primeset)+1)