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: Time Limit Exceeded

Solution code:
from sys import stdin
import fractions

A, B = [int(x) for x in stdin.readline().rstrip().split()]
gcd = fractions.gcd(A, B)

x = 2
ans = 1
g = 1

while gcd > 1:
    if gcd % x == 0:
        gcd //= x
        if g != x:
            ans += 1
        g = x
    else:
        x += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import math

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

kosuu = 1  # 1

if saidai % 2 == 0:
    kosuu += 1

while saidai % 2 == 0:
    saidai = saidai // 2

for i in range(3, 100000000000000000000, 2):
    if saidai <= 1:
        break

    if saidai % i == 0:
        kosuu += 1

    while saidai % i == 0:
        saidai = saidai // i

print(kosuu)

Submission status: Time Limit Exceeded

Solution code:
# import math


def trial_division(n):
    # 素因数を格納するリスト
    factor = set()
    # 2から√n以下の数字で割っていく
    # tmp = int(math.sqrt(n)) + 1
    for num in range(2, n+1):
        while n % num == 0:
            n //= num
            factor.add(num)
    # リストが空ならそれは素数
    if not factor:
        return set((1, n))
    else:
        factor.add(n)
        return factor


A, B = map(int, input().split())
# print(trial_division(A))
# print(trial_division(B))
print(len(trial_division(A) & trial_division(B)))

Submission status: Time Limit Exceeded

Solution code:
a, b = map(int, input().split())
cnt = 1
i = 2
c, d = a, b

while d > 0:
    c, d = d, c % d

while c > 1:
    if c % i == 0:
        cnt += 1
        
        while c % i == 0:
            c //= i

    i += 1

print(cnt)

Submission status: Time Limit Exceeded

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

def f(n):
    li = []
    while True:
        for i in range(2, n+1):
            if n % i == 0:
                n = n // i
                li.append(i)
                break
            else:
                continue
        else:
            break
    return li

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

Submission status: Time Limit Exceeded

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

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

ret = 0
x = gcd(A, B)
if x % 2 == 0 :
    ret += 1
    while x % 2 == 0 :
        x //= 2
        
i = 3
while x != 1 :
    flg = False
    while x % i == 0 :
        x //= i
        flg = True
        
    if flg :
        ret += 1
    i += 2
        
print(ret + 1)

Submission status: Time Limit Exceeded

Solution code:
n=list(map(int,input().split()))
n.sort()
ans=1
for i in range(n[0]-1):
    #print(n[0])
    if n[0]%(i+2)==0 and n[1]%(i+2)==0:
        #print(i+2)
        ans+=1
        n[0]=n[0]//(i+2)
print(ans)

Submission status: Time Limit Exceeded

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

tmpA = max(a, b)
tmpB = min(a, b)

while tmpB != 0:
    newB = tmpA % tmpB
    tmpA = tmpB
    tmpB = newB

already = [1]
tmp = tmpA

while True:
    if tmp == 1:
        break
    
    for i in range(2, tmp):
        if tmp % i == 0:
            already.append(i)
            tmp = tmp // i
            break
    else:
        already.append(tmp)
        break

print(len(set(already)))

Submission status: Time Limit Exceeded

Solution code:
import math

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

def decompose(n):
	result = []
	
	i = 2
	while i <= n:
		if n % i == 0:
			result.append(i)
			n //= i
		else:
			i += 1
	return result

def calc_gcm(a, b):
	if a > b:
		r = a % b
		a = r
	
	while a > 0:
		r = b % a
		b = a
		a = r
	
	return b

primes = decompose(calc_gcm(A, B))
count = 1
prev = 0
for p in primes:
	if prev != p:
		count += 1
	prev = p
print(count)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())


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

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return table


l = gcd(n, m)

a = sieve(l)

ans = 0
for i in a:
    if (n % i == 0 and m % i == 0):
        ans += 1

print(ans + 1)

Submission status: Time Limit Exceeded

Solution code:
"""
see https://qiita.com/daikw/items/f48d6ac374255763463d
"""

import math
import random


seed_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]


class MillerRabin:
    """
    see https://qiita.com/srtk86/items/609737d50c9ef5f5dc59
    """

    def __init__(self, witnesses=None):
        if witnesses is None:
            self.witnesses = MillerRabin._witnesses
        else:
            self.witnesses = witnesses

    @staticmethod
    def _witnesses(num):
        def _get_range():
            if num < 2047:
                return 1
            if num < 1373653:
                return 2
            if num < 25326001:
                return 3
            if num < 3215031751:
                return 4
            if num < 2152302898747:
                return 5
            if num < 3474749660383:
                return 6
            if num < 341550071728321:
                return 7
            if num < 3825123056546413051:
                return 9
            return 12
        return seed_primes[:_get_range()]

    @staticmethod
    def _random_witnesses(num):
        return [random.randint(1, num - 1) for _ in range(100)]

    def is_prime(self, n):
        d = n - 1
        while d & 1 == 0:
            d >>= 1

        witnesses = self.witnesses(n)
        for w in witnesses:
            y = pow(w, d, n)

            while d != n - 1 and y != 1 and y != n - 1:
                y = (y * y) % n
                d <<= 1

            if y != n - 1 and d & 1 == 0:
                return False

        return True


class BruteForce:
    @staticmethod
    def is_prime(n):
        for k in range(2, int(math.sqrt(n)) + 1):
            if n % k == 0:
                return False
        return True


miller_rabin = MillerRabin()


def is_prime(n):
    """
    see https://qiita.com/gushwell/items/ff9ed83ba55350aaa369
    """
    if n == 1:
        return False
    if n in seed_primes:
        return True
    if any(map(lambda x: n % x == 0, seed_primes)):
        return False

    if n < 2000000:
        return BruteForce.is_prime(n)
    else:
        return miller_rabin.is_prime(n)


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


class PollardsRho:
    def find_factor(self, n, seed=1):
        """
        see
        https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
        https://qiita.com/gushwell/items/561afde2e00bf3380c98
        """
        def f(x):
            p = seed_primes[seed % len(seed_primes)]
            return (p * x + seed) % n

        if is_prime(n):
            return n

        x, y, d = 2, 2, 1
        count = 0
        while d == 1:
            count += 1
            x = f(x)
            y = f(f(y))
            d = gcd(abs(x - y), n)

        if d == n:
            return self.find_factor(n, seed + 1)
        return self.find_factor(d)

    def factorize(self, n):
        primes = {}
        if is_prime(n):
            return {n: 1}

        while n > 1:
            factor = self.find_factor(n)
            primes.setdefault(factor, 0)
            primes[factor] += 1
            n //= factor

        return primes


class Fermat:
    @staticmethod
    def is_prime(n):
        if n == 1:
            return False
        if n == 2:
            return True

        for k in range(100):
            a = random.randint(2, n - 1)

            if math.gcd(n, a) != 1:
                return False

            if pow(a, n - 1, n) != 1:
                return False

        return True


import fractions

a, b = list(map(int, input().split()))
x = fractions.gcd(a, b)

dic = PollardsRho().factorize(x)
print(len(dic) + 1)

Submission status: Time Limit Exceeded

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

def cf(A,B):
    cf=[]
    for i in range(2,min(A,B)+1):
        if A % i == 0 and B % i == 0:
            cf.append(i)
    return cf


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

print(sum([is_prime(one) for one in cf(A,B)])+1)

Submission status: Time Limit Exceeded

Solution code:
A,B = map(int,input().split())
def cf(x1,x2):
  cf=[]
  for i in range(2,min(x1,x2)+1):
    if x1 % i == 0 and x2 % i == 0:
      cf.append(i)
  return cf

cf_list = cf(A,B)
p = []
for num in cf_list:
  for n in range(2,num):
    if num%n == 0:
      break
  else:
    p.append(num)
print(len(p)+1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

plis = seachPrimeNum(max(2,min(A,B)))

ans = 1
for p in plis:
    if A%p +B%p ==0:
        ans += 1
        A = A//p
        B = B//p
        if min(A,B) == 1:
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ABC141d
import sys
import heapq
import math
import fractions
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

a, b = map(int, input().split())
cd = []
for i in range(1, fractions.gcd(a, b) + 1):
    if (a % i != 0 or b % i != 0):
        continue
    flag = True
    for j in cd:
        if (j == 1):
            continue
        if (i % j == 0):
            flag = False
            break
    if (flag):
        cd.append(i)
print(len(cd))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, deque
from heapq import *
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# L = [list(input().strip())  for _ in range(N)]
# S = input().strip()

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

g = gcd(N, M)

pp = []
for i in range(2, g + 1):
    if g % i == 0:
        pp.append(i)

ans = pp.copy()
for i in range(len(pp)):
    t = pp[i]
    ans = [v for v in ans if v % t != 0 or v == t]

print(len(ans) + 1)

Submission status: Time Limit Exceeded

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

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

def make_primeset(N):
  if N == 2:
    return {2}
  else:
    result = {2}
    for i in range(3,N+1):
      flag = True
      for p in result:
        if i % p == 0:
          flag = False
          break
      if flag:
        result.add(i)
    return result

gcd_ = gcd(A,B)
if gcd_ == 1:
  print(1)
else:
  ans = 1  # 1のぶん
   # 素因数の種類数+1
  for p in make_primeset(gcd_):
    if gcd_ % p == 0:
      ans += 1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
A, B = list(map(int, input().split()))
if B>A: A,B = B,A
while B>0:
    A,B = B,A%B

p=2
ans=1
while p*2<=A:
    c=0
    while A%p==0:
        A//=p
        c+=1
    if c>0: ans+=1
    p+=1
if A>1: ans+=1

print(ans)

Submission status: Time Limit Exceeded

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

if a > b:
    c = b
    d = a
else:
    c = a
    d = b

i = 2
ans = 1 
incre = True
while True:
    while a % i == 0 and b % i == 0:
        a //= i
        b //= i
        if incre:
            ans += 1
            incre = False
    incre = True
    i += 1
    if i > c:
        break


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

def cf(x1,x2):
    cf=[]
    for i in range(1,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

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

    C = cf(A,B)

    cnt = 1
    for c in C:
        if is_prime(c):
            cnt += 1

    print(cnt)

main()

Submission status: Time Limit Exceeded

Solution code:
n=[int(i) for i in input().split()]
ans=[]
prime = [0 for i in range(min(n[0],n[1])+ 1)]
ans.append(1)
p = 2
while (p * p <= min(n[0],n[1])):

    # If prime[p] is not changed, then it is a prime
    if (prime[p] == 0):
        if n[0] % p == 0 and n[1] %p == 0:
            ans.append(p)
        # Update all multiples of p
        for i in range(p * p, min(n[0],n[1]) + 1, p):
            prime[i] = 1
    p += 1
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import math
def e(n):
  prime = []
  limit = math.sqrt(n)
  data = [i + 1 for i in range(1, n)]
  while True:
    p = data[0]
    if limit <= p:
      return prime + data
    prime.append(p)
    data = [e for e in data if e % p != 0]
a,b = map(int,input().split())
c = min(a,b)
if c == 1:
  print(1)
  exit()
ec = e(c)
count = 1
for x in ec:
  if a%x == 0 and b%x == 0:
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

# 約数の全列挙
def 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(reverse=True)  # ソート
    return divisors

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

    divA = divisors(A)
    comDiv = []

    for a in divA:
        if B % a == 0:
            comDiv.append(a)

    comDiv.sort()
    isIndep = [True] * len(comDiv)
    maxDiv = comDiv[-1]
    divToIndex = {d : i for i, d in enumerate(comDiv)}
    ans = 1

    for i, div in enumerate(comDiv[1:], start=1):
        if isIndep[i]:
            ans += 1
            mul = 2
            while div * mul <= maxDiv:
                if div * mul in divToIndex:
                    isIndep[divToIndex[div * mul]] = False
                mul += 1

    print(ans)

sol()

Submission status: Time Limit Exceeded

Solution code:
# ABC141d
import sys
import heapq
import math
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

a, b = map(int, input().split())
cd = []
for i in range(1, min(a, b) + 1):
    if (a % i != 0 or b % i != 0):
        continue
    flag = True
    for j in cd:
        if (j == 1):
            continue
        if (i % j == 0):
            flag = False
            break
    if (flag):
        cd.append(i)
print(len(cd))

Submission status: Time Limit Exceeded

Solution code:
import fractions
A, B = map(int, input().split())
GCD = fractions.gcd(A, B)
k = 1
cnt = 1
while GCD > 1:
  k += 1
  if GCD % k:
    continue
  cnt += 1
  while GCD % k == 0:
    GCD //= k
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n=[int(i) for i in input().split()]
ans=[]
prime = [0 for i in range(min(n[0],n[1])+ 1)]
p = 2
while (p * p <= min(n[0],n[1])):

    # If prime[p] is not changed, then it is a prime
    if (prime[p] == 0):

        # Update all multiples of p
        for i in range(p * p, min(n[0],n[1]) + 1, p):
            prime[i] = 1
    p += 1
for i in range(1,min(n[0],n[1])+1):
    if n[0]%i==0 and n[1]%i==0 and prime[i]==0:
        ans.append(i)
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
def gcd(n,m):
    while n:
        m,n = [n,m%n]
    return m

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

S = gcd(A,B)

s = 1
i = 2
while S != 1:
    hoge = 0
    while S % i == 0:
        hoge += 1
        S //= i
    if hoge:
        s += 1
    i += 1

print(s)

Submission status: Time Limit Exceeded

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


def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf


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


for i in cf(A, B):
    ans += is_prime(i)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(n,m):
    while n:
        m,n = [n,m%n]
    return m

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

S = gcd(A,B)

s = {1}
i = 2
while S != 1:
    while S % i == 0:
        S //= i
        s |= {i}
    i += 1

print(len(s))

Submission status: Time Limit Exceeded

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

while a!=0 and b!=0:
    a,b = max(a,b),min(a,b)
    a %= b

ans = 1
for i in range(2, b+1):
    t = 0
    while b % i == 0:
        b //= i
        # print(b)
        t = 1
        if b==1:
            break
    ans += t
    if b==1:
        break
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math


def read():
    return int(input())

def readmap():
    return map(int, input().split())

def readlist():
    return list(map(int, input().split()))

def cf(x1,x2):
    cf=[]
    for i in range(1,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

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

if __name__ == "__main__":
    a, b = readmap()

    lst = cf(a, b)

    ans = sum([is_prime(e) for e in lst]) + 1

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
A, B = map(int, input().split())
a = set()
b = set()
i = 2
while i <= 10 ** 9:
  if A <= 1:
    break
  while A % i == 0:
    a.add(i)
    A //= i
  i += 1
i = 2
while i <= 10 ** 9:
  if B <= 1:
    break
  while B % i == 0:
    b.add(i)
    B //= i
  i += 1
inter = a.intersection(b)
print(len(inter) + 1)

Submission status: Time Limit Exceeded

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

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

ret = 0
i = 2
x = gcd(A, B)
while x != 1 :
    flg = False
    while x % i == 0 :
        x //= i
        flg = True
        
    if flg :
        ret += 1
    i += 1
        
print(ret + 1)

Submission status: Time Limit Exceeded

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

counter = 0
primes = [2, 3]

for n in range(5, min(a,b), 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)

ans = 1
for i in primes:
    if a%i == 0 and b%i == 0:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(x,y):
    if x==y:
        return x
    elif x>y:
        r=-1
        while r!=0:
            r=x%y
            x=y
            y=r
        return x
    else:
        r=-1
        while r!=0:
            r=y%x
            y=x
            x=r
        return y

def sosu(n):
    pn=[2]
    for i in range(3,n+1):
        chk=True
        for j in pn:
            if i%j==0:
                chk=False
        if chk:
            pn.append(i)
    return pn


a,b=map(int,input().split())
x=gcd(a,b)
l=sosu(x)
ans=1
for m in l:
    if x%m==0:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

isPrime = [True for i in range(max(A, B)+1)]
isPrime[0] = False
isPrime[1] = False

for i in range(2, max(A, B) + 1):
    if isPrime[i]:
        for j in range(2*i, max(A, B)+1, i):
            isPrime[j] = False


print(sum(p for i, p in enumerate(isPrime) if i>0 and A%i==0 and B%i==0) + 1)

Submission status: Time Limit Exceeded

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

ret = 0
i = 2
while A >= i and B >= i :
    flg = False
    while A % i == 0 and B % i == 0 :
        A //= i
        B //= i
        flg = True
        
    if flg :
        ret += 1
    i += 1
        
print(ret + 1)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

d = gcd(A, B)
ans = 1
k = 2
while d > 2:
    plus = 0
    while d % k == 0:
        d //= k
        plus = 1
    ans += plus
    k += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase
from typing import List
from math import gcd


def get_divisors(n: int) -> List[int]:
    i = 1
    ret = []
    while i * i <= n:
        if n % i == 0:
            ret.append(i)
            x = n // i
            if x != i:
                ret.append(x)
        i += 1
    return ret



def main() -> None:
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a

    divisors = list(filter(lambda x: b % x == 0, get_divisors(a)))
    divisors.sort()
    # print(divisors)
    ret = []

    for div in divisors:
        ok = True
        for i in ret:
            if gcd(i, div) != 1:
                ok = False
                break
        if ok:
            ret.append(div)

    print(len(ret))


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self, **kwargs):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import sqrt
from math import ceil
def prime_factorization(n):
    pfs = [1]
    i = 2
    for i in range(2, int(ceil(sqrt(n)))):
        while n % i == 0:
            pfs.append(i)
            n //= i
    if n > 0:
        pfs.append(n)
    return pfs


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


def bit_search(pfs):
    m = len(pfs)
    ds = set([])
    for i in range(1 << m):
        d = 1
        for j in range(m):
            if i & (1 << m) > 0:
                d *= pfs[m]
        ds.add(d)
    return ds

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

gcdab = gcd(a, b)
#print (gcdab)
pfsab = prime_factorization(gcdab)
#print (pfsab)
pfsabset =set(pfsab)
print (len(pfsabset))

Submission status: Accepted

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

#N以下の素数れっきょエラトステネス
def prime(N):
    lsprime = [0,0]+[1 for i in range(N-1)]
    lsprime2 = []
    for i in range(N+1):
        if lsprime[i] == 0:
            continue
        lsprime2.append(i)
        k = i
        while i <= N:
            lsprime[i] = 0
            i += k
    return lsprime2

#素因数分解
def prime2(N):
    arr = []
    temp = N
    setprime = set()
    for i in range(2, int(-(-N**0.5//1))+1):
        if temp%i==0:
            cnt=0
            setprime.add(i)
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
        setprime.add(temp)

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

    return arr,setprime

_,setp = prime2(C)
print(len(setp)+1)

Submission status: Accepted

Solution code:
from math import gcd
a, b = map(int, input().split())

gcd = gcd(a, b)
ans = 1
n = int(gcd**0.5) + 2
for i in range(2, n):
    if gcd%i == 0:
        ans += 1
        while gcd%i == 0:
            gcd //= i
    if gcd < i:
        break
if gcd >= n:
    ans += 1
if ans == 1 and gcd != 1:
    ans = 2
    
print(ans)

Submission status: Accepted

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

def prime_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

setA=set(prime_factorization(A))
setB=set(prime_factorization(B))
setAB=setA &setB
if setAB=={1}:
    print(1)
else:
    print(len(setAB)+1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import gcd
a, b = map(int, input().split())

def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n //i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

v = gcd(a,b) # greatest common divisors
divs = make_divisors(v)

k = 1
ans = 0
for d in divs:
    test = gcd(k, d)
    if test == 1:
        ans += 1
        k *= d
print(ans)

Submission status: Accepted

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


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


a = prime_numbers(A)
b = prime_numbers(B)
#print(a, b)
#print(a.intersection(b))
ans = len(a.intersection(b))
print(ans)

Submission status: Accepted

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest
import collections

def yn(b):
    print("Yes" if b==1 else "No")
    return

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 resolve():
    readline=sys.stdin.readline
    a,b=map(int, readline().rstrip().split())

    af = factorization(a)
    bf = factorization(b)

    c = collections.Counter()
    c[1]=2
    for x in af:
        c[x[0]]+=1
    for x in bf:
        c[x[0]]+=1
    ans=0
    for k in c.keys():
        if c[k]>=2:
            ans+=1
    print(ans)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Accepted

Solution code:

import math

# 試し割法により素因数分解
# https://note.nkmk.me/python-prime-factorization/
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,input().split())
    G = math.gcd(A, B)
    primes = prime_factorize(G)
    print(1 + len(set(primes)))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
ab = [int(i) for i in input().split()]
ab = math.gcd(ab[0], ab[1])
dic = {}
n = 2
while n**2 <= ab:
  if ab % n:
    n += 1
  else:
    ab //= n
    dic[n] = dic.get(n,0) + 1
if 1 < ab:
  dic[ab] = dic.get(ab,0) + 1

print(len(dic) + 1)

Submission status: Accepted

Solution code:
import math

def factorization(n):
    d = [1]
    i = 2
    while True:
        if i > int(math.sqrt(n)):
            break
        if n % i == 0:
            d.append(i)
            n //= i
        else:
            i += 1
    if n != 1:
        d.append(n)
    return d


def main():
    A, B = map(int, input().split())
    fa = set(factorization(A))
    fb = set(factorization(B))
    print(len(fa & fb))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import gcd,sqrt,floor
a,b = map(int,input().split())
c = gcd(a,b)
x = []
for i in range(1,floor(sqrt(c))+1):
    if c % i == 0:
        x.append(i)
        x.append(c//i)
x.sort()
y = []
i = 1
while c > 1 and i < len(x):
    if c % x[i] == 0:
        y.append(x[i])
        c = c // x[i]
    else:
        i += 1
print(len(set(y))+1)