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 factorization(n):
    arr = [[1,1]]
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.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(" ")))

val = min(A,B)
lim = int(val ** 0.5)


ms = factorization(min(A,B)) 
res = []
maxi = max(A,B)

for v, _ in ms:
    if maxi % v == 0:
        res.append(v)
print(len(res))

Submission status: Accepted

Solution code:
import math
import sys
a, b = map(int, input().split())
x = min(a, b)
y = max(a, b)

if x == 1:
    print(1)
    sys.exit()


d = []
for i in range(1, int(math.sqrt(x))+1):
    if x % i == 0:
        d.append(i)
        d.append(int(x/i))

zero = 0
for i in range(len(d)):
    if y % d[i] != 0:
        d[i] = 0
        zero += 1

if zero != 0:
    for i in range(zero):
        d.remove(0)

if len(d) == 1:
    print(1)
    sys.exit()

    
ans = 0
for i in range(len(d)):
    flag = 1
    for j in range(2, int(math.sqrt(d[i])) +1):
        if d[i] % j == 0:
            flag = 0
            break
    
    if flag == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from math import sqrt, floor

a, b = map(int, input().split())
mx, mi = max(a, b), min(a, b)

g = gcd(b, a % b)

div = []
for i in range(1, int(g**0.5)+1):
    if g % i == 0:
        div.append(i)
        if i != g // i:
            div.append(g//i)

def is_prime(x):
    if x == 2: return True
    if not x % 2: return False
    for j in range(3, floor(sqrt(x))+1, 2):
        if not x % j: return False
    else: return True

ans = 0
for d in div:
    ans += is_prime(d)

print(ans)

Submission status: Accepted

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

i = 1
j = 1
table_a = []
while i * i <= a:
    if a%i == 0:
        table_a.append(i)
        table_a.append(a//i)
    i += 1
table_a = list(set(table_a))

table_b = []
while j * j <= b:
    if b%j == 0:
        table_b.append(j)
        table_b.append(b//j)
    j += 1
table_b = list(set(table_b))

table = set(table_a) & set(table_b)
nums = list(table)

cnt = 0
for i in range(len(nums)):
    if is_prime(nums[i]):
        cnt += 1
print(cnt+1)

Submission status: Accepted

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


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

a=fr.gcd(A,B)
U=make_divisors(a)

JJ=0
for i in U:
    if is_prime(i)==True:
        JJ+=1
print(JJ+1)

Submission status: Accepted

Solution code:
import fractions

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

ans = prime_factorize(fractions.gcd(a, b))
ans = set(ans)
print(len(ans)+1)

Submission status: Accepted

Solution code:
a,b = map(int, input().split())
import fractions
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
myset={1}
mygcd=fractions.gcd(a,b)
myset=myset | set(prime_factorize(mygcd))
print(len(myset))

Submission status: Accepted

Solution code:
import math
a,b=map(int,input().split())
while b!=0:
    a,b=b,a%b
c=a
d=[]
for i in range(2,int(c**0.5)+2):
    while c%i==0:
        c//=i
        d.append(i)
if c!=1:
    d.append(c)
print(len(set(d))+1)

Submission status: Accepted

Solution code:
import fractions
import collections

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

a, b = map(int, input().split())
g = fractions.gcd(a, b)
c = collections.Counter(fact(g))

print(len(c)+1)

Submission status: Accepted

Solution code:
from fractions import gcd
from itertools import count, chain, product

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

g = gcd(A, B)

divisors = []
for i in chain([2], range(3, int(g ** 0.5) + 1, 2)):
    firsttime = True
    while g % i == 0:
        g //= i
        if firsttime:
            divisors.append(i)
            firsttime = False
    if g == 1:
        break
if g != 1:
    divisors.append(-1)

print(len(divisors) + 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())
ab_gcd=fractions.gcd(a,b)
div_list=make_divisors(ab_gcd)
prime_list=[]

for i in div_list:
    flg=True
    for j in prime_list:
        if j == 1:
            continue
        if i % j == 0:
            flg = False
            break
    if flg:
        prime_list.append(i)

print(len(prime_list))

Submission status: Accepted

Solution code:
import math


def is_prime(n):
    if n == 1 or n == 2: return True
    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


a, b = map(int, input().split())
a_div = make_divisors(a)
b_div = make_divisors(b)
a_b_div = list(set(a_div).intersection(set(b_div)))
cnt = 0
for num in a_b_div:
    if is_prime(num):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import fractions
a,b=map(int,input().split())
c=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 c==1:
  print(1)
else:
  print(len(factorization(c))+1)

Submission status: Accepted

Solution code:
import math

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

def soinsu(test):
    list_sosu = []
    x = 0
    while x==0:
        for i in range(2,test+1):
            if i > int(math.sqrt(test)):
                list_sosu.append(test)
                x = 1
                break
            elif test % i == 0:
                test = int(test/i)
                if test == 1:
                    x = 1
                list_sosu.append(i)
                break
    return set(list_sosu)

if A == 1 or B == 1:
    print(1)
    
else:
    print(len(soinsu(A)&soinsu(B))+1)

Submission status: Accepted

Solution code:
import sys
from random import randint

a, b = map(int, sys.stdin.readline().split())

def isPrime(n, k=5): # miller-rabin
	if n < 2: return False
	for p in [2,3,5,7,11,13,17,19,23,29]:
		if n % p == 0: return n == p
	s, d = 0, n-1
	while d % 2 == 0:
		s, d = s+1, d//2
	for i in range(k):
		x = pow(randint(2, n-1), d, n)
		if x == 1 or x == n-1: continue
		for r in range(1, s):
			x = (x * x) % n
			if x == 1: return False
			if x == n-1: break
		else: return False
	return True

x = min(a, b)
def divisors(a, b):
	divs = set()
	i = 1
	while i*i <= x:
		if a%i == 0 and b%i==0:
			if isPrime(i):
				divs.add(i)
		other = a//i 
		if a%other == 0 and b%other==0:
			if isPrime(other):
				divs.add(other)
		i += 1
	return divs

res = divisors(a, b)
print(len(res)+1)

Submission status: Accepted

Solution code:
N, M  = 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 = make_divisors(N)
m = make_divisors(M)

res = set(n) & set(m)

res = list(res)

res.sort()


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

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


print(result+1)

Submission status: Accepted

Solution code:
import sys

def gcd (x,y):
  if y :
    return gcd(y, x%y)
  else:
    return x
  
# https://qiita.com/snow67675476/items/e87ddb9285e27ea555f8
# 素因数分解
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,sys.stdin.readline().split())
ansList=factorization(gcd(A,B))
if ansList[0][0] == 1:
  print(len(ansList))
else:
  print(len(ansList)+1)

Submission status: Accepted

Solution code:
def solve():
  import sys
  import math

  sys.setrecursionlimit(10**7)
  readline=sys.stdin.readline

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

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

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

  max_gcd = gcd(a,b)

  ans = set(prime_factorize(max_gcd))

  print(len(ans)+1)

  
if __name__ == '__main__':
  solve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
# スペース区切りの整数の入力
A, B = map(int, input().split())
# Aのほうが大きいとする
if A < B:
  A, B = B, A
# 最大公約数を算出（ユークリッドの互除法）
def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a
# 最大公約数を素因数分解
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
ans = factorize(gcd(A, B))
print('{}'.format(len(ans)+1))

Submission status: Accepted

Solution code:
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac
import bisect
import sys
import logging
import heapq
logging.basicConfig(level=logging.DEBUG)

input = sys.stdin.readline

setrecursionlimit(1000000)

MOD = 10**9+7

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

    max_gcd=gcd([A,B])
    P=prime_factor(max_gcd)
    P2=set(P)
    print(len(P2)+1)

def gcd(l):
	x = l.pop()
	y = l.pop()
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	l.append(min(x,y))
	return gcd(l) if len(l) > 1 else l[0]

def primes(n):
    ass = []
    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
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return ass #sortされていない

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

main()

Submission status: Accepted

Solution code:
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)
    return a

A, B = map(int, input().split())
a_prime = set(prime_factorize(A))
b_prime = set(prime_factorize(B))
prime = a_prime & b_prime
print(len(prime))

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

def solve():
    import fractions
    A,B = map(int, input().split())
    gcd = fractions.gcd(A,B)
    prime_factor = list(set(prime_factorize(gcd)))
    
    ans = int(len(prime_factor))
    for i in range(int(2**len(prime_factor))):
        i_temp = i
        j = 0
        composite = 1
        count = 0
        while i_temp != 0:
            if i_temp%2 == 0:
                pass
            elif i_temp%2 == 1:
                composite *= prime_factor[j]
                count += 1
            j += 1
            i_temp /= 2
        
        for j in prime_factor:
            if j == composite and count >= 2:
                ans -= 1

    print(ans + 1) 

solve()

Submission status: Accepted

Solution code:
def prime(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())
x = prime(a)
y = prime(b)
print(len(set(x) & set(y)) + 1)

Submission status: Accepted

Solution code:
A, B = map(int, input().split())
list = [A, B]
list.sort()

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

import collections
c = collections.Counter(prime_factorize(gcd(A, B)))

print(len(c)+1)

Submission status: Accepted

Solution code:
from fractions import gcd
a,b = map(int, input().split())
# ans = 1
count = 2
n=gcd(a,b)

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

Submission status: Accepted

Solution code:
A , B = map(int, input().split())
def gcd(x, y):
    if x < y:
        tmp = x
        x = y
        y = tmp
    r = x % y   
    while r != 0:
        x = y
        y = r
        r = x % y
    return y
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
X = gcd(A,B)
lst = make_divisors(X)
for i in lst:
    if i == 1:
        check = [1]
        continue
    for j in check:
        if gcd(i, j) != 1:
            break
    else:
        check.append(i)
print(len(check))

Submission status: Accepted

Solution code:
a, b = map(int, input().split())
# a, bに何種類共通の素因数があるかを調べればよい.
# 試し割り法で、どちらも素因数だと判断されればOK.10^6まで調べればいい.
ans = 1 # 1の分
chk_a = a
chk_b = b
if((a % 2) == 0 and (b % 2) == 0):
    ans += 1
while chk_a % 2 == 0:
    chk_a //= 2
while chk_b % 2 == 0:
    chk_b //= 2
f = 3
checker = max(a, b)
while f * f <= checker:
    if( (chk_a % f) == 0 and (chk_b % f) == 0):
        ans += 1
    while chk_a % f == 0:
        chk_a //= f
    while chk_b % f == 0:
        chk_b //= f
    f += 2
check_min = min(chk_a,chk_b)
if((chk_a % check_min) == 0 and (chk_b % check_min) == 0 and check_min > 1):
    ans += 1
print(ans)

Submission status: Accepted

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

    return divisors

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

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

    return True

c = set(make_divisors(a))
d = set(make_divisors(b))
e = list(c & d)

f = []
for i in range(len(e)):
        if is_prime(e[i]):
            f.append(e[i])
print(len(f) + 1)

Submission status: Accepted

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

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

    divisors.sort()
    return divisors

A_temp = make_divisors(A)
B_temp = make_divisors(B)

AB_temp = list(set(A_temp) & set(B_temp))

ans = 0

for i in AB_temp:
    count = 0
    if i > 2 and i % 2 != 0:
        for j in AB_temp:
            if i % j != 0:
                count += 1
        if count == len(AB_temp)-2:
            ans += 1
    elif i <= 2:
        ans += 1
 
print(ans)

Submission status: Accepted

Solution code:
x,y = map(int,input().split())
 
#print(x,y)
 
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
x_li=(make_divisors(x))
y_li=(make_divisors(y))
z_li=(list(set(x_li)&set(y_li)))
#print(z_li)
 
import math
count=1

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
for n in z_li:
  if(is_prime(n)==True):
    count=count+1
print(count)

Submission status: Accepted

Solution code:
a1,a2 = 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
import collections
c1 = collections.Counter(prime_factorize(a1))
c1 = list(c1.keys())
c2 = collections.Counter(prime_factorize(a2))
c2 = list(c2.keys())
c = 1
for i in range(0,len(c1)):
    if c2.count(c1[i]) == 0:
        continue
    else:
        c = c+1
print(c)

Submission status: Accepted

Solution code:
import math

def euclid(a, b):
    if a == b:
        return a
    elif b > a:
        return euclid(b, a)
    else:
        while b > 0:
            temp = a % b
            a = b
            b = temp
        return a


def get_e(x):
    l = []
    i = 2
    m = math.floor(math.sqrt(x))
    while i <= m and i <= x:
        if x % i == 0:
            x = x // i
            l += [i]
        else:
            i += 1
    if x != 1:
        l += [x]
    return l


def calc(A, B):
    gcd = euclid(A, B)
    if gcd == 1:
        return 1
    else:
        return 1 + len(set(get_e(gcd)))


(A, B) = tuple([int(s) for s in input().split(' ')])
print(calc(A, B))

Submission status: Accepted

Solution code:


def main():
    from fractions import gcd
    A, B = map(int, input().split())
    # 1 <= A, B <= 10 ** 12
    if B > A:
        A, B = B, A
    G = gcd(A, B)
    print(1+len(set(prime_factorize(G))))

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
''' 
------------------------
author : iiou16
------------------------
'''

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

    # 最大公約数
    a = max(A, B)
    b = min(A, B)
    while b:
        a, b = b, a % b
    # print(a)

    # 素因数分解
    def prime_decomposition(n):
        i = 2
        table = []
        while i * i <= n:
            while n % i == 0:
                n /= i
                table.append(i)
            i += 1
        if n > 1:
            table.append(n)
        return table

    pp = prime_decomposition(a)
    # print(pp)

    # 最大公約数を素因数分解したリストから重複を除いたものがanswer
    ans = len(set(pp)) + 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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):
    # 確かめるのはnの平方根までで大丈夫
        if not is_prime[i]:  # すでにfalseなら次のiへ
            continue
            """
            bool(not False)はTrueになる
            """
        for j in range(i * 2, n + 1, i):
        # iずつ大きくなる(つまりiの倍数をみる)
            is_prime[j] = False
            # i自身を除くiの倍数を全てFalseにする
    return [i for i in range(n + 1) if is_prime[i]]
     # Trueのものだけ列挙して返す


def gcd(m, n):
    while n:
        m, n = n, m % n
    return m


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

# Aの約数を列挙する
A_divs = []
ans = 0

for i in range(1, int(A**(1/2))+2):
    if A % i == 0:
        A_divs.append(i)
        A_divs.append(A//i)

common_divisor = []

for a in A_divs:
    if B % a == 0:
        common_divisor.append(a)

common_divisor = list(set(common_divisor))
common_divisor.sort()
# print(common_divisor)

ans = [1]

for num in common_divisor:
    flag = True
    for i in range(len(ans)):
        if gcd(num, ans[i]) != 1:
            flag = False
    if flag:
        ans.append(num)
ans.remove(1)

print(len(ans))

Submission status: Accepted

Solution code:


import fractions
n, k  = map(int, input().split())
l=[]



kou=fractions.gcd(n, k)


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

print(len(set(l))+1)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
from fractions import gcd
L = 10**6+1
isPrime = [True] * L
isPrime[0] = False
isPrime[1] = False
primes = []
for n in range(2, L):
  if isPrime[n]:
    primes.append(n)
    isPrime[2*n::n] = [False] * ((L-n-1) // n)

def primeFactorization(n):
  ret = dd(int)
  ret[1] = 1
  for p in primes:
    while n % p == 0:
      ret[p] += 1
      n //= p
  ret[n] = 1
  return ret

A, B = map(int, input().split())
g = gcd(A, B)
ps = primeFactorization(g)
print(len(ps))

Submission status: Accepted

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

import math

def prime(n):
  if n == 1:
    return False
  i = 1
  while i < int(math.sqrt(n)):
    i += 1
    if n%i == 0:
      return False
  else:
    return True

#print(prime(1))

if prime(a) and prime(b) and a==b:
  print(2)
  exit()
  
if a-b == 1 or b-a == 1:
  print(1)
  exit()

l = []
for i in range(1, max(int(math.sqrt(a))+2, int(math.sqrt(b))+2)):
  if i == 1:
    l.append(i)
  else:
    if a%i == 0 and b%i == 0 and prime(i):
      l.append(i)
    j = a//i
    if j != 0:
      if b%j == 0 and prime(j):
        l.append(j)
    k = b//i
    if k != 0:
      if a%k == 0 and prime(k):
        l.append(k)
#print(set(l))
print(len(set(l)))

Submission status: Accepted

Solution code:
def main():
    a, b = map(int, input().split(' '))
    d_s = make_divisors(a, b)

    ans = []

    for j in d_s:
        flg = True
        for k in d_s:
            if k == 1 or j == k:
                continue
            if j % k == 0:
                flg = False
                break
        if flg:
            ans.append(j)
    print(len(ans))


def make_divisors(a, b):
    A = []
    B = []
    n = max(a, b)
    for i in range(1, int(n**0.5)+1):
        if a % i == 0:
            A.append(i)
            if i != a // i:
                A.append(a//i)
        if b % i == 0:
            B.append(i)
            if i != b // i:
                B.append(b//i)
    return list(set(A) & set(B))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
a, b = map(int, input().split())
import math
import fractions
n = fractions.gcd(a, b)
devide = 2
l1 = []
while devide <= math.sqrt(n):
    while n % devide == 0:
        n = n / devide
        l1.append(devide)
    devide += 1
l1.append(n)
l1 = list(set(l1))
if n == 1:
    print(int(len(l1)))
else:
    print(int(len(l1) + 1))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

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

    def soin(x):
        res = []
        cnt = 0
        while x % 2 == 0:
            x //= 2
            cnt += 1
        if cnt: res.append(cnt)
        d = 3
        while d ** 2 <= x:
            cnt = 0
            while x % d == 0:
                x //= d
                cnt += 1
            if cnt: res.append(cnt)
            d += 2
        if x != 1: res.append(1)
        return res

    a, b = map(int, input().split())
    g = gcd(a, b)
    e = soin(g)
    print(len(e) + 1)

main()

Submission status: Accepted

Solution code:
import itertools

# どっかのサイトから
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())
    
com_div = sorted(list(set(make_divisors(A)) & set(make_divisors(B))))

# ふるいにかける
limit = max(com_div)**0.5 + 1

primes = []

for i in itertools.count(1):
    if i >= len(com_div):
        break
    sosuu = com_div[i]
    if sosuu > limit:
        break
    com_div = [j for j in com_div if (j % sosuu != 0 or j == sosuu)]

print(len(com_div))

Submission status: Accepted

Solution code:
import math
from fractions import gcd

def era(ps, n):
    if len(ps) == 1:
        return 1
    search_list = ps[1:]
    for i in range(1, n+1):
        search_list = [num for num in search_list if num % i != 0 or num == i ]

    return len(search_list)+1

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(math.sqrt(n))+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def main():
    a,b = map(int, input().split())

    g = gcd(a, b)
    div = make_divisors(g)
    #print(div)

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

    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import fractions
a,b=map(int, input().split())
f=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 f==1:
  print(1)
  exit()
else:
  temp=factorization(f)
  temps=set([])
  for item in temp:
    temps.add(item[0])
  if 1 in temps:
    print(len(temps))
  else:
    print(len(temps)+1)

Submission status: Accepted

Solution code:
import math
def gcd(x, y): 
  
   while(y): 
       x, y = y, x % y 
  
   return x 
  
a,b = map(int,input().split())
n = gcd(a,b)
count = [1]
while (n % 2 == 0):
    count += [2]
    n = n / 2
for i in range(3, int(math.sqrt(n)) + 1, 2):
    while (n % i == 0):
        count+=[i]
        n = n / i

if n > 2:
    count+=[n]
c = 1
count = sorted(count)
for i in range(1,len(count)):
    if (count[i-1] != count[i]):
        c+=1
print(c)

Submission status: Accepted

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


def trial_division(n):
    factor_set = set()
    factor_set.add(1)
    tmp = int(math.sqrt(n)) + 1
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor_set.add(num)
    if not factor_set:
        factor_set.add(n)
        return factor_set
    else:
        factor_set.add(n)
        return factor_set


a, b = map(int, input().split())
td_a = trial_division(a)
td_b = trial_division(b)
count = len(td_a & td_b)
print(count)

Submission status: Accepted

Solution code:
def main():
    A, B = map(int, input().split())
    X = prime_decomposition(gcd(A, B))
    print(len(set(X))+1)


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


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


if __name__ == '__main__':
    main()

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) #再帰定義
n = 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
  
L = sorted(make_divisors(n))
tmp = []
for i in range(len(L)):
  e = L[i]
  if e == 1:
    tmp.append(e)    
  else:
    f = 0
    for j in range(len(tmp)):      
      if gcd(e,tmp[j]) != 1:
        f = 1
        if tmp[j] == 1:
          f = 0
    if f == 0:
      tmp.append(e)

print(len(tmp))