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


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


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(list(set(prime_factorize(gcd(a, b))))) + 1)

Submission status: Accepted

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

def max_div(a,b):
    c = max(a,b)
    b = min(a,b)
    a = c
    
    while(c!=0):
        c = a%b
        a = b
        b = c
        
    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_ = max_div(a,b)
b_ = prime_factorize(a_)
b_ = set(b_)

print(len(b_)+1)

Submission status: Accepted

Solution code:
import math

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

a, b = map(int, input().split())
g = gcd(a, b)
g_2 = int(math.sqrt(g))
cnt = 1

for i in range(2, g_2+1):
    if g % i == 0:
        while g % i == 0:
            g //= i
        cnt += 1
if g > 1:
    cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
 
import random
def is_prime(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
 
    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True
 
import fractions
a, b = map(int,input().split())
ans = 1
gcd_div = make_divisors(fractions.gcd(a, b))
for i in gcd_div:
    if is_prime(i) == True:
        ans += 1
print(ans)

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

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

if fractions.gcd(a, b) == 1:
    print(1)
else:
    print(len(factorization(fractions.gcd(a, b))) + 1)

Submission status: Accepted

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

a,b=map(int,input().split())
c=gcd(a,b)
ans = 1
div = 2
first_flag=1
while c>1:
    if  div**2 > c:
        ans +=1
        break
    while c%div == 0:
        c /= div
        if first_flag == 1:
            ans += 1
            first_flag = 0 
    div += 1
    first_flag = 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import math

A, B = map(int, sys.stdin.readline().split())
C, D = max(A, B), min(A, B)

#ユーグリッド互除法
while True:
    amari = C%D
    C, D = D, amari
    if amari ==0:
        gcd = C
        break
#print(gcd)

#素因数分解
L = [1]
n = int(math.sqrt(gcd))
for i in range(2, n+1):
    while True:
        if gcd%i ==0:
            L.append(i)
            gcd = gcd//i
        else:
            break
if gcd>1:
    L.append(gcd)
L = set(L)
print(len(L))

Submission status: Accepted

Solution code:
from math import *
def gcd(n,m):
    while m != 0:
        n,m=m,n%m
    return n
def main():
    a,b=map(int,input().split(' '))
    g=gcd(a,b)
    cnt = 1
    g2 = int(sqrt(g))
    for i in range(2,g2+1):
        if g%i ==0:
            while g%i ==0:
                g //= i
            cnt += 1
    if g > 1:
        cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd

def FindAllDivisors(x):
    divList = []
    y = 1
    while y <= x**0.5:
        if x % y == 0:
            divList.append(y)
            divList.append(int(x / y))
        y += 1
    return sorted(list(set(divList)))

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

max_divs = gcd(A, B)
divs = FindAllDivisors(max_divs)

results = []
for div in divs[1:]:
    flag = True
    for result in results:
        if div % result == 0:
            flag = False
            break
    if flag:
        results.append(div)

print(len(results) + 1)

Submission status: Accepted

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

n = gcd(A, B)

ans = set()
for i in range(2, int(sqrt(n)+1)+1):
    while n % i == 0:
        n = n // i
        ans.add(i)
if n > 1:
    ans.add(n)

print(len(ans)+1)

Submission status: Accepted

Solution code:
def prime_fact(n):
    a=[]
    while n%2==0:
        a.append(2)
        n //=2
    f=3
    while f**2<=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_key=set(prime_fact(a))
b_key=set(prime_fact(b))
print(len(a_key&b_key)+1)

Submission status: Accepted

Solution code:
import fractions

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

a, b = map(int, input().split())
a_list = return_prime(fractions.gcd(a, b))
print(len(set(a_list)))

Submission status: Accepted

Solution code:
from fractions import gcd
A, B = map(int,input().split())
N = 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

arr = prime_factorize(N)
print(len(list(set(arr))) + 1)

Submission status: Accepted

Solution code:
import fractions
from collections import defaultdict

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

def main():
    a, b = map(int, input().split())
    saidaikoyaku = fractions.gcd(a, b)
    ps = prime_factorize(saidaikoyaku)
    count = 1
    for k in ps:
      count += 1
    print(count)
main()

Submission status: Accepted

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

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

prime_A = set(prime_factorize(A))
prime_B = set(prime_factorize(B))
ans = len(prime_A & prime_B) + 1

print(ans)

Submission status: Accepted

Solution code:
import math
A,B = map(int,input().split())
"""自分の方針
素因数分解ができるならする
そうすると、両方に含まれる因数がわかる
素因数の数が答え。"""
def factriz(N):
    upper = int(math.sqrt(N))
    k = N
    ans = []
    for i in range(2,upper+2):
        if(k%i == 0):
            ans.append(i)
            while(k%i == 0):
                k = k//i
    if(k != 1):
        ans.append(k)
    return ans

A_list = set(factriz(A))
B_list = set(factriz(B))
print(len(A_list & B_list) + 1)

Submission status: Accepted

Solution code:
import sys
from math import ceil, sqrt


def input(): return sys.stdin.readline().strip()


def prime_factors(x):
    f = []
    for i in range(2, ceil(sqrt(x))+1):
        if x % i != 0:
            continue
        f.append([i, 0])
        while x % i == 0:
            x //= i
            f[-1][1] += 1
    if x != 1:
        f.append([x, 1])
    return f


def solve(A, B):
    d_a = set([x[0] for x in prime_factors(A)])
    d_b = set([x[0] for x in prime_factors(B)])
    return d_a & d_b


def main():
    A, B = map(int, input().split())
    ans = len(solve(A, B)) + 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from fractions import gcd


def main():
    A, B = [int(i) for i in input().split()]
    p = get_prime(gcd(A, B))
    print(len(list(p)))


def get_prime(N):
    if N < 2:
        return {1}
    prime = set()
    prime.add(1)

    i = 2
    while i*i <= N:
        while N % i == 0:
            prime.add(i)
            N = N//i
        i += 1
    if N != 1:
        prime.add(N)
    return prime


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin


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


def factorization(a):
    if a < 2:
        return []
    fac = []
    lim = int(a ** 0.5)
    i = 2
    while a > 1 and i <= lim:
        n = 0
        while a % i == 0:
            a //= i
            n += 1
        if n > 0:
            fac += [(i, n)]
        i += 1
    if a > 1 or fac == []:
        fac += [(a, 1)]
    return fac


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

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

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


class AtCoder:

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

    def factorize(self, n):
        p = 2
        res = 1
        while p * p < n:
            if n % p == 0:
                res += 1
                while n % p == 0:
                    n /= p
            p += 1
        if n != 1:
            res += 1
        return res

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

        _gcd = self.gcd(A, B)
        print(self.factorize(_gcd))


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Accepted

Solution code:
import fractions


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


gcd_ab = fractions.gcd(A,B)	



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

    if temp!=1:
        arr += 1

    return arr

f = factorization(gcd_ab)
print(f + 1)

Submission status: Accepted

Solution code:
from fractions import gcd


def main():
    A, B = [int(i) for i in input().split()]
    G = gcd(A, B)
    factor = set()
    i = 2
    while i * i < G:
        while True:
            if G % i == 0:
                factor.add(i)
                G = G // i
            else:
                break
        i += 1

    if G != 1:
        factor.add(G)
    print(len(list(factor))+1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
import copy


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


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

    A_l = divisor(A)
    B_l = divisor(B)
    AB_l = set()
    for a in A_l:
        if a in B_l:
            AB_l.add(a)
    AB_l = sorted(list(AB_l))
    tmp = set(AB_l)
    ans = []
    for i, a in enumerate(AB_l):
        if a not in tmp:
            continue
        try:
            tmp.remove(a)
        except:
            pass
        for b in list(tmp):
            if gcd(a, b) != 1:
                try:
                    tmp.remove(b)
                except:
                    pass
        else:
            ans.append(a)

    print(len(ans))


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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

    return arr

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

if a == [1] and b == [1]:
  print(1)
else:
  print(len(set(a) & set(b))+1)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
sys.setrecursionlimit(10**6)
#input=sys.stdin.readline
show_flg=False
show_flg=True


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

a,b=MI()
g=gcd(a,b)
og=g
ans=set()
ans.add(1)



for i in range(2,int(g**0.5)+2):
    if g%i==0:
        ans.add(i)
        while g%i==0:
            g//=i

x=len(ans)
if g>int(og**0.5) and og!=1:
    x+=1
    
print(x)

Submission status: Accepted

Solution code:
def slove():
    import sys
    import fractions
    input = sys.stdin.readline
    a, b = list(map(int, input().rstrip('\n').split()))
    gcd = fractions.gcd(a, b)
    cnt = 1
    s = 2
    e = int(gcd ** 0.5) + 1
    d = True
    while True:
        if d:
            d = False
            for i in range(s, e):
                if gcd % i == 0:
                    d = True
                    cnt += 1
                    while True:
                        if gcd % i == 0:
                            gcd //= i
                        else:
                            break
                    s = i + 1
                    e = int(gcd ** 0.5) + 1
                    break
        else:
            break
    if gcd != 1:
        cnt += 1
    print(cnt)


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
def resolve():
    a, b = map(int, input().split())
    div_a = set(prime_factorize(a))
    div_b = set(prime_factorize(b))
    print(len(div_a & div_b) + 1)
    # print(div_a)
    # print(div_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


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

A,B = map(int,input().split())
li = list(set([1] + prime_factor(A) + prime_factor(B)))
count = 0
for i in li:
    if A%i==0 and B%i==0:
        count += 1
print(count)

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

x = gcd(a, b)
y = prime_factorize(x)

print(len(y)+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())
n = fractions.gcd(a,b)

li = prime_factorize(n)

print(len(set(li))+1)

Submission status: Accepted

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

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

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

print(len(set(prime_factorize(gcd(A, B))))+1)

Submission status: Accepted

Solution code:
import numpy as np
N=list(map(int,input().split()))
A,B=max(N),min(N)
#ユーグリッド
GCD=1
while True:
    r=A%B
    if r==0:
        GCD=B
        break
    else:
        A=B
        B=r

if GCD==1:
    print(1)
else:
    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

    _GCD=factorization(GCD)
    num_list=[1]
    for num in _GCD:
        num_list+=[num[0]]
    #これで素因数分解の加工が完全に完了
    print(len(num_list))

Submission status: Accepted

Solution code:
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 common_divisor(a, b):
    table = []
    for i in a:
        if i in b:
            table.append(i)
    return table


def resolve():
    A, B = map(int, input().split())
    a_list = divisor(A)
    b_list = divisor(B)
    common_list = common_divisor(a_list, b_list) if len(a_list) < len(b_list) else common_divisor(b_list, a_list)
    common_list.sort()
    i = 1
    while i < len(common_list):
        j = i + 1
        while j < len(common_list):
            if common_list[j] % common_list[i] == 0:
                del common_list[j]
            else:
                j += 1
        i += 1

    print(len(common_list))
    
resolve()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import collections


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

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

def tameshiwari(n):
  result=[]

  f=2
  if n==2:
    result.append(2)
  while f*f<=n:
    if n%f==0:
      result.append(f)
      n=n//f
    else:
      f+=1
  if n!=1:
    result.append(n)
  return result
  

c = collections.Counter(tameshiwari(gcd(a,b)))
print(len(c)+1)

Submission status: Accepted

Solution code:
from collections import Counter
def prime_fact(n):
    a=[]
    while n%2==0:
        a.append(2)
        n //=2
    f=3
    while f**2<=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_key=Counter(prime_fact(a))
b_key=Counter(prime_fact(b))
print(len(a_key&b_key)+1)

Submission status: Accepted

Solution code:
import fractions

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

f = fractions.gcd(A, B)

kouyakusuu = []

if f % 2 == 0:
    kouyakusuu.append(2)
    while f % 2 == 0:
        f = f / 2

i = 3
while i*i <= f:
    if f % i == 0:
        kouyakusuu.append(i)
        while f % i == 0:
            f = f / i
    i += 2
if f != 1:
    kouyakusuu.append(f)
print(len(kouyakusuu)+1)

Submission status: Accepted

Solution code:
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
 
def fact(n):
    b = 2
    li = []
    li.insert(0,1)
    while b*b<=n:
        while n%b == 0:
            n = n//b
            li.append(b)
        b+=1
    if n>1:
        li.append(n)
 
    return li
a,b = map(int,input().split())
c = gcd(a,b)
ans = set(fact(c))
print(len(ans))

Submission status: Accepted

Solution code:
# ABC142D - Disjoint Set of Common Divisors
def gcd(x: int, y: int) -> int:
    while y:
        x, y = y, x % y
    return x


def prime_factors(x: int) -> list:
    if x % 2:
        max_prime, factors = 0, []
    else:
        max_prime, factors = 2, [2]
        while x % 2 == 0:
            x //= 2
    for i in range(3, int(x ** 0.5) + 1, 2):
        if x % i == 0:
            max_prime = i
            factors.append(i)
            while x % i == 0:
                x //= i
    if x > 2:  # when x is prime greater than 2
        factors.append(x)
    return factors


def main():
    # compute the number of prime factors of gcd(A, B)
    A, B = map(int, input().split())
    g = gcd(A, B)
    ans = len(prime_factors(g)) + 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def fact(n):
    b = 2
    li = []
    li.insert(0,1)
    while b*b<=n:
        while n%b == 0:
            n = n//b
            li.append(b)
        b+=1
    if n>1:
        li.append(n)

    return li
a,b = map(int,input().split())
c = gcd(a,b)
ans = set(fact(c))
print(len(ans))

Submission status: Accepted

Solution code:
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
a, b = map(int, input().split())
a_list = prime_factorize(a)
b_list = prime_factorize(b)
a_set = set(a_list)
b_set = set(b_list)

ans_set = a_set & b_set
ans_set.add(1)
print(len(ans_set))

Submission status: Accepted

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

def factorization(n):
    count=0
    for i in range(2,int(-(-n**0.5//1))+1):
        if n%i == 0:
            
            while n%i == 0:
                n //=i
            count +=1
            
    if n !=1:
        count +=1
    
    return count

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

d=gcd(a,b)
print(factorization(d)+1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


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

    # まずは最大公約数を求める
    G = gcd(A, B)

    # 最大公約数を素因数分解して素因数の数を求める
    result = factorizer(G)
    print(result)


# ユークリッド互除法
def gcd(a, b):
    # print("a:{0},b:{1}".format(a, b))
    if b == 0:
        return a
    return gcd(b, a % b)


def factorizer(n):
    """
    素因数分解するということは、
    2 ~ Nまでの数で割り続けるということ　試し割り
    割れなくなったら次の数で割る。
    素数を除いて、素因数の最大値は√nなので、それを超えたらやめる
    """
    res = {1: 1}  # １は必ずある
    calcEnd = n ** 0.5

    for i in range(2, int(calcEnd) + 2, 1):
        while n % i == 0:
            if res.get(i) is None:
                res[i] = 1
            else:
                res[i] += 1
            n /= i
            # print("n:{0}".format(n))

    # GCDが素数だった時の処理
    if n > 1:
        res[int(n)] = 1

    # print("res is {}".format(res))
    return len(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
#最大公約数
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)
#因数分解
def factorize(x):
    f=[]
    div=2
    while div**2<=x:
        while x%div==0:
            f.append(div)
            x=x//div
        div+=1
    if x>1:
        f.append(x)
    return f

"""def factorize(x):
    ans=1#約数１
    div=2
    while div**2<=x:
        while x%div==0:
            x=x//div
            flag=1
        if flag==1:
            ans+=1
        div+=1
        flag=0
    if x>1:
        ans+=1
    return ans"""

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

Submission status: Accepted

Solution code:
import fractions

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

C = fractions.gcd(A, B)

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

print(len(list(set(factorize(C)))) + 1)

Submission status: Accepted

Solution code:
from fractions import gcd
g = gcd(*map(int, input().split()))

f = 2
d = {}
while f**2 <= g:
    if g % f:
        f += 1
    else:
        d[f] = d.get(f,0) + 1
        g//=f

if g>1:
    d[g] =d.get(g,0) + 1

print(len(d)+1)

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]:
                b.append(a[i-1])
        if i == len(a) and i > 0:
            b.append(a[i-1])
        elif i == len(a) and i == 0:
            b.append(a[i])
    return b


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

ap = prime_factorize(a)
bp = prime_factorize(b)

c = []

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

print(len(c))

Submission status: Accepted

Solution code:
from collections import Counter
from fractions import gcd

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

g = gcd(a,b)

def sosuu(a):
    sosuu_list = set()
    sosuu_list.add(1)
    i = 2
    while 1:
        flag = True
        while a >= i*i:
            if a % i == 0:
                # print(a,i)
                a = a//i
                sosuu_list.add(i)
                flag = False
            else:
                i += 1
        if flag:
            sosuu_list.add(a)
            return sosuu_list
        i += 1

a = sosuu(g)
print(len(a))

Submission status: Accepted

Solution code:


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

def bunkai(n):
    sosu= {1}
    tmp = n
    
    if tmp%2 == 0:
        while tmp%2==0:
            tmp //=2
        sosu.add(2)
    
    for i in range(3,int(n**0.5)+1,2):
        if tmp%i == 0:
            while tmp%i==0:
                tmp //=i
            sosu.add(i)
            
    if tmp!=1:
        sosu.add(tmp)
                
    if sosu==[1]:
        sosu.add(n)
    
    return sosu

def check_sosu(n,x):
    ans=0
    tmp = n
    for i in x:
        if (tmp % i) == 0:
            ans+=1
    return ans

ans = check_sosu(B,bunkai(A))

print(ans)

Submission status: Accepted

Solution code:

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

def bunkai(n):
    sosu= {1}
    tmp = n
    stop_flag = n
    
    if tmp%2 == 0:
        while tmp%2==0:
            tmp //=2
        sosu.add(2)
    
    for i in range(3,n+1,2):
        if tmp%i == 0:
            while tmp%i==0:
                tmp //=i
            sosu.add(i)
            stop_flag = tmp 
            
        if i > stop_flag:
            break
        else:
            stop_flag = int(n/i)+1
            
    if tmp!=1:
        sosu.add(tmp)
                
    if sosu==[1]:
        sosu.add(n)
    
    return sosu

def check_sosu(n,x):
    ans=0
    tmp = n
    for i in x:
        if (tmp % i) == 0:
            ans+=1
    return ans

ans = check_sosu(B,bunkai(A))

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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

A, B = map(int, input().split())
n_gcd = gcd(A, B)
n_div = prime_decomposition(n_gcd)
print(len(n_div)+1)

Submission status: Accepted

Solution code:
import math
def solve():
    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 gcd( x, y ):
        while y != 0:
            x, y = y, x%y
        return x

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

    gcd_value = gcd(A , B)
    cd = []
    div = make_divisors(gcd_value)
    for value in div:
        if A % value == 0 and B % value == 0 and is_prime(value):
            cd.append(value)
    print(len(cd) + 1)
    
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
# coding: utf-8

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())
dA = make_divisors(A)
dB = make_divisors(B)
Al = list(set(dA) & set(dB))
ans_l = [1]

for i in range(1, len(Al)):
    cnt = 0
    for j in range(i):
        if Al[i] % Al[j] == 0:
            cnt += 1
    if cnt == 1:
        ans_l.append(Al[i])
print(len(set(ans_l)))

Submission status: Accepted

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

def gcd(a, b):
	if b == 0: return(a)
	else : return gcd(b, a % b)
		
G = gcd(A, B)
ctr = 1
for i in range(2, int(math.sqrt(G)) + 1):
    if G == 1: 
        break
    if G % i == 0: 
        ctr += 1
    while G % i == 0:
        G /= i
        
if G == 1:        
    print(ctr)
else:
    print(ctr + 1)

Submission status: Accepted

Solution code:
def f(n):
  ret={1}
  for i in range(2,int(n**.5)+1):
    if n%i==0:
      ret.add(i)
      while n%i==0:
        n//=i
    else:pass
  if n:
    ret.add(n)
  return ret
a,b=map(int,input().split())
print(len(f(a)&f(b)))