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(x, y):
    while y != 0:
        r = x % y
        x = y
        y = r
    return x

A, B = map(int, input().split())
gcd = gcd(A, B)
result = 1
d = 2
while d * d <= gcd:
    e = 0
    while gcd % d == 0:
        gcd //= d
        e += 1
    if e > 0:
        result += 1
    d += 1
if gcd > 1:
    result += 1
print(result)

Submission status: Accepted

Solution code:
import numpy as np

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

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

GCD = get_gcd(a,b)

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

primes = sorted(sep_prime(GCD))

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

# judge
count = 0
for p in primes:
  if is_prime(p):
    count += 1

print(count)

Submission status: Accepted

Solution code:
import collections

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

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


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

g = gcd(A,B)
L = prime_factorization(g)

c = collections.Counter(L)
ans = len(c)

print(ans)

Submission status: Accepted

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

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

num = gcd(A, B)

if num < 2:
    print(1)
    quit()

length = int(num ** 0.5) + 2
isPrime = [True for i in range(length)]
isPrime[2] = True
for i in range(2, length):
    if isPrime[i]:
        for j in range(2 * i, length, i):
            isPrime[j] = False

count = 1

cur = 2
while num != 1 and cur < length:
    if isPrime[cur] and num % cur == 0:
        while num % cur == 0:
            num //= cur
        count += 1
    cur += 1

print(count + (num != 1))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def mkou(A,B):
    x = A%B
    if  x== 0:
        return B
    else:
        return mkou(B,x)
        
def prime_F(k):
    a =[1,]
    end = int(pow(k,0.5))
    if k % 2 == 0:
        while k %2 == 0:
            k /=2
        a.append(2)
    k =int(k)

    for x in range(3,end,1):
        if k % x == 0:
            while k %x == 0:
                k/=x
            a.append(x)
            if k == 1:
                break
    if k != 1:
        a.append(k)
    return a
            
A,B = map(int,input().split())
divA_array = []
divB_array = []
if A<B:
    A,B =B,A

kouyaku = mkou(A,B)
soinsu =prime_F(kouyaku)
print(len(soinsu))

Submission status: Accepted

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

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

def factrize(z):
    i = 2
    set = {1}
    while i*i <= z:
        while z%i==0:
            z//=i
            set.add(i)
        i+=1
    if z > 1:
        set.add(z)
    return set

gcd = calc_gcd(a, b)
print(len(factrize(gcd)))

Submission status: Accepted

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

def main():
    a,b = map(int,input().split())
    a_set = set(prime_factor(a))
    b_set = set(prime_factor(b))
    c_set = a_set & b_set
    print(len(c_set)+1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions as fc

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

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

m = max(a,b)

max_koyakusu = fc.gcd(a,b)

print(len(prime_factorize(max_koyakusu)))

Submission status: Accepted

Solution code:
def calc_prime(x):
    prime = set()
    
    if not x % 2: prime.add(2)
    while not x % 2: x //= 2
        
    i = 3
    while i ** 2 <= x:
        if not x % i: prime.add(i)
        while not x % i: x //= i
        i += 2
        
    if x != 1: prime.add(x)
    
    return prime

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

print(len(calc_prime(A) & calc_prime(B)) + 1)

Submission status: Accepted

Solution code:
from fractions import gcd
def f(n):
    tmp = n
    cnt = 0
    i = 2
    while i <= n**0.5 + 1:
        if tmp < i:
            break
        if tmp % i == 0:
            cnt += 1
            while tmp % i == 0:
                tmp //= i
        i += 1
    if tmp != 1:
        cnt += 1
    return cnt

A, B = map(int, input().split())
g = gcd(A, B)
ans = f(g) + 1
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

def div(n,m):
    divisors = [1]
    for i in range(2, 10**7+1):
        if n % i == 0 and m % i == 0:
            divisors.append(i)
            while n % i == 0 and m % i == 0:
                n = n // i
                m = m // i

    return divisors,n,m

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

d,n,m = div(a,b)

if gcd(n,m) > 1:
    print(len(d)+1)
else:
    print(len(d))

Submission status: Accepted

Solution code:
from fractions import gcd
a,b=map(int,input().split())
g=gcd(a,b)
l=[]
for i in range(2,int(g**0.5)+1):
  while g%i==0:
    l.append(i)
    g//=i
#print(l)
if g>1:
  l.append(g)
#print(l)
print(len(set(l))+1)

Submission status: Accepted

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

Submission status: Accepted

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

maxn=fractions.gcd(A,B)
list=[]
def isPrime(n):
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    if n==3:
        return True
    m = math.floor(math.sqrt(n)) + 1
    for p in range(3, m,2):
        if n % p == 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

yaku=make_divisors(maxn)
for i in range(len(yaku)):
    if isPrime(yaku[i]):
        list.append(yaku[i])

print(len(list))

Submission status: Accepted

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

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



g = gcd(a, b)

nof = 1
up = g

for i in range(2, up):
    if i*i > up:
        break
    if g%i == 0:
        nof += 1
        #print(i, nof)
        while g%i == 0:
            g = g//i
if g > 1:
    nof += 1
print(nof)

Submission status: Accepted

Solution code:
# 1と素因数の個数の和が答え
# つまりAの素因数を求めて、その中でBの約数となっているものを数えればよい。

def p_factors(x): # prime_factors
    ret = [1]
    check = 2
    while (True):
        if x % check == 0:
            ret.append(check)
            while x % check == 0:
                x = x // check
        check += 1
        if x == 1 or check > int(x**0.5)+1:
            break
    if x != 1:
        ret.append(x)
    return ret

def main():
    A, B = map(int, input().split())
    factors = p_factors(A)
    cnt = 0
    for f in factors:
        if B % f == 0:
            cnt += 1
    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import fractions

def calc_factors(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())
g = fractions.gcd(A,B)
if g == 1:
    print(1)
else:
    print(len(set(calc_factors(g)))+1)

Submission status: Accepted

Solution code:
import math
def prime(n):
    flag = True
    if n==1 or n==2:
        return True
    for i in range(2,math.ceil(math.sqrt(n))+1):
        if n%i == 0:
            flag = False
            break
    return flag

a,b=map(int,input().split())
A=set()
B=set()

for i in range(1,math.ceil(math.sqrt(a))+1):
    if a%i == 0:
        A.add(i)
        A.add(a//i)

for i in range(1,math.ceil(math.sqrt(b))+1):
    if b%i == 0:
        B.add(i)
        B.add(b//i)

A=[num for num in A if prime(num)]
B=[num for num in B if prime(num)]

ans=0
for b in B:
    if b in A:
        ans+=1
print(ans)

Submission status: Accepted

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

def main():
    a,b = list(map(int,input().split()))
    prime_a = prime_factorize(a)
    prime_b = prime_factorize(b)
    cnt = 0
    for i in prime_a:
        for j in prime_b:
            if i == j:
                cnt+=1
    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
import fractions

x, y = map(int,input().split())

gcd = fractions.gcd(x,y)

size = int(math.sqrt(gcd)) + 1

def calc_div(num):
    table =  []
    for i in range(2,int(math.sqrt(num))+1):
        if num % i == 0:
            table.append(i)    
            while num % i == 0:
                num //= i
    if num > int(math.sqrt(num)):
        table.append(num)
    return table 

ans = calc_div(gcd)

print(len(ans) + 1)

Submission status: Accepted

Solution code:
import math
def trial_division(n):
    a = [1]
    for i in range(2,int(math.sqrt(n)) + 1):
        while n % i == 0:
            n //= i
            a.append(i)
    a.append(n)
    return a
A, B = map(int, input().split())
ans = set(trial_division(A)) & set(trial_division(B))
print(len(ans))

Submission status: Accepted

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

a_div_max = int(a ** (1/2)) + 1
b_div_max = int(b ** (1/2)) + 1

a_divs = {1}
b_divs = {1}
for i in range(1, a_div_max):
	if a % i == 0:
		a_divs.add(i)
		a_divs.add(a // i)

for i in range(1, b_div_max):
	if b % i == 0:
		b_divs.add(i)
		b_divs.add(b // i)

divs = a_divs & b_divs

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

res = len([d for d in divs if is_prime(d)]) + 1
print(res)

Submission status: Accepted

Solution code:
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(int(n))
  return table
  
num1, num2 = map(int, input().split())

primeList = prime_decomposition(gcd(num1, num2))
primeSet = set(primeList)
print(len(primeSet) + 1)

Submission status: Accepted

Solution code:
A, B = input().split(" ")
A = int(A)
B = int(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
  
x_A = [x[0] for x in factorization(A)]
x_B = [x[0] for x in factorization(B)]


if x_A == [1] and x_B == [1]:
  print(1)
  exit()


ans = 1
for x in x_A:
  if x in x_B:
    ans += 1


print(ans)

Submission status: Accepted

Solution code:
"""
最大公約数を求める
最大公約数の約数を列挙
素数かどうかを判定
"""

import math

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

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

def is_prime(n):
    """素数判定関数

    Arguments:
        n {[type]} -- [description]

    Returns:
        [type] -- [description]
    """
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return True

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

gcd = max_yakusu(B,A)
numbers = divisor(int(gcd))
ans = 0
for i in numbers:
    if is_prime(i):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
A, B = input().split(" ")
A = int(A)
B = int(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
  
x_A = [x[0] for x in factorization(A)]
x_B = [x[0] for x in factorization(B)]

if x_A == [1] and x_B == [1]:
  print(1)
  exit()

ans = 1
for x in x_A:
  if x in x_B:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
def factor(n):
    factor_set = {1}
    tmp = int(n**0.5)+1
    for i in range(2, tmp):
        while n % i == 0:
            n = n // i
            factor_set.add(i)
    factor_set.add(n)
    return factor_set


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

print(len(factor(A) & factor(B)))

Submission status: Accepted

Solution code:
from collections import Counter
a,b=[int(i) for i in input().split()]
a_yaku=[]
b_yaku=[]
for i in range(1,int(a**0.5)+1):
    if a%i==0:
        a_yaku+=[i,a//i]

for i in range(1,int(b**0.5)+1):
    if b%i==0:
        b_yaku+=[i,b//i]
yaku=a_yaku+b_yaku
koyaku=[]
cnt=dict(Counter(yaku))
for key,val in zip(cnt.keys(),cnt.values()):
    if val==2:
        koyaku+=[key]
koyaku.sort()
koyaku=koyaku[1:]
l=len(koyaku)
ans=1
for i in range(l):
    flg=True
    for j in range(l):
        if i!=j and koyaku[i]%koyaku[j]==0:
            flg=False
    if flg:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
ii0 = lambda: ii() - 1
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
def divs_gen(n):
    for i in range(1, int(m**.5)+1):
        if n%i == 0:
            yield i
            if i != n//i:
                yield n//i


def main():
    A, B = mis()
    from fractions import gcd
    G = gcd(A, B)
    fs = set()
    for i in range(2, int(G**0.5)+2):
        if G%i == 0 and all(i%f != 0 for f in fs):
            fs.add(i)
            while G%i == 0:
                G //= i
    if G > 1:
        fs.add(G)
    print(len(fs)+1)


main()

Submission status: Accepted

Solution code:
A,B=map(int,(input().split()))
import fractions 
C=fractions.gcd(A,B)
d = []
for i in range(2, int(C**0.5)+1):
	if C % i == 0:
		d.append(i)
		if i != C // i:
			d.append(C//i)
	
D=sorted(d)[::-1]
if D!=[]:
	j=0
	k=len(D)-1
	while j<k:
 
		if D[j]%D[k]==0:
			D.pop(j)
			k=len(D)-1
		else:
			if j+1<k:
				k-=1
			else:
				j+=1
				k=len(D)-1
	D.append(1)
elif C!=1:
	D=[C,1]
else:
	D=[1]
print(len(D))

Submission status: Accepted

Solution code:
a, b = map(int, input().split())
m, n = a, b
c = 0

while n != 0:
    c = m % n
    m = n
    n = c

li = [1]
for i in range(2, int(m ** 0.5)+1):
    while m % i == 0:
        m //= i
        li.append(i)
li.append(m)

print(len(set(li)))

Submission status: Accepted

Solution code:
import math
list1 = [int(i) for i in input().split()]
def prime(n):
    for i in range(2, int(n**0.5) + 1):
        if(n%i == 0):
            return False
    return True
a = list1[0]
b = list1[1]
count = 0 
diva = []
divb = []
for i in range(1,int(a**0.5) + 1):
    if(a%i == 0):
        diva.append(i)
        diva.append(a//i)
for i in range(1,int(b**0.5) + 1):
    if(b%i == 0):
        divb.append(i)
        divb.append(b//i)

set1 = set(diva)
set2 = set(divb)
l = []
set3 = list(set1.intersection(set2))
for i in set3:
    if(prime(i)):
      
        l.append(i)
        
print(len(l))

Submission status: Accepted

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

x=fractions.gcd(A,B)

l=[]
for i in range(2, math.floor(math.sqrt(x))+1):
  count=0
  while x%i==0:
    count+=1
    x/=i
  if count>=1:
    l.append([i,count])
if x>math.floor(math.sqrt(x)):
  l.append([x, 1])
print(len(l)+1)

Submission status: Accepted

Solution code:
import sys
import fractions


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    a, b = list(map(int, input().rstrip('\n').split()))
    gcd = fractions.gcd(a, b)
    cnt = 1
    for i in range(2, int(gcd ** 0.5) + 1):
        if gcd % i == 0:
            cnt += 1
            while True:
                if gcd % i == 0:
                    gcd //= i
                else:
                    break
    print(cnt + 1 if gcd != 1 else cnt)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

Submission status: Accepted

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

def dfs(n):
    table = []
    i = 2
    while n >= i**2:
    # nのその数自身を除いた素因数は√n以下であることから。
        cnt = 0
        while n % i == 0:
            cnt += 1
            n /= i
        if cnt:
          table.append(cnt)
        i += 1
    if n > 1:
        table.append(1)
# 最後に残った、最大の素因数をリストに入れる。
    return table

dfs_list = dfs(fractions.gcd(a, b))

print(len(dfs_list)+1)

Submission status: Accepted

Solution code:
A,B = map(int,input().split())
def prime_number_set(n):
  N = n
  result = set()
  while (n%2) == 0:
    n //= 2
    result.add(2)

  for i in range(3,int(N**0.5)+2,2):
    while (n%i) == 0:
      n //= i
      result.add(i)
  if n > 1:
    result.add(n)
  return result

arrayA = prime_number_set(A)
arrayB = prime_number_set(B)
array = arrayA & arrayB
print(len(array)+1)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest


def factorization(n):
    if n == 1:
        return {}
    d = {}
    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
            d[i] = cnt

    if temp != 1:
        d[temp] = 1

    if d == {}:
        d[n] = 1

    return d


def resolve():
    A, B = map(int, input().split())
    A_f = factorization(A)
    B_f = factorization(B)

    d = {}
    for key_A, value_A in A_f.items():
        if key_A not in B_f:
            continue
        d[key_A] = max(value_A, B_f[key_A])

    print(len(d.keys()) + 1)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """12 18"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """420 660"""
        output = """4"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """1 2019"""
        output = """1"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
from sys import stdin
import fractions
import bisect

a,b = [int(x) for x in stdin.readline().rstrip().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

ali = set(prime_factorize(a))
bli = set(prime_factorize(b))

ali = list(ali)
bli = list(bli)

point = 0
for i in range(len(ali)):
    if ali[i] in bli:
        point += 1
print(point+1)

Submission status: Accepted

Solution code:
### Pythonのバージョンが3.4.3なのでmath.gcd(*, *)がエラーとなるらしい。
import fractions
import math

def prime_factorization(n):
    s = math.floor(math.sqrt(n)) # 平方根を小数点切り捨て
    ans = [] # [素数, 指数]のリスト

    # 2からsまでの素因数を求める
    for i in [2] + list(range(3, s + 1, 2)):
        if n < i:
            break
        if n % i == 0:
            r = 0 # 指数カウンタクリア
            while n % i == 0:
                r += 1
                n //= i
            ans.append([i, r])

    # 残った素数を追加
    if n > s:
        ans.append([n, 1])

    return(ans)


A, B = [int(a) for a in input().split()]

# d = gcd(A, B) = p_1^(e_1) + p_2^(e_2) + ... + p_k^(e_k)
# と素因数分解できる場合、答えは k + 1
d = fractions.gcd(A, B)
pf = prime_factorization(d)
print(len(pf) + 1)

Submission status: Accepted

Solution code:
def gcd(a,b):
    if a>b :
        while b!=0:
            a,b = b,a%b
        return a
    else :
        while a!=0:
            a,b = b%a,a
        return b
######################################
def pff(m):
    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
    return pf
############################
import heapq
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')

A, B = LI()
ans = int(1)

cur = gcd(A,B)

ansC = pff(cur)

ans = len(ansC)+1

print(ans)

Submission status: Accepted

Solution code:
def calc_gcd(a, b):
    return calc_gcd(b, a % b) if b else a


def p_d():
    a, b = map(int, input().split())
    gcd = calc_gcd(a, b)
    ans = 1
    cnt = 2
    while cnt * cnt < gcd:
        up = True
        while gcd % cnt == 0:
            if up:
                ans += 1
                up = False
            gcd //= cnt
        cnt += 1
    ans += 1 if gcd != 1 else 0
    print(ans)


if __name__ == '__main__':
    p_d()

Submission status: Accepted

Solution code:
import fractions

def prime_factorization(N):
    tmp = N
    ans = []
    for i in range(2, int(N ** 0.5) + 1):
        count = 0
        while tmp % i == 0:
            tmp //= i
            count += 1
        if count != 0:
            ans.append([i, count])
    if tmp != 1:
        ans.append([tmp, 1])
    if ans == []:
        ans.append([N, 1])
    return ans

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

gcdAB = fractions.gcd(A, B)

if gcdAB == 1:
    print(1)
else:
    print(len(prime_factorization(gcdAB)) + 1)

Submission status: Accepted

Solution code:
from sys import stdin
import math
a, b = [int(x) for x in stdin.readline().rstrip().split()]
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,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
g = gcd(a,b)
answer = factorize(g)
answer = list(set(answer))
print(len(answer) + 1)

Submission status: Accepted

Solution code:
#l=list(map(int, input().split()))
a,b=map(int, input().split())
#l=list(map(int, input().split()))
#n = int(input())
def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1

ans = 1
hoge = divisor(a)
hoge2 = divisor(b)

temp = []
for i in hoge:
    if i in hoge2:
        temp.append(i)

for i in temp:
    if is_prime(i):
        ans += 1

print (ans)

Submission status: Accepted

Solution code:
#l=list(map(int, input().split()))
a,b=map(int, input().split())
#l=list(map(int, input().split()))
#n = int(input())
def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1



ans = 1
temp1 = divisor(a)
temp2 = divisor(b)

if len(temp1) < len(temp2):
    hoge = temp1
    hoge2 = temp2
else:
    hoge = temp2
    hoge2 = temp1

temp = []
for i in hoge:
    if i in hoge2:
        temp.append(i)

#print (temp)
for i in temp:
    if is_prime(i):
        ans += 1

print (ans)

Submission status: Accepted

Solution code:
#l=list(map(int, input().split()))
a,b=map(int, input().split())
#l=list(map(int, input().split()))
#n = int(input())
def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1



ans = 1
temp1 = divisor(a)
temp2 = divisor(b)
hoge = []
if len(temp1) < len(temp2):
    hoge = temp1
    hoge2 = temp2
else:
    hoge = temp2
    hoge2 = temp1

temp = []
for i in hoge:
    if i in hoge2:
        temp.append(i)

#print (temp)
for i in temp:
    if is_prime(i):
        ans += 1

print (ans)

Submission status: Accepted

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

i = 1

table_a = []
table_b = []

while i * i <= a:
    if a % i == 0:
        table_a.append(i)
        table_a.append(a // i)
    i += 1
i = 1
while i * i <= b:
    if b % i == 0:
        table_b.append(i)
        table_b.append(b // i)
    i += 1
a_b_and = list(set(table_b) & set(table_a))
a_b_and.sort()
i = 0
while i < len(a_b_and) - 1:
    j = i + 1
    while j < len(a_b_and):
        temp1 = a_b_and[i]
        temp2 = a_b_and[j]
        while temp2:
            temp1, temp2 = temp2, temp1 % temp2
        if temp1 != 1:
            a_b_and.pop(j)
        else:
            j += 1
    i += 1
print(len(a_b_and))

Submission status: Accepted

Solution code:
import math
def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)
a,b=map(int,input().split())
hcf=gcd(a,b)
l=int(math.sqrt(hcf))
divset=set()
for i in range(1,l+1):
    if hcf%i==0:
        divset.add(i)
        divset.add(hcf//i)
divset.remove(1)
d=list(divset)
d.sort()
for i in range(1,len(d)):
    for j in range(i):
        if d[i]%d[j]==0:
            divset.remove(d[i])
            break
print(len(divset)+1)

Submission status: Accepted

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

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

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

a,b = map(int, input().split())
c = gcd(a,b)
d = primeFactrization(c)
print(len(d)+1)

Submission status: Accepted

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


#################### library ####################

def factorize_naive(n):
	def f(n, p0):
		if n == 1:
			return ()
		
		for p in takewhile(lambda p: p * p <= n, count(p0)):
			if n % p == 0:
				return (p,) + f(n / p, p)
		else:
			return (n,)
	
	return list((k, len(list(v))) for k, v in groupby(f(n, 2)))


#################### naive ####################


#################### process ####################

def read_input():
	[n, m] = map(int, raw_input().split())
	return (n, m)

def proc():
	n, m = read_input()
	d = gcd(n, m)
	fs = factorize_naive(d)
	return len(fs) + 1


#################### main ####################

print proc()

Submission status: Accepted

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

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

ans = 0
tmp = 1
g = gcd(a,b)
while g > 1:
    for i in range(tmp+1,ceil(sqrt(g))):
        if g%i == 0:
            ans += 1
            tmp = i
            while g%i == 0:
                g //= i
            break
    else:
        # もうgでしか割れないはず
        ans += 1
        break
print(ans+1)

Submission status: Accepted

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

def gcd(x,y):
  if x%y==0:
    return y
  else:
    return gcd(y,x%y)
  
  
n=gcd(a,b)  
i=2
ans=[1]

while i * i <= n:
  if n % i == 0:
    n /= i
    ans.append(i)
  else:
    i += 1

ans.append(n)    
  
print(len(set(ans)))

Submission status: Accepted

Solution code:
import math

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())
a = prime_factorize(A)
b = prime_factorize(B)
ans = 1

while a != []:
    x = a[0]
    if x in b:
        ans+=1
    a = [i for i in a if i != x]

print(ans)