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 .

Solution (Python):
def factorization(n):
    res = set()
    tmp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if tmp % i == 0:
            while tmp % i == 0:
                tmp //= i
            res.add(i)
    res.add(tmp)
    if not res:
        res.add(n)
    return res

a, b = map(int,input().split())
ans = factorization(a) & factorization(b) | {1}
print(len(ans))

Solution (Python):
def factorization(n):
    res = set()
    tmp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if tmp % i == 0:
            while tmp % i == 0:
                tmp //= i
            res.add(i)
    if tmp != 1:
        res.add(tmp)
    if not res:
        res.add(n)
    return res

a, b = map(int,input().split())
ans = factorization(a) & factorization(b) | {1}
print(len(ans))

Solution (Python):
def factorization(n):
    res = set()
    tmp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if tmp % i == 0:
            cnt = 0
            while tmp % i== 0:
                cnt += 1
                tmp //= i
            res.add(i)
    if tmp != 1:
        res.add(tmp)
    if not res:
        res.add(n)
    return res

a, b = map(int,input().split())
ans = factorization(a) & factorization(b) | {1}
print(len(ans))

Solution (Python):
def prime_facorize(N):
    res = {1}
    for i in range(2, int(N ** 0.5) + 1):
        while N % i == 0:
            res.add(i)
            N /= i

        if N <= 1:
            break
    if N > 1:
        res.add(N)
    return res


A, B = map(int, input().split())
commons = prime_facorize(A) & prime_facorize(B)
print(len(commons))

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

a, b = map(int,input().split())
a_list = [x[0] for x in factorization(a)]
b_list = [x[0] for x in factorization(b)]
ans = set(a_list) & set(b_list) | {1}
print(len(ans))

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

a, b = map(int,input().split())
a_list = [x[0] for x in factorization(a)]
b_list = [x[0] for x in factorization(b)]
ans = set(a_list) & set(b_list) | {1}
print(len(ans))

Solution (Python):
from fractions import gcd


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


def main():
    A, B = map(int, input().split())
    g = gcd(A, B)
    lst_prime_numbers = prime_factorize(g)
    ans = 1 + len(set(lst_prime_numbers))
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from fractions import gcd
from math import sqrt
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def prime_factorize(n):
    result = []
    for i in range(2, int(sqrt(n)) + 1):
        if n % i != 0:
            continue
        t = 0
        while n % i == 0:
            n //= i
            t += 1
        result.append((i, t))
        if n == 1:
            break
    if n != 1:
        result.append((n, 1))
    return result


def main():
    a, b = map(int, input().split())
    print(len(prime_factorize(gcd(a, b))) + 1)


if __name__ == '__main__':
    main()

Solution (Python):
import math
 
def gcd(a,b):
  if b == 0:
    return a
  else:
    return gcd(b, a % b)

A, B = map(int, input().split(" "))
if A >= B:
  C = gcd(A,B)
else:
  C = gcd(B,A)

c = math.ceil(math.sqrt(C)) + 1
l = [1]
f = [1] + [0]*c

for i in range(2,c+1):
  if f[i-1] == 0:
    f[i-1] = 1
    if C % i == 0:
      l.append(i)
      while C % i == 0:
        C //= i
    for j in range(i+i, c+1, i):
      f[j-1] = 1

if C > 1:
  l.append(C)

print(len(l))

Solution (Python):



def run_prime_factorization(max_number: int) -> dict:
    '''Run prime factorization.
    Args:
        max_number: Int of number (greater than 1).
    Returns:
        A dictionary's items ((base, exponent) pairs).
    Landau notation: O(log n)
    '''

    from math import sqrt

    ans = dict()
    remain = max_number

    for base in range(2, int(sqrt(max_number)) + 1):
        if remain % base == 0:
            exponent_count = 0

            while remain % base == 0:
                exponent_count += 1
                remain //= base

            ans[base] = exponent_count

    if remain != 1:
        ans[remain] = 1

    return ans


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

    
    
    
    count = 1
    result_a = run_prime_factorization(a)
    result_b = run_prime_factorization(b)
    count += len(result_a.keys() & result_b.keys())
    print(count)


if __name__ == '__main__':
    main()

Solution (Python):



class Prime(object):
    '''Represents a snippet for prime numbers.
    '''

    def __init__(self, number):
        self.number = number
        self._values = []

    def is_included(self) -> bool:
        '''Determine whether it is a prime number.
        Args:
            number: Int of number (greater than 0).
        Returns:
            True if the input number was prime.
            False if the input number was not prime.
        See:
            https://qiita.com/srtk86/items/874639e361917e5016d4
            https://docs.python.org/ja/3/library/2to3.html?highlight=isinstance
        '''

        from math import sqrt

        if (self.number <= 1) or (isinstance(self.number, float)):
            return False

        for i in range(2, int(sqrt(self.number)) + 1):
            if self.number % i == 0:
                return False

        return True

    def generate(self) -> list:
        '''Generate a list of prime numbers using sieve of Eratosthenes.
        Returns:
            A list of prime numbers that is eqaul to or less than the input
            number.
        Landau notation: O(n log log n)
        See:
            https://beta.atcoder.jp/contests/abc110/submissions/3254947
        '''

        if self._values:
            return self._values

        is_met = [True for _ in range(self.number + 1)]
        is_met[0] = False
        is_met[1] = False

        for i in range(2, self.number + 1):
            if is_met[i]:
                self._values.append(i)

                for j in range(2 * i, self.number + 1, i):
                    is_met[j] = False
        return self._values


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

    
    for i in range(1, int(a ** 0.5) + 1):
        if a % i == 0:
            set_a.add(i)
            set_a.add(a // i)

    for i in range(1, int(b ** 0.5) + 1):
        if b % i == 0:
            set_b.add(i)
            set_b.add(b // i)

    
    set_ab = set_a & set_b
    count = 1

    
    for s in set_ab:
        p = Prime(s)

        if p.is_included():
            count += 1

    print(count)


if __name__ == '__main__':
    main()

Solution (Python):
import math


def main():
    inputs = input().split()
    inputs = [int(i) for i in inputs]

    a = inputs[0]
    b = inputs[1]

    g = n = gcd(a, b)
    d = {}

    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i:
            continue
        d[i] = i
        while n % i == 0:
            n /= i

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

    print(len(d) + 1)


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


if __name__ == "__main__":
    main()

Solution (Python):
from fractions import gcd
a,b = map(int,input().split())
gcdab = gcd(a, b)
d = {}
j = 2
while j*j<=gcdab:
  while gcdab%j==0:
    gcdab //= j
    if j in d:
      d[j] += 1
    else:
      d[j] = 1
  j += 1
if gcdab>1:
  d[gcdab] = 1
print(len(d)+1)

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

while b!=0:
  a,b=b,a%b

n=a
s=set()
s.add(1)

while n%2==0:
  n //= 2
  s.add(2)

f=3
while f*f<=n:
  if n%f==0:
    n //= f
    s.add(f)
  else:
    f += 2

if n!=1:
  s.add(n)

print(len(s))

Solution (Python):


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

gcd = fractions.gcd(A,B)
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

    soinsulist=factorization(gcd)
    print(len(soinsulist)+1)

Solution (Python):
from sys import stdin
A, B = [int(_) for _ 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
print(len(set(prime_factorize(A)) & set(prime_factorize(B)))+1)

Solution (Python):
import numpy as np
a, b = map(int, input().split())
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
n = gcd(a, b)

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

print(len(set(table))+1)

Solution (Python):
from math import sqrt


def get_divisors(n):
    """
    約数の個数を数える
    :param n: 自然数
    :return: 約数の個数, 約数の set
    """
    res = {1}
    cnt = 1
    for i in range(2, int(sqrt(n)) + 1):
        if n % i == 0:
            cnt += 1

        while n % i == 0:
            res.add(i)
            n /= i
        if (n <= 1): break

    if n > 1:  
        res.add(n)
    return cnt, res


A, B = [int(_) for _ in input().split()]
print(len(get_divisors(A)[1] & get_divisors(B)[1]))

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

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

A_prime = set(prime_decomposition(A))
B_prime = set(prime_decomposition(B))
union = A_prime & B_prime
print(len(union)+1)

Solution (Python):
def dfs(n):
    table =[]
    i = 2
    while n >= i**2:
        while n % i == 0:
            if i not in table:
                table.append(i)
            n /= i
        i += 1
    if n > 1:
        table.append(int(n))
    return table

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

yaku_A = dfs(A)
yaku_B = dfs(B)
count = 1

for i in yaku_A:
  if i in yaku_B:
    count += 1

print(count)

Solution (Python):

from fractions import gcd
import math


def primeFactor(n):
    flg = 0
    count = 0
    tmp = math.sqrt(n)
    i = 2

    if n == 1:
        return 1

    while i <= tmp:
        
        if n % i == 0:
            if flg == 0:
                flg = 1
                count += 1
            n = n // i
        else:
            flg = 0
            i += 1
    
    
    
    if n > 1:
        count += 1
    
    count += 1
    return count



m,n = map(int,input().split())
p = gcd(m,n)

ans = primeFactor(p)
print(ans)

Solution (Python):
from collections import defaultdict

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

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

d = defaultdict(int)
g = gcd(A,B)
tmp = g
for i in range(2, int(g ** 0.5) + 1):
    if tmp % i == 0:
        while tmp % i == 0:
            d[i] += 1
            tmp //= i
if tmp != 1:
    d[tmp] += 1

print(len(d)+1)

Solution (Python):
from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))


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

    divisors.sort()
    return divisors

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

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

    return True

a,b = inpl()
res = 0
gc = fractions.gcd(a,b)
div = make_divisors(gc)

for i in div:
    if is_prime(i):
        res += 1
print(res)

Solution (Python):
import fractions as fc

A, B = [int(x) for x in input().split()]
C = fc.gcd(A, B)
b = 2
ans =  1
while b * b <= C:
  if C % b == 0:
    ans += 1
    while C % b == 0:
      C //= b
  if C == 1:
    break
  b += 1
if C > 1:
  ans += 1
print(ans)

Solution (Python):

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

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

Solution (Python):

import numpy as np


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

def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2, N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

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

    
    return divisors

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        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 prime3(n):
    counter = 0
    primes = [2, 3]

    for n in range(5, n, 2):
        isprime = True
        for i in range(1, len(primes)):
            counter += 1
            if primes[i] ** 2 > n:
                break
            counter += 1
            if n % primes[i] == 0:
                isprime = False
                break
        if isprime:
            primes.append(n)
    return primes

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

count=0
ad=set(make_divisors(a))
bd=set(make_divisors(b))

common=ad & bd

l=[]
for s in common:
    if is_prime(s):
        count+=1
print(count+1)

Solution (Python):
def GCD(a, b):
  if a < b:
    a = a+b
    b = a-b
    a -= b
  q = a//b
  r = a%b
  if r == 0:
    return b
  else:
    return GCD(b, r)

A, B = map(int, input().split())
g = GCD(A, B)
tmp = g
m = 1
ps = []
while m**2 <= g:
  if tmp % m == 0:
    ps.append(m)
    tmp //= m
    m = 2
  else:
    m += 1
ps.append(tmp)
ps = list(set(ps))
print(len(ps))

Solution (Python):
import sys
sys.setrecursionlimit(12345678)
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def primes(n):
    pl = [1]
    if n == 2:
        pl.append(2)
        return pl
    if n == 3:
        pl.append(3)
        return pl

    i = 2
    while i * i <= n:
        if n % i == 0:
            pl.append(i)
            while n % i == 0:
                n //= i
        i += 1
    if n > 1:
        pl.append(n)
    return pl


def main():
    a, b = map(int, input().split())
    ap = set(primes(a))
    bp = set(primes(b))
    
    
    
    print(len(ap & bp))


if __name__ == '__main__':
    main()

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

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

c = prime_factorize(gcd)
d = set(c)
print(len(d)+1)

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

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

c = collections.Counter(prime_factorize(gcd))
print(len(list(c.keys()))+1)

Solution (Python):
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
if g>1:
  l.append(g)
print(len(set(l))+1)

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

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

n = gcd(a, b)

if n == 1:
    print(1)
    exit()

m = 2
ans = 1
while m <= (n ** 0.5):
    if n % m == 0:
        ans += 1
        while n % m == 0:
            n //= m
    if n == 1:
        break
    m += 1

if n > 1:
    ans += 1

print(ans)

Solution (Python):
a,b=map(int,input().split())
t=min(a,b)
t1=t
s=max(a,b)
c=1
i=2
while t > 1 and i <=int(t1**(0.5)+1):
  frag=0
  while t%i ==0:
    t=t/i
    if frag==0 and s%i ==0:
      c=c+1
    frag=1
  if i==2:
    i=3
  else:
    i= i+2
if s%t==0 and t > int(t1**(0.5)+1):
  c=c+1
print(c)

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

def factorization(n):
	lista=[]
	temp=n
	
	i=2
	while i<=int(n**0.5//1):
		if temp%i==0:
			lista.append(i)
			temp=temp//i
		else:
			i=i+1
	if temp!=1:
		lista.append(temp)


	
	
	return lista
	


seta=set(factorization(a))
setb=set(factorization(b))
setc=seta&setb

ans=len(setc)+1
print(ans)

Solution (Python):
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)
    if temp!=1:
        arr.append(temp)
    if arr==[]:
        arr.append(n)
    return arr

A,B=map(int,input().split())
l=factorization(A)
c=0
for x in l:
    c += 1 if B%x==0 else 0
print(1 if l==[1] else c+1)

Solution (Python):
from fractions import gcd


def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    m = 3
    while m ** 2 <= n:
        if n % m == 0:
            return False
        m += 2
    return True


A, B = map(int, input().split())
d = gcd(A, B)
n = 1
s = set()
while n ** 2 <= d:
    if d % n == 0:
        if is_prime(n):
            s.add(n)
        if is_prime(d // n):
            s.add(d // n)
    n += 1
s.add(1)
print(len(s))

Solution (Python):
import sys
input = sys.stdin.readline
import fractions
import collections
def main():
    A,B = map(int,input().split())
    gcd = fractions.gcd(A,B)
    def prime(n):
        a = []
        while n%2 == 0:
            a.append(2)
            n //= 2
        f = 3
        while f*f <= n:
            if n%f == 0:
                a.append(f)
                n //= f
            else:
                f += 2
        if n!=1:
            a.append(n)
        return a

    c = collections.Counter(prime(gcd))
    print(len(list(c.keys()))+1)

if __name__ == "__main__":
    main()

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

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

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

g = gcd(A, B)
f = prime_factor(g)

ans = len(f)
if f[0][0] != 1:
    ans += 1
print(ans)

Solution (Python):
import sys


	
def gcd(a,b):
	if a < b:
		a,b = b,a
	
	while b!=1:
		tt=a%b
		if tt==0:
			return b
		a,b=b,tt
		
	return b
	
def is_sosuu(v, pl):
	if v == 2:
		return True
	if v <= 1:
		return False
	for p in pl:
		if v %p==0:
			return False
	return True
	
def bbb(val):
	return int(val**(0.5))+1
	
def main():
	b , c = map(int, input().split())
	sk=gcd(b,c)
	
	
	ans=1
	sosuu_list=[]
	using=set()
	using.add(1)
	sss=sk
	for i in range(2,bbb(sss)+1):
		while sss % i == 0:
			sss = sss // i
			using.add(i)
			if bbb(sss) < i:
				using.add(sss)
				break
	using.add(sss)
	print(len(using))
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):



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

def solve():
    A, B = map(int, input().split())
    
    a_arr = factrization(A)
    b_arr = factrization(B)
    
    s_ans = a_arr & b_arr
    print(len(s_ans)+1)


if __name__ == '__main__':
    solve()

Solution (Python):
import random

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

def is_prime(q,k=50):
    q = abs(q)
    
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        
        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

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


def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a

def divisorize(fct):
    b, e = fct.pop()  
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

x=[]
y=[]
z=[]

if a==1:
  x.append(1)
else:
  fct_a = factorize(a)
  for div in divisorize(fct_a):
    x.append(num(div))

if b==1:
  y.append(1)
else:
  fct_b = factorize(b)
  for div in divisorize(fct_b):
    y.append(num(div))

z=x+y
w=[m for m in set(z) if z.count(m) > 1]

c=0

for i in range(0,len(w)):
  if is_prime(w[i]):
    c+=1
print(c+1)

Solution (Python):

import sys, fractions, math

def eratosthenes_sieve(n: int):
    """
    エラトステネスの篩を用いてn以下の素数を求める
    """
    table = [0] * (n + 1)
    prime_list = []
    
    for i in range(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in range(i + i, n + 1, i):
                table[j] = 1
    
    return prime_list

def prime_factorization(n: int, prime_list: "List[int]"):
    """
    n: 素因数分解したい数
    prime_list: sqrt(n)までの素数が格納されたリスト
    -------------------
    prime_count: 素因数の個数が入ったCounterオブジェクト
    """
    import collections
    prime_count = collections.Counter()
    
    for i in prime_list:
        if i * i > n:
            break
        while n % i == 0:
            n /= i
            prime_count[int(i)] += 1
    if n > 1:
        prime_count[int(n)] += 1
    
    return prime_count

def solve(A: int, B: int):
    g = fractions.gcd(A, B)
    prime_list = eratosthenes_sieve(math.ceil(math.sqrt(g)))
    prime_count = prime_factorization(g, prime_list)
    print(len(prime_count) + 1)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  
    B = int(next(tokens))  
    solve(A, B)

if __name__ == '__main__':
    main()

Solution (Python):


def greatest_common_divisor(N, M):
    assert N >= M
    while M != 0:
        N, M = M, N%M
    return N

def prime_divisor(N):
    temp = N
    for n in range(2, int(-(-N**0.5//1))+1):
        if temp % n == 0:
            while temp % n == 0:
                temp //= n
            yield n
    if temp != 1:
        yield temp
        

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

    if a > b:
        a, b = b, a

    gcd = greatest_common_divisor(b, a)
    pdiv = [pd for pd in prime_divisor(gcd)]
    print(len(pdiv)+1)

main()

Solution (Python):
import sys
import math


def main():
    a, b = [int(s) for s in sys.stdin.readline().strip().split()]

    def factorize(x):
        ret = set()
        for n in range(2, int(math.sqrt(x))+1):
            if x % n == 0:
                while x % n == 0:
                    x //= n
                ret.add(n)
        if x != 1:
            ret.add(x)
        return ret

    a_primes = factorize(a)
    b_primes = factorize(b)
    shared = a_primes.intersection(b_primes)
    print(len(shared) + 1)


main()

Solution (Python):
import sys
import math

def main():
    a, b = [int(s) for s in sys.stdin.readline().strip().split()]

    def factorize(x):
        ret = set()
        for n in range(2, int(math.sqrt(x))+2):
            if x % n == 0:
                while x % n == 0:
                    x //= n
                ret.add(n)
        if x != 1:
            ret.add(x)
        return ret

    a_primes = factorize(a)
    b_primes = factorize(b)
    shared = a_primes.intersection(b_primes)
    print(len(shared) + 1)


main()

Solution (Python):
A,B=map(int,input().split())
Pa={1}
Pb={1}
a=2
while(a*a<=A):
    if A%a==0:
        A=A//a
        Pa.add(a)
    else:
        a+=1
if A>1:
    Pa.add(A)
b=2
while(b*b<=B):
    if B%b==0:
        B=B//b
        Pb.add(b)
    else:
        b+=1
if B>1:
    Pb.add(B)
print(len(Pa&Pb))

Solution (Python):
import fractions

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

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

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

    return arr
    
A = list(map(int, input().split()))

B = fractions.gcd(A[0], A[1])

C = factorization(B)

if C[0][0] != 1:
    print(len(C) + 1)
else:
    print(1)

Solution (Python):

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


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

def main():
  a,b=map(int,input().split())
  print(len(prime_decomposition(gcd(a,b))))
  
main()

Solution (Python):


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

a,b=map(int,raw_input().split())
z=gcd(a,b)
s=set()
i=2
while i*i<=z:
 while z%i==0:
  s.add(i)
  z/=i
 i+=1
if z>1:
 s.add(z)
print len(s)+1

Solution (Python):
from math import sqrt


def solve(n):
    res = set()
    for i in range(2, int(sqrt(n))+1):
        while n % i == 0:
            res.add(i)
            n /= i
        if(n<=1): break
    if n>1:
        res.add(n)
    res.add(1)
    return res


A, B = [int(_) for _ in input().split()]
print(len(solve(A) & solve(B)))

Solution (Python):


from fractions import gcd

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

g=gcd(a,b)


def trial_div(n):
    from collections import Counter
    
    prime=Counter()

    for i in range(2,int(pow(n,0.5)+2)):
        while n%i==0:
            n//=i
            prime[i]+=1
    if n>1:prime[n]+=1
    
    return prime


res=trial_div(g)
print(1+len(res))

Solution (Python):
from fractions import gcd
a, b = map(int, input().split())
g = gcd(a, b)
ans = 1
for i in range(2, int(g ** 0.5) + 1):
    if g % i != 0:
        continue
    while g % i == 0:
        g //= i
    ans += 1
if g > 1:
    ans += 1
print(ans)

Solution (Python):
def primes_sieve(limit):
    a = [True] * limit
    a[0] = False

    for (i, is_prime) in enumerate(a):
      p = i+1
      if is_prime:
        yield p
        for n in range(p, limit, p):
          a[n-1] = False
                
def trial_division(n):
    if n < 2:
        return set()
    prime_factors = set()
    for p in primes_sieve(int(n**0.5)):
      if p*p > n: break
      while n % p == 0:
        prime_factors.add(p)
        n //= p
    if n > 1:
        prime_factors.add(n)
    return prime_factors

A, B = map(int, input().split())
Ap = trial_division(A)
ans = [i for i in Ap if B % i == 0]
print(len(ans)+1)

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

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

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
      
c = gcd(A, B)

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