Problem:


Score : 400 points

Problem Statement

Given are positive integers A and B.

Let us choose some number of positive common divisors of A and B.

Here, any two of the chosen divisors must be coprime.

At most, how many divisors can we choose?

Definition of common divisor

An integer d is said to be a common divisor of integers x and y when d divides both x and y.

Definition of being coprime

Integers x and y are said to be coprime when x and y have no positive common divisors other than 1.

Definition of dividing

An integer x is said to divide another integer y when there exists an integer \alpha such that y = \alpha x.

Constraints

All values in input are integers.

1 \leq A, B \leq 10^{12}

Input

Input is given from Standard Input in the following format:

A B

Output

Print the maximum number of divisors that can be chosen to satisfy the condition.

Sample Input 1

12 18

Sample Output 1

3

12 and 18 have the following positive common divisors: 1, 2, 3, and 6.

1 and 2 are coprime, 2 and 3 are coprime, and 3 and 1 are coprime, so we can choose 1, 2, and 3, which achieve the maximum result.

Sample Input 2

420 660

Sample Output 2

4

Sample Input 3

1 2019

Sample Output 3

1

1 and 2019 have no positive common divisors other than 1.



Sample input:
12 18


Sample output:
3

Submission status: Accepted

Solution code:
A,B=map(int,input().split())
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
def fa(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
if A ==1 or B == 1:
  print(1)
else:
  ans=fa(gcd(A,B))
  if ans == [1]:
    print(1)
  else:
    print(len(ans)+1)

Submission status: Accepted

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

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

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

def isPrime(n):
  if n < 2:
    return False
  if n == 2:
    return True
  for p in range(2, int(n**0.5)+1):
      if n % p == 0:
        return False
  return True

n = gcd(a,b)
lst = divisor(n)

ans = []
for x in lst:
    if isPrime(x):
        ans.append(x)
print(len(ans) + 1)

Submission status: Accepted

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


def factorization(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 = set(factorization(A))
b = set(factorization(B))


ans = 1
for aa in a:
    if aa in b:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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 table


a, b = list(map(int, input().split(' ')))
q = gcd(a,b)
t = prime_decomposition(q)

print(len(set(t))+1)

Submission status: Accepted

Solution code:
a,b=list(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])

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

    return arr

aa=factorization(a)
bb=factorization(b)

dicta={"1":1}
dictb={"1":1}
for i in range(len(aa)):
  if(str(aa[i][0]) not in dicta):
    dicta[str(aa[i][0])]=1
for i in range(len(bb)):
  if(str(bb[i][0]) not in dictb):
    dictb[str(bb[i][0])]=1
count=0
for i in dicta:
  if(i in dictb):
    count +=1

print(count)

Submission status: Accepted

Solution code:
import sys, math

def GCD(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0:
        a, b = b, a % b
    return b

def solve():
    A, B = map(int, input().split())
    is_prime = dict()
    is_prime[1] = True
    primes = {1}
    gcd = GCD(A, B)
    lim = int(math.sqrt(gcd))
    count = 1
    for i in range(2, lim + 1):
        if i not in is_prime:
            primes |= {i}
            is_prime[i] = True
            k = i * 2
            while k <= lim:
                is_prime[k] = False
                k += i

            if gcd % i == 0:
                count += 1
                while gcd % i == 0:
                    gcd //= i
    
    if gcd > 1: count += 1
    print(count)

            
        
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

a, b = na()

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

g = gcd(a, b)
ans = 1
for d in range(2,1000001):
    e = 0
    while g % d == 0:
        g //= d
        e += 1
    if e > 0:
        ans += 1
if g > 1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import math
from fractions import gcd

def readInts():
  return [int(s) for s in input().split(" ")]

def main():
  A, B = readInts()
  g = gcd(A, B)

  ds = set()
  for n in range(1, math.floor(math.sqrt(g)) + 1):
    if g % n == 0:
      ds.add(n)
      ds.add(g // n)

  ds = sorted(ds)
  c = 0
  bs = [True for _ in range(len(ds))]
  for (i, n) in enumerate(ds):
    if n == 1:
      c += 1
      continue
    if bs[i]:
      c += 1
      for j in range(i+1, len(ds)):
        if ds[j] % n == 0:
          bs[j] = False
  print(c)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from fractions import gcd

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

Submission status: Accepted

Solution code:
#  --*-coding:utf-8-*--

import math

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

    return n


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

    g2 = int(math.sqrt(g))
    cnt = 1

    if g%2 == 0:
        cnt += 1
        while g%2 == 0:
            g //= 2

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

    if g > 1:
        cnt += 1
            
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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 = set(prime_decomposition(A))
b = set(prime_decomposition(B))

print(len(a & b) + 1)

Submission status: Accepted

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

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

def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1

a_set = divisor(A)
b_set = divisor(B)
S = a_set & b_set
S = list(S)
ans = 0

for s in S:
    if is_prime(s):
        ans += 1

print(ans+1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())

from fractions import gcd
a = gcd(n,m)

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

t = factorization(a) 

if (n == 1) or (m == 1):
    print(1)
else:
    print(len(t)+1)

Submission status: Accepted

Solution code:
import fractions

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

GCD = fractions.gcd(A, B)

def pf(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(pf(GCD))) + 1)

Submission status: Accepted

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

def pdw(n):
    i=2
    t=[]
    ta = t.append
    while i*i<=n:
        while n%i==0:
            n//=i
            ta(i)
        i+=1
    if n>1:ta(n)
    return t
a,b = map(int,input().split())
g = gcd(a,b)
if g==1:
    print(1)
else:
    a = pdw(g)
    ans = set(a)
    print(len(ans)+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

def gcd(m, n):
    if m < n:
        return gcd(n, m)
    if m % n == 0:
        return n
    return gcd(n, m % n)


def primeFactorize(n):
    primes = set()
    d = 2
    while d*d <= n:
        while n % d == 0:
            primes.add(d)
            n = n // d
        d += 1
    if n > 1:
        primes.add(n)
    return primes


def solve(A, B):
    primes = primeFactorize(gcd(A, B))
    return len(primes) + 1


if __name__ == '__main__':

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

    ans = solve(A, B)

    print(ans)

Submission status: Accepted

Solution code:
import math
import fractions

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


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

aa = prime_factorize(a)
bb = prime_factorize(b)

#print(aa,bb)
a = set(aa)
b = set(bb)
a = a.intersection(b)

#print(a)

print(len(a)+1)

Submission status: Accepted

Solution code:
import collections

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

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

a, b = map(int, input().split())
n = gcd(a,b)
c = collections.Counter(prime_factorize(n))
print(len(c))

Submission status: Accepted

Solution code:
import fractions
A,B = list(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

x=fractions.gcd(A,B)
#print(x)

y = prime_factorize(x)
#print(y)

print(len(set(y))+1)

Submission status: Accepted

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


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


divA=divisor(A)
divB=divisor(B)

C=[]
for i in divA:
    if i in divB:
        C.append(i)

        
def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1

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

print(cnt+1)

Submission status: Accepted

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

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

g=gcd(a,b)
t=1
ans=0
while t**2<=g:  #10**6
  if g%t==0:
    k=1
    for i in range(2,round(t**0.5)+1):  #10**3
      if t%i==0:
        k=0
        break
    if k:
      ans+=1
    #print(t)
  l=g//t
  if l!=t and g%l==0:
    k=1
    for i in range(2,round(l**0.5)+1):
      if l%i==0:
        k=0
        break
    if k:
      ans+=1
    #print(l)
  t+=1
print(ans)

Submission status: Accepted

Solution code:
import fractions
import math

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

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(x):
    if x < 2: return False # 2未満に素数はない
    if x == 2 or x == 3 or x == 5: return True # 2,3,5は素数
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False # 2,3,5の倍数は合成数
    prime = 7
    step = 4
    while prime <= math.sqrt(x):
        if x % prime == 0: return False
        prime += step
        step = 6 - step
    return True

def solve():
    gcd = fractions.gcd(A, B)
    divisors = make_divisors(gcd)
    l = [x for x in divisors if is_prime(x)]
    print(len(l)+1)

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

print(len(C)+1)

Submission status: Accepted

Solution code:
import fractions

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

    divisors.sort()
    return divisors

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

gcd = fractions.gcd(A,B)
divs = make_divisors(gcd)

#print(divs)

ans=[]

for d in divs:
    
    is_so=True
    for i in range(1,len(ans)):
        if d % ans[i] == 0:
            is_so = False
#    print(str(d)+','+str(is_so))
    if is_so:
        ans.append(d)

print(len(ans))

Submission status: Accepted

Solution code:
def fact(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())
print(len( (set(fact(A))|set([1])) & (set(fact(B))|set([1])) ))

Submission status: Accepted

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


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

    divisors.sort()
    return divisors


a = (set(make_divisors(A)))
b = (set(make_divisors(B)))
tmp = list(a & b)


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


ans = sum([is_prime(i) for i in tmp])
print(ans)

Submission status: Accepted

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

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

    return arr

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

prime_factors_A = [x[0] for x in factorization(A)]
prime_factors_B = [x[0] for x in factorization(B)]
prime_factors_A.append(1)
prime_factors_B.append(1)
ans = 0
for x in prime_factors_A:
    ans += 1 if x in prime_factors_B else 0
print(ans)

Submission status: Accepted

Solution code:
a,b = map(int,input().split())
def lcm(a, b):
    return a * b // gcd (a, b)
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
def prime_factor(n):
    ass = [1]
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass
s = 0


l = prime_factor(gcd(a,b))


print(len(set(l)))

Submission status: Accepted

Solution code:
def gcd(a,b):
    if a < b:
        a, b = b, a
    while b >= 1:
        a, b = b, a % b
    return a

def shave(n):
    n_root = int(n**0.5)
    candidate = [i for i in range(3,n+1,2)]
    for i in range(3,n_root+2,2):
        candidate = [ j for j in candidate if j == i or j % i != 0]   
    candidate = [2] + candidate
    return candidate

x, y = [ int(v) for v in input().split() ]

gcd1 = gcd(x, y)
prime_list = shave(int(gcd1**0.5)+1)

ans = 1
for i in prime_list:
    if gcd1 % i == 0:
        ans += 1
        while gcd1 % i == 0:
            gcd1 //= i
if gcd1 != 1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
A, B = map(int, input().split())
prA = [1]
count = 1
i = 2
while i*i <= A:
  while A%i == 0:
    A//=i
    prA.append(i)
  i += 1
if A>1:
  prA.append(A)
#prA = prime_decomposition(A)
#prB = prime_decomposition(B)
prA = set(prA)
prB = [1]
i = 2
flag = 0
while i*i <= B:
  while B%i == 0:
    B//=i
    if i in prA and flag == 0:
      count += 1
      prB.append(i)
      flag = 1
  i += 1
  flag = 0
if B>1:
  prB.append(B)
  if B in prA:
    count += 1

print(count)

Submission status: Accepted

Solution code:
import fractions
import math


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


a, b = map(int, input().split())
res = 1
n = fractions.gcd(a, b)


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


ln = make_divisors(n)
for i in ln:
    if is_prime(i):
        res += 1

print(res)

Submission status: Accepted

Solution code:
import collections
def gcd(m,n):
    if min(m,n) == 0:
        return(max(m,n))
    else:
        return(gcd(min(m,n),max(m,n)%min(m,n)))
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
a,b = list(map(int,input().split()))
c = gcd(a,b)
d = collections.Counter(prime_factorize(c))
print(len(d)+1)

Submission status: Accepted

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

def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return 0
    return n

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

    divisors.sort()
    return divisors
C = make_divisors(fractions.gcd(A, B))


#print(C)
#print(is_prime(5))
#print(is_prime(10))

print(len(C) - C.count(0) )

Submission status: Accepted

Solution code:
a,b = map(int,input().split())
if(a==1 and b==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
    fa = factorization(a)
    fb = factorization(b)
    fa = [i[0] for i in fa]
    fb = [i[0] for i in fb]
    c = fa+fb
    print(len(c)-len(set(c))+1)

Submission status: Accepted

Solution code:
x, y = map(int,input().split())
#li = list(map(int, input().split()))

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

print(len(set(pr(x)) & set(pr(y)))+1)

Submission status: Accepted

Solution code:
import sys


input = sys.stdin.readline


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

    c = []
    n = 1
    m = min(A, B)
    k = max(A, B)
    while n*n <= m:
        if m % n == 0:
            if k % n == 0:
                c.append(n)
            if k % (m//n) == 0 and n*n != m:
                c.append(m//n)
        n += 1
    c.sort()
    ary = []
    for i in range(1, len(c)):
        for n in ary:
            if c[i] % n == 0:
                break
        else:
            ary.append(c[i])
    # print(c, ary)
    print(len(ary)+1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np
import math


# noinspection PyShadowingBuiltinsInspection

def yakusu_map(x):
    max_n = math.sqrt(x)
    ret = {}
    if x % 2 == 0:
        ret[2] = 0
        # ret.append(2)
        while x % 2 == 0:
            x //= 2
            ret[2] += 1
    mod = 3
    while mod <= max_n and mod <= x:
        if x % mod == 0:
            ret[mod] = 0
            # ret.append(mod)
            while x % mod == 0:
                x //= mod
                ret[mod] += 1
        mod += 2
    if x != 1:
        ret[x] = 1
    return ret

def main():
    a, b = [int(x) for x in input().split()]
    print(len(set(yakusu_map(a).keys()) &
          set(yakusu_map(b).keys())) + 1)
    # print(yakusu_map(b))
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def make_divisors(a, b):
    n = min(a, b)
    m = max(a, b)
    import math
    divisors = []
    for i in range(2, int(math.sqrt(n)) + 1):
        if n == 1:
            break
        if n % i == 0: #割り切れるとき
            if m % i == 0:
                divisors.append(i)
            while n % i == 0 and n != 1:
                n //= i
    if n != 1 and m % n == 0:
        divisors.append(n)
    return divisors

lst = make_divisors(A, B) #この中から素数を数えたらいい
print (len(lst) + 1)

Submission status: Accepted

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

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

r=list(set(divisor(a)) & set(divisor(b)))

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

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

def fctr1(n): 
    f=[]
    c=0
    r=int(n**0.5)
    for i in range(2,r+2):
        while n%i==0:
            c+=1
            n=n//i
        if c!=0:
            f.append([i,c])
            c=0
    if n!=1:
        f.append([n,1])
    return f

a, b = map(int, input().split(" "))
g = gcd(a, b)

fct = fctr1(g)
#print(g, fct)

out = len(fct) + 1
print(out)

Submission status: Accepted

Solution code:
def gcd(a,b):
  while b!=0:a,b=b,a%b
  return a
def lcm(a,b):return a*b//gcd(a,b)

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

import random
def is_prime(n):
  if n == 2: return True
  if n == 1 or n & 1 == 0: return False
  d = (n - 1) >> 1
  while d & 1 == 0:
    d >>= 1
  for k in range(100):
    a = random.randint(1, n - 1)
    t = d
    y = pow(a, t, n)
    while t != n - 1 and y != 1 and y != n - 1:
      y = (y * y) % n
      t <<= 1
    if y != n - 1 and t & 1 == 0: return False
  return True

A,B=map(int,input().split())
l=sorted(ds(gcd(A,B)))
n=0
for i in l:
  if is_prime(i)==True:n+=1
print(n+1)

Submission status: Accepted

Solution code:
import math
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 False

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

    return True
a, b = map(int, input().split())
x = make_divisors(a)
y = make_divisors(b)
z = set(x) & set(y)
cnt = 1
for i in z:
    if is_prime(i):
        cnt = cnt + 1
print(cnt)

Submission status: Accepted

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

a,b=map(int,input().split())
while a!=b:
    if a>b:
        a-=b
    else:
        b-=a
    if a==b:
        break
def prime_factorize(s):
    l = []
    while s % 2 == 0:
        l.append(2)
        s //= 2
    f = 3
    while f * f <= s:
        if s % f == 0:
            l.append(f)
            s //= f
        else:
            f += 2
    if s != 1:
        l.append(s)
    return l
m=prime_factorize(a)
m=set(m)
print(len(m)+1)
#print(m)

Submission status: Accepted

Solution code:
def gcd(a,b):
	while b!=0:
		a,b=b,a%b
	return a
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())
fac = factorization(gcd(A,B))
if fac[0][0] == 1:
  print(1)
else: print(len(fac)+1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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

# 1の時には[]が返される
A_fact_set = set(prime_factorize(A))
A_fact_set.add(1)
B_fact_set = set(prime_factorize(B))
B_fact_set.add(1)

ans_set = A_fact_set & B_fact_set
print(len(ans_set))

Submission status: Accepted

Solution code:
import sys
import os
sys.setrecursionlimit(100000)

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

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

A, B = map(int,input().split())
P = factorize(gcd(A,B))
P = set(P)

print(len(P)+1)

Submission status: Accepted

Solution code:
from fractions import gcd

def prime_factors(n):
  i = 2
  factors = []
  while i * i <= n:
    if n % i:
      i += 1
    else:
      n //= i
      factors.append(i)
  if n > 1:
    factors.append(n)
  return factors

A,B = map(int,input().split())
G = gcd(A,B)
#print(G)
plist = prime_factors(G)
ans = 1
prep = 1
for p in plist:
  if p != prep:
    ans += 1
    prep = p
print(ans)

Submission status: Accepted

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

def factorize(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 gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a

D = gcd(A,B)
factors = factorize(D)
if factors[0][0]==1:
    print(1)
else:
    print(len(factors)+1)

Submission status: Accepted

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

c = fractions.gcd(a, b)
f = factorization(c)

print(len(f)+1 if c > 1 else 1)

Submission status: Accepted

Solution code:
from fractions import gcd
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 check_disjoint(i, div_list):
  flag = True
  for d in div_list:
    if gcd(i, d)!=1:
      flag = False
      break
  if flag:
    div_list.append(i)
  return div_list
      

a, b = map(int, input().split())
s = make_divisors(gcd(a, b))
if len(s) == 1:
  print(1)
else:
  div_list = [s[1]]
  inputs = s[2:]
  for i in inputs:
    div_list = check_disjoint(i, div_list)
  print(len(div_list)+1)

Submission status: Accepted

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

inputs = input().split()
a = int(inputs[0])
b = int(inputs[1])

af = factorize(a)
bf = factorize(b)

afbf = set(af) & set(bf)

print(len(afbf)+1)

Submission status: Accepted

Solution code:
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
  
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
  
def main():
  A,B=map(int,input().split())
  C=gcd(A,B)
  t=prime_factorize(C)
  print(len(set(t))+1)
  
main()

Submission status: Accepted

Solution code:
a,b = map(int,input().split())
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
ls = (make_divisors(a))
ls2 = (make_divisors(b))
ls3 = (set(ls)&set(ls2))


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

ans = 0
if 1 in ls3:
    ans += 1
for i in ls3:
    if is_prime(i) == True:
        ans += 1
        
print(ans)