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:
import math
def readinput():
    a,b=list(map(int,input().split()))
    return a,b

def myFactorization(n):
    '''nを素因数分解する

    戻り値: factList = [[prime1, exp1], [prime2, exp2],...] 
           n=(prime1)**exp1 * (prime2)**exp2 * ...
    '''

    factList=[]
    temp=n
    cnt=0
    while(temp%2==0):
        temp=temp//2
        cnt+=1
    if(cnt>0):
        factList.append([2,cnt])

    m=int(math.sqrt(n))+1
    for i in range(3,m+1,2):
        cnt=0
        while(temp%i==0):
            temp=temp//i
            cnt+=1
        if(cnt>0):
            factList.append([i,cnt])
        if(temp==1):
            break
    if(temp>1):
        factList.append([temp,1])
    return factList

def euclid(x,y):
    if x<y:
        x,y=y,x
    
    while y>0:
        r=x%y
        x=y
        y=r
    return x

def main(a,b):
    gcd=euclid(a,b)
    factList=myFactorization(gcd)
    return len(factList)+1

if __name__=='__main__':
    a,b=readinput()
    ans=main(a,b)
    print(ans)

Submission status: Accepted

Solution code:
#　解説確認後
#　参考サイト「けんちょんの競プロ精進記録」
#　URL: https://atcoder.jp/contests/abc142/tasks/abc142_d

import math
def prime_factorize(n): # 素因数分解
    p = 2
    res = []
    while p*p <= n:
        if n % p: # 割り切れない
            p += 1
            continue
        num = 0
        while n % p == 0:
            n //= p
            num += 1
        res.append((p,num))
        p += 1
    if n != 1: res.append((n,1))
    return res

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

G = math.gcd(a,b) # 最大公約数

pl = prime_factorize(G)

print(len(pl)+1) # 1+n個なので

Submission status: Accepted

Solution code:
def make_divisors(n):
    from collections import deque
    divisors = deque([])
    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)
    lst_divisors = list(divisors)
    lst_divisors.sort()
    return lst_divisors

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

ya = set(make_divisors(a))
yb = set(make_divisors(b))

cand = list(ya&yb)
cand.sort()

#print(cand)

ans = []
if len(cand) > 1:
    for n in cand[1:]:
        if ans:
            for waru in ans:
                if n%waru == 0:
                    break
            else:
                ans.append(n)
        else:
            ans.append(n)
#print(ans)
print(len(ans)+1)

Submission status: Accepted

Solution code:
def make_divisors(n):
    from collections import deque
    divisors = deque([])
    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)
    lst_divisors = list(divisors)
    lst_divisors.sort()
    return lst_divisors

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

ya = set(make_divisors(a))
yb = set(make_divisors(b))

cand = list(ya&yb)
cand.sort()

#print(cand)

ans = []
if len(cand) > 1:
    for n in cand[1:]:
        if ans:
            for n in cand[1:]:
                for waru in ans:
                    if n%waru == 0:
                        break
                else:
                    ans.append(n)
        else:
            ans.append(n)
#print(ans)
print(len(ans)+1)

Submission status: Accepted

Solution code:
from math import floor, sqrt
from collections import defaultdict
from math import gcd
def factors(n):
    d = defaultdict(int)
    for i in range(2,floor(sqrt(n))+1):
        while n % i == 0:
            n //= i
            d[i] += 1
        if n == 1:
            break
    if n != 1:
        d[n] += 1
    return d

A,B = map(int,input().split())
N = gcd(A,B)
fac = factors(N)
print(len(fac)+1)

Submission status: Accepted

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

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

    return arr

a, b = map(int, input().split())
fa = factorization(a)
fb = factorization(b)

i = 0
j = 0
cnt = 1
while i < len(fa) and j < len(fb):
  if fa[i][0] == fb[j][0]:
    cnt += 1
    i += 1
    j += 1
  elif fa[i][0] < fb[j][0]:
    i += 1
  else:
    j += 1

print(cnt)

Submission status: Accepted

Solution code:
"""
    こんにちは。これはクシャルです
    
    Author : thekushalghosh (クシャル)
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time
start_time = time.time()
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################

def solve():
    a,b = invr()
    print(len(set(prime_factors(math.gcd(a,b)))) + 1)
            
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################
 
def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
        sys.stdout.close()
    
#---------------------- USER DEFINED INPUT FUNCTIONS ----------------------#
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
 
#------------------ USER DEFINED PROGRAMMING FUNCTIONS ------------------#
def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1],1
    return(q)
 
def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97],1
    return(q)

def factors(n):
    q = []
    for i in range(1,int(n ** 0.5) + 1):
        if n % i == 0: q.append(i); q.append(n // i)
    return(list(sorted(list(set(q)))))

def prime_factors(n):
    q = []
    while n % 2 == 0: q.append(2); n = n // 2
    for i in range(3,int(n ** 0.5) + 1,2):
        while n % i == 0: q.append(i); n = n // i
    if n > 2: q.append(n)
    return(list(sorted(q)))

#-----------------------------------------------------------------------#
        
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
main()

Submission status: Accepted

Solution code:
a, b = map(int, input().split())
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    return arr
c = factorization(a)
d = factorization(b)
cnt = 1
for i,j in c:
  for k,l in d:
    if i == k:
      cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc142/tasks/abc142_d
# 公約数とは、最大公約数の約数

import sys
import math
from functools import reduce

input = sys.stdin.readline

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


def gcd(*numbers):
    return reduce(math.gcd, numbers)

# 素因数分解
# 考え方：1~√nまで実際に割れるか試せば良いが、割れた場合は割れる限りその数で割り続ける
# 計算量：O(√n)
def prime_factorize(n):
    i = 2
    primes = []
    while i * i <= n:
        if n % i != 0:
            i += 1
            continue
        exp = 0
        while n % i == 0:
            exp += 1
            n = n // i
        primes.append([i, exp])
        i += 1
    # 最後に残った数は1か素数にしかならない
    if n != 1:
        primes.append([n, 1])
    return primes

g = gcd(A, B)
divisors = prime_factorize(g)
print(len(divisors)+1)

Submission status: Accepted

Solution code:
from math import gcd


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


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

fac = factorization(n_gcd)
ans = 0
if fac[0][0] != 1:
    ans += 1

ans += len(fac)
print(ans)

Submission status: Accepted

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

a, b = map(int, input().split())
_min, _max = min(a, b), max(a, b)
prime_factors = []
i = 2
while i ** 2 <= _min:
    ext = 0
    while _min % i == 0:
        ext += 1
        _min //= i
    if ext:
        prime_factors.append((i, ext))
    i += 1
if _min != 1:
    prime_factors.append((_min, 1))

ans = 1
for pf, _ in prime_factors:
    if _max % pf == 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def integer_factorization(n):
    prime_count = collections.Counter()
    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n //= i
            prime_count[i] += 1
    if n > 1:
        prime_count[n] += 1
    return prime_count

def main():
    a, b = LI()
    d1 = integer_factorization(a)
    d2 = integer_factorization(b)
    dk1 = [k for k, v in d1.items()]
    dk2 = [k for k, v in d2.items()]
    ans = set()
    for a in dk1:
        if d2[a] == 0:
            continue
        ans.add(a)

    for b in dk2:
        if d1[b] == 0:
            continue
        ans.add(b)

    print(1 + len(ans))


main()

Submission status: Accepted

Solution code:
def main():
    N, M = (int(i) for i in input().split())

    def prime_factorize(n):
        res = set()
        for i in range(2, n+1):
            if i*i > n:
                break
            if n % i != 0:
                continue
            ex = 0
            while n % i == 0:
                ex += 1
                n //= i
            res.add(i)
        if n != 1:
            res.add(n)
        return res

    pf_N = prime_factorize(N)
    pf_M = prime_factorize(M)

    ans = 1 + len(pf_N & pf_M)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, M = (int(i) for i in input().split())

    def prime_factorize(n):
        res = []
        for i in range(2, n+1):
            if i*i > n:
                break
            if n % i != 0:
                continue
            ex = 0
            while n % i == 0:
                ex += 1
                n //= i
            res.append((i, ex))
        if n != 1:
            res.append((n, 1))
        return res

    from math import gcd
    g = gcd(N, M)
    pf = prime_factorize(g)

    ans = 1 + len(pf)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, M = (int(i) for i in input().split())

    def enum_divisors(n):
        # 約数列挙
        divs = set()
        for i in range(1, n+1):
            if i*i > n:
                break
            if n % i == 0:
                divs.add(i)
                if n//i != i:
                    # i が平方数でない
                    divs.add(n//i)
        return divs

    divs = enum_divisors(N) & enum_divisors(M)
    ans = 1
    v = 1
    from math import gcd
    for s in sorted(divs):
        if s == 1:
            continue
        if gcd(v, s) == 1:
            v *= s
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

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))
    table = sorted(table)
    return table

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

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

A_list = set(divisor(A))
B_list = set(divisor(B))

list = A_list & B_list

cnt = 1

for i in list:
    if is_prime(i):
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import numpy as np

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))
    table = sorted(table)
    return table

def make_prime(U):
    is_prime = np.zeros(U,np.bool)
    is_prime[2] = 1
    is_prime[3::2] = 1
    M = int(U**.5)+1
    for p in range(3,M,2):
        if is_prime[p]:
            is_prime[p*p::p+p] = 0
    return is_prime, is_prime.nonzero()[0]
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

A_list = set(divisor(A))
B_list = set(divisor(B))

list = A_list & B_list

#_, primes = make_prime(10**8)

cnt = 1

for i in list:
    if is_prime(i):
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import math
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))


# a, bの公約数の集合 と a, bの最大公約数の約数の集合 は同値
# a, bの最大公約数の約数のうち、互いに素なもの <= a, bの最大公約数の素因数と(と 1)
# n の素因数分解はO(√ n)で行える

# ↑の方法とは異なる解法
def prime_factrize(n: int) -> list:
    # 素因数のリストを取得(重複する素因数を含む)
    # 例 : 18 -> [2, 3, 3]
    if n < 2:
        return []
    p_factors = []
    # 2だけ先に取り分けておく
    while n % 2 == 0:
        p_factors.append(2)
        n //= 2
    # 残りの奇数の素因数を探す
    f = 3
    while f * f <= n:
        if n % f == 0:
            p_factors.append(f)
            n //= f
        else:
            f += 2
    # nが素数の場合
    if n != 1:
        p_factors.append(n)
    return p_factors


def main():
    a, b = LI()
    # a, bの素因数を取り出し、共通する素因数(に1を加えたもの)の個数を数える
    pf_a = prime_factrize(a)
    pf_b = prime_factrize(b)
    pf = (set(pf_a) & set(pf_b)) | {1}
    print(len(pf))


main()

Submission status: Accepted

Solution code:
import math
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))


# a, bの公約数の集合 と a, bの最大公約数の約数の集合 は同値
# a, bの最大公約数の約数のうち、互いに素なもの <= a, bの最大公約数の素因数と(と 1)
# n の素因数分解はO(√ n)で行える

# ↑の方法とは異なる解法
def prime_factrize(n: int) -> list:
    # 素因数のリストを取得(重複する素因数を含む)
    # 例 : 18 -> [2, 3, 3]
    if n < 2:
        return []
    p_factors = []
    # 2だけ先に取り分けておく
    while n % 2 == 0:
        p_factors.append(2)
        n //= 2
    # 残りの奇数の素因数を探す
    f = 3
    while f * f <= n:
        if n % f == 0:
            p_factors.append(f)
            n //= f
        else:
            f += 2
    # nが素数の場合
    if n != 1:
        p_factors.append(n)
    return p_factors


def main():
    a, b = LI()
    gcd = math.gcd(a, b)
    pf = prime_factrize(gcd)
    pf = set(pf)  # 素因数だけ取り出す
    # 1 を加える
    pf.add(1)
    print(len(pf))


main()

Submission status: Accepted

Solution code:
import math
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))


# a, bの公約数の集合 と a, bの最大公約数の約数の集合 は同値
# a, bの最大公約数の約数のうち、互いに素なもの <= a, bの最大公約数の素因数と(と 1)
# n の素因数分解はO(√ n)で行える


def get_primes(n):
    root_n = int(n ** 0.5)
    is_prime = [True] * (n + 1)
    is_prime[0], is_prime[1] = False, False
    for i in range(2, root_n + 1):
        if not is_prime[i]:
            continue
        # i の倍数の素数判定をFalseにする
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


def prime_factrize(n: int) -> list:
    # 素因数のリストを取得(重複する素因数を含む)
    # 例 : 18 -> [2, 3, 3]
    if n < 2:
        return []
    p_factors = []
    # 2だけ先に取り分けておく
    while n % 2 == 0:
        p_factors.append(2)
        n //= 2
    # 残りの奇数の素因数を探す
    f = 3
    while f * f <= n:
        if n % f == 0:
            p_factors.append(f)
            n //= f
        else:
            f += 2
    # nが素数の場合
    if n != 1:
        p_factors.append(n)
    return p_factors


def main():
    a, b = LI()
    gcd = math.gcd(a, b)
    pf = prime_factrize(gcd)
    pf = set(pf)  # 素因数だけ取り出す
    # 1 を加える
    pf.add(1)
    print(len(pf))


main()

Submission status: Accepted

Solution code:
def main():

    def factorization(n):
        l = []
        tmp = n
        i = 2
        while i*i <= n:
            if tmp%i == 0:
                while tmp%i == 0:
                    tmp //= i
                l.append(i)
            i += 1
        if tmp != 1:
            l.append(tmp)
        if l == []:
            if n != 1:
                l.append(n)
        return l

    a, b = map(int, input().split())
    a_f = factorization(a)
    b_f = factorization(b)
    ans = len(set(a_f) & set(b_f)) + 1
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

from collections import defaultdict
def factorization(n):
    d = defaultdict(int)
    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 len(d) == 0:
        d[n] = 1
    return d
ans = 0
d = factorization(A)
d[1] = 1
for x in d.keys():
    if B%x == 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from math import gcd

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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 main():
    A, B = map(int, readline().split())

    g = gcd(A, B)
    factors = prime_factorize(g)

    print(len(set(factors)) + 1)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def div(n):
    divs = set([1])
    i = 2
    while i*i <= n:
        while n%i==0:
            divs.add(i)
            n//=i
        i+=1
        
    if n>1:
        divs.add(n)
        
    return divs

div_set = div(a) & div(b)

print(len(div_set))

Submission status: Accepted

Solution code:
import math
def prime(g):
    l = []
    p = 2
    while p * p <= g:
        if g % p != 0:
            p += 1
            continue
        while g % p == 0:
            g //= p
        l.append(p)
        p += 1
    if g != 1:
        l.append(g)
    return len(l)

a, b = map(int, input().split())
g = math.gcd(a, b)
print(prime(g) + 1)

Submission status: Accepted

Solution code:
from math import gcd
def main():
    def factorization(n):
        arr = []
        temp = n
        for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
            if temp % i == 0:
                cnt = 0
                while temp % i == 0:
                    cnt += 1
                    temp //= i
                arr.append([i, cnt])
        if temp != 1:
            arr.append([temp, 1])
        if arr == []:
            arr.append([n, 1])
        return arr

    a, b = map(int, input().split())
    g = gcd(a,b)
    g_fac = factorization(g)
    r = len(g_fac)
    if g_fac[0][0] != 1:
        r += 1
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

pa = []
for i in range(2, roota + 2):
    if a % i == 0:
        pa.append(i)
        while a % i == 0:
            a //= i
if (pcheck(a) == True) & (a != 1):
    pa.append(a)
cd = []
for i in range(len(pa)):
    if b % pa[i] == 0:
        cd.append(pa[i])
print(len(cd) + 1)

Submission status: Accepted

Solution code:
import math

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

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

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

    return arr
a, b = map(int, input().split())
c = math.gcd(a, b)
d = factorization(c)
if a == 1 or b == 1:
    print(1)
else:
    print(len(d)+1)

Submission status: Accepted

Solution code:
from math import gcd

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

d = gcd(A, B)
ans = 1
i = 2
while i <= pow(d, 1/2)+1:
  if d%i == 0:
    ans += 1
    while d%i == 0:
      d //= i
  i += 1
ans += (d > 1)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
def prime_factorize(n):
    f = 2
    primes = []
    while f * f <= n:
        if n % f != 0:
            f += 1
            continue
        primes.append(f)
        n //= f
    if n > 1:
        primes.append(n)
    return list(set(primes))
a, b = map(int, input().split())
ab_primes = Counter(prime_factorize(a) + prime_factorize(b))
ans = 0
for prime in ab_primes.values():
    if prime > 1:
        ans += 1
print(1 + ans)

Submission status: Accepted

Solution code:
import math

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

A_prime = set(prime_factorize(A))
B_prime = set(prime_factorize(B))

res = A_prime & B_prime

print(len(res)+1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        lower, upper = [], []
        i = 1
        while i * i <= n:
            if n % i == 0:
                lower.append(i)
                if i != n // i:
                    upper.append(n // i)
            i += 1
        return lower + upper[::-1]

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

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

    @staticmethod
    def fact(N):
        res = {}
        tmp = N
        for i in range(2, int(N ** 0.5 + 1) + 1):
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if cnt > 0:
                res[i] = cnt
        if tmp != 1:
            res[tmp] = 1
        if res == {}:
            res[N] = 1
        return res


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def solve():
    A, B = Scanner.map_int()
    div_A = Math.divisor(A)
    div_B = Math.divisor(B)
    X = set(div_A) & set(div_B)
    ans = 0
    for x in X:
        if Math.is_prime(x):
            ans += 1
    print(ans + 1)


def main():
    # sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
a,b=map(int,input().split())
num=math.gcd(a,b)
if num==1:
    print(1)
else:
    def f(n):
        arr = []
        temp = n
        for i in range(2, int(-(-n**0.5//1))+1):
            if temp%i==0:
                cnt=0
                while temp%i==0:
                    cnt+=1
                    temp //= i
                arr.append([i, cnt])

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

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

        return arr
    l1=f(num)
    print(len(l1)+1)

Submission status: Accepted

Solution code:
import math

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

def yakusuu(n):
    l = []
    u = []
    i = 1
    while(i*i <= n):
        if(n%i == 0):
            l.append(i)
            if(i != n//i):
                u.append(n//i)
        i += 1
    return l+u[::-1]
        
A, B = map(int, input().split())
a = set(yakusuu(A))
b = set(yakusuu(B))

lst = []
for i in a:
    if(i in b):
        lst.append(i)
   
cnt = 0
for i in range(len(lst)):
    if(isprime(lst[i])):
        cnt += 1
    
print(cnt)

Submission status: Accepted

Solution code:
import sys

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

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

    pf_A = factorization(A)
    pf_B = factorization(B)

    if pf_A[0][0] == 1 or pf_B[0][0] == 1:
        pfs = []
    else:
        pfs = set([i for i,num in pf_A]) & set([i for i,num in pf_B])

    print(len(pfs)+1)
main()

Submission status: Accepted

Solution code:
from math import gcd

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

m = gcd(A, B)
#print(m)

num = int(m**0.5) #mに対する素因数分解は、int(√m)の場合を調べればよい
ans = 1

for i in range(2,num+1):
    if m%i:
        continue
    ans += 1
    while not m%i:
        m /= i

if m>1:
    ans+=1 #m+1が素因数の場合がある

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

A,B=map(int,input().split())
p=set([1])
g=gcd(A,B)
for d in range(2,g):
    while g%d==0:
        p.add(d)
        g//=d
    if (d*d>=g): break
if g>=2:
    p.add(g)
print(len(p))

Submission status: Accepted

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

A,B=map(int,input().split())
p=set([1])
g=gcd(A,B)
for d in range(2,g):
    while g%d==0:
        p.add(d)
        g//=d
    if (d*d>=g): break
if g>=2:
    p.add(g)
print(len(p))

Submission status: Accepted

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

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

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

    return arr
a,b=map(int,input().split())
g=math.gcd(a,b)

if g==1:
    print(g)
else:
    arr=factorization(g)
    print(len(arr)+1)

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
g=1
while 1:
  if a==b:
    g=a
    break
  if a<b:
    k=a
    a=b
    b=k
  a-=b
ans=1
i=2
while i*i<=g:
  if g%i==0:
    ans+=1
    while g%i==0:
      g//=i
  i+=1
if g!=1:
  ans+=1
print(ans)

Submission status: Accepted

Solution code:
from math import gcd
from itertools import combinations


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


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


a, b = map(int, input().split())
se = set(make_divisors(a)) & set(make_divisors(b))
ans = 1
for i in se:
    if is_prime(i):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def gcd(a,b):
    if a%b == 0:
        return b
    else:
        return gcd(b, a%b)
ans = 1
def fact(n):
    global ans
    p = 2
    while p**2 <= n:
        flag = False
        while n%p == 0:
            flag = True
            n /= p
        p += 1
        if flag:
            ans += 1
    if n!= 1:
        ans += 1
a,b = map(int, input().split())
g = gcd(a,b)
fact(g)
print(ans)

Submission status: Accepted

Solution code:
import math

A,B = map(int,input().split())
G = math.gcd(A,B)

N = G
#素因数分解
sep = []
for i in range(2,int(math.sqrt(N))+2,1):
    if N % i ==0:
        count = 0
        while N % i == 0:
            N = N//i
            count += 1
        sep.append([i,count])
if N != 1:
    sep.append([N,1])

print(len(sep)+1)