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: Wrong Answer

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

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

k = []
no = 1
large = max(a,b)
small = min(a,b)
while no * no <= small:
	if no % 2 == 0 and no != 2:
		no += 1
		continue
	if small % no == 0 and large % no == 0:
		k.append(no)
		if small // no != no:
			k.append(small//no)
	no += 1
k.sort()

l = []
l.append(k[0])
ans = 1

for i in range(1,len(k)):
	flag = True
	for j in range(len(l)):
		if gcd(k[i],l[j]) != 1:
			flag = False
			break
	if flag:
		l.append(k[i])
		ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
def cd(x, y):
    ret = [1]
    for i in range(2, min(x, y)+1):
        if x % i == 0 and y % i == 0:
            ret.append(i)
    return ret


def main():
    a, b = map(int, input().split())
    ab_cds = cd(a, b)
    count = 0
    temp_list = []
    for i, x in enumerate(ab_cds):
        for y in ab_cds[min(i+1,len(ab_cds)-1) : ]:
            xy_cds = cd(x, y)
            if len(xy_cds) == 1:
                count += 1
                temp_list.append((x,y))
    # print(ab_cds)
    # print(temp_list)
    print(count)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from fractions import gcd
def f(n):
    tmp = n
    cnt = 0
    for i in range(2,int(n**0.5) + 2):
        if tmp < i:
            break
        if tmp % i == 0:
            cnt += 1
            while tmp % i == 0:
                tmp //= i
    if cnt == 0 and tmp != 1:
        cnt += 1
    return cnt

A, B = map(int, input().split())
g = gcd(A, B)
ans = f(g) + 1
print(ans)

Submission status: Wrong Answer

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

ans = 1

n = 2

while n <= int(max(a, b)**0.5):
    if a%n == 0 and b%n == 0:
        while a%n == 0:
            a = a//n
        while b%n == 0:
            b = b//n
        ans += 1
    
    n += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import fractions as fra
a,b=map(int,input().split())
c=fra.gcd(a,b)
d=[[i,1] for i in range(0,1000000)]
e=[]
t=0
for i in range(2,1000000):
    if(d[i][1]==1):
        e.append(i)
        t=i
        while(t<1000000):
            d[t][1]=0
            t+=i
        t=0
cnt=0
for i in range(len(e)):
    if(c%e[i]==0):
        cnt+=1
print('{0}'.format(cnt+1))

Submission status: Wrong Answer

Solution code:
import sys


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

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

    def divisors(n):
        ans = []
        val = n
        for i in range(2, n):
            if val % i == 0:
                val = val // i
                ans.append(i)
        return ans

    gcd_val = gcd(a, b)
    divs = divisors(gcd_val)
    ans = 1

    for div in sorted(divs):
        if div == 1:
            continue
        if gcd_val % div == 0:
            ans += 1
            while gcd_val % div == 0 and gcd_val > 1:
                gcd_val = gcd_val // div
    print(ans)


main()

Submission status: Wrong Answer

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

def soinsu(n):
  c = []
  t = n
  m = int(-((-n**0.5)//1))+5
  for i in range(2, m):
    if t%i==0:
      while t%i==0:
        t //= i
      c.append(i)
  if c==[]:
    c.append(n)
  return c

count = 1
a = soinsu(A)
b = soinsu(B)
for j in a:
  for k in b:
    if j == k:
      count += 1
      
print(count)

Submission status: Wrong Answer

Solution code:
A, B = [int(v) for v in input().split()]

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

s1 = factorization(A)
s2 = factorization(B)
s3 = s1 & s2
print(len(s3))

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, deque
from functools import reduce
import math

input = sys.stdin.readline


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 main():
    A, B = map(int, input().split())
    k = []
    if min(A, B) == 1:
        print(1)
    else:
        prime_list = make_divisors(min(A, B))

        for p in prime_list:
            if A % p == 0 and B % p == 0:
                for i in k:
                    if i != 1 and p % i == 0:
                        break
                else:
                    k.append(p)
        print(len(k))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#%%

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

#%%

from fractions import gcd


#%%
n = gcd(18, 12)

#%%

vv = set([i for i in range(1, int(n // 2) + 1) if n % i == 0])

def get_prime_and_1_list(N):
    l = [i for i in range(2, N + 1)]
    p = [1]
    while l[0] <= int(N ** 0.5):
        p.append(l[0])
        t = l[0]
        l = [i for i in l if i % t != 0]

    p.extend(l)
    
    return p

p = set(get_prime_and_1_list(n))

print(len(vv & p))

Submission status: Wrong Answer

Solution code:
a,b=map(int,input().split())
c=[]
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
d=gcd(a,b)
x=0
for i in range(int(d**0.5)):
    e=0
    if i==0:
        c.append(1)
        x+=1
        continue
    if d%(i+1)==0:
        for j in range(len(c)):
            if (i+1)%c[j]!=0:
                e+=1
            elif c[j]!=1:
                break
        if e==len(c)-1:
            c.append(i+1)
            x+=1
            y=d//i+1
            for j in range(len(c)):
                if y%c[j]!=0:
                    e+=1
                elif c[j]!=1:
                    break
            if e==len(c)-1:
                c.append(i+1)
                x+=1
f=0
for i in range(len(c)):
    if d%c[i]!=0:
        f+=1
    elif c[i]!=1:
        break
if f==len(c)-1:
    x+=1
if d==1:
    print(1)
else:
    print(x)

Submission status: Wrong Answer

Solution code:
import fractions as m

a, b = map(int, input().split())
# a = 10**12
# b = 10**12

lcd = []
cd = m.gcd(a, b)

t1 = a
t2 = b
cd1 = cd
cd2 = cd

if a == b:
    for i in range(1, int(a**0.5)+1):
        if a % i == 0:
            lcd.append(i)
            if i != a // i:
                lcd.append(a//i)
    lcd.sort()
elif cd > 1:
    lcd.append(cd)
    while True:
        m1 = t1 % cd1
        m2 = t2 % cd2
        if m1 > 0 and m2 > 0:
            break
        if m1 == 0:
            c = t1 // cd1
            lcd.append(c)
            t1 = c
        if m2 == 0:
            c = t2 // cd2
            lcd.append(c)
            t2 = c

    lcd = list(set(lcd))
    lcd.append(1)
    lcd.sort()
else:
    lcd.append(cd)

ans = 0
lns = len(lcd)
i = 0
while i < lns:
    j = i + 1
    while j < lns:
        if m.gcd(lcd[i], lcd[j]) > 1:
            lcd.pop(j)
            lns = len(lcd)
        j += 1
    lns = len(lcd)
    i += 1

print(len(lcd))

Submission status: Wrong Answer

Solution code:
a_b = input().split(" ")
A = int(a_b[0])
B = int(a_b[1])

p_nums = []
range_max = int(min([A, B])**0.5)
if (min([A, B])**0.5).is_integer() is False:
    range_max += 1
for i in range(1, range_max):
    is_p_num = True
    if A % i == 0 and B % i == 0:
        for p in p_nums:
            if p == 1:
                continue
            if i % p == 0:
                is_p_num = False
                break
        if is_p_num:
            p_nums.append(i)

print(len(p_nums))

Submission status: Wrong Answer

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

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

out_A = calc_divi(A)
out_B = calc_divi(B)

tmp = list(set(out_A) & set(out_B))
tmp = sorted(tmp, reverse=True)

out = 0
for i in range(len(tmp)):
  jdg = 0
  for k in range(len(tmp)):
    if tmp[i] > tmp[k]:
      if tmp[k] != 1:
        if tmp[i]%tmp[k] == 0:
          break
  if jdg == 0:
    out = out + 1
          
print(out)

Submission status: Wrong Answer

Solution code:
import fractions

A, B = list(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

l = list(set(make_divisors(A)) & set(make_divisors(B)))
i = 0
while i < len(l):
    v = l[i]
    if v == 1:
        i += 1
        continue
    l = l[0:i+1] + list(filter(lambda x: x % v != 0, l[i+1:]))
    i += 1
print(len(l))

Submission status: Wrong Answer

Solution code:
import fractions
# fractions.gcd(x,y)
def prime_t(t):
    i=2
    while i**2<=t:
        if t%i==0:
            return 0
        i+=1
    return 1

def chkl(tt):
    p_t=set()
    for i in range(2,tt+1):
        if prime_t(i):
            p_t.add(i)
    return p_t

def div(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)

    # divisors.sort()
    return divisors
a,b=map(int,input().split())
x=div(a)
y=div(b)
z=x&y
t=len(z)
chk=chkl(t)
#print(z&chk)
ans=len(z&chk)+1
print(ans)

Submission status: Wrong Answer

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

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,b = map(int,input().split())	
lis_ab = cf(a,b)
print(len(lis_ab)+1)

Submission status: Wrong Answer

Solution code:
A,B=map(int,input().split())
if A>B:
  s=B
elif A==B:
  s=A
else:
  s=A
x=[]
for i in range(1,s+1):
  if A%i==0 and B%i==0:
    x.append(i)
def f(m):
  s=[]
  for k in range(1,m+1):
    if m%k==0:
      s.append(k)
  return s
g=0    
for j in range(len(x)-1):
  if x[j] in f(x[j+1]):
    g+=1
print(g)

Submission status: Wrong Answer

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

def common_divisors(a, b):
    cd = []
    n = min(a, b)
    m = max(a, b)
    for i in range(1, int(n**0.5)+1):
        if n % i == 0 and m % i == 0:
            cd.append(i)
            if i != n // i and m % (n//i) == 0:
                cd.append(n//i)
    return cd

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

def sieve(n):
    prime = []
    is_prime = [True]*(n+1)
    is_prime[0] = False
    is_prime[1] = False

    for i in range(2, n+1):
        if is_prime[i]:
            prime.append(i)
            for j in range(2*i, n+1, i):
                is_prime[j] = False
    return prime


cd = common_divisors(A, B)
#prime = sieve(max(cd))

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

#print(cd)
#print(max(cd))
#print(prime)

ans = 1 # 1は絶対入る
for a in cd:
    if is_prime(a):
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
A, B = [int(s) for s in input().split()]
def gcd(x, y):
  while y != 0:
    x, y = y, x%y
  return x
def divisors(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
gcd_divisors = divisors(gcd(A, B))
N = len(gcd_divisors)
count = 0
for i in range(N):
  flg = False
  for j in range(N-1-i-i):
    if gcd(gcd_divisors[N-1-i], gcd_divisors[j]) != 1:
      flg = True
  if flg == False:
    count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import math
A,B = map(int,input().split())
N = max(A,B)
prime = []

tA = A
tB = B
# print(math.ceil(N**0.5))
for i in range(2, math.ceil(N**0.5)+1):
    if tA%i==0 and tB%i==0:
        while tA%i==0:
            tA //= i
        while tB%i==0:
            tB //= i
        prime.append(i)

if tA!=1 and tA == tB:
    prime.append(tA)


# print(prime)
print(len(prime)+1)

Submission status: Wrong Answer

Solution code:
def fatora(n):
	ans = []
	for i in range(1, n+1):
		if i*i > n:
			break
		else:
			if n % i == 0:
				ans.append(i)
				ans.append(n//i)
	return set(ans)

def eh_primo(n):
	if n == 0:
		return False
	elif n == 1:
		return True
	elif n == 2:
		return True
	else:
		for i in range(2, n+10):
			if i*i > n:
				break
			else:
				if n % i == 0:
					return False
		return True



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

Submission status: Wrong Answer

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

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

g = gcd(A,B)
g_ = g

count = 0
l = []
i = 2
while i**2 <= g_:
    j = g_/i if g_%i == 0 else 0
    while g%i == 0:
        g = g/i
        l.append(i)
    if j > 0:
        while g%j == 0:
            g = g/j
            l.append(j)
    l = list(set(l))
    i = i+1

print(1+len(l))

Submission status: Wrong Answer

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

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

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

    if not arr:
        arr.add(n)

    return arr


fa = factorization(a)
fb = factorization(b)
res = 1

for n in fa:
    if n in fb:
        res += 1
print(res)

Submission status: Wrong Answer

Solution code:
def resolve():
    a, b = map(int, input().split())
    ps = primes(int(min(a, b) ** 0.5))
    ans = [pi for pi in ps if a % pi == 0 and b % pi == 0]
    print(len(ans) + 1)


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]]


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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

    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
 
a, b = map(int,input().split())
 
c = 1
m = min(a,b)
for i in range(1,int(m**0.5)+1):
	if a % i == 0 and b % i == 0:
		if is_prime(i):
			c+=1
		if i != a//i and i != b//i:
			if a % (m//i) == 0 and b % (m//i) == 0:
				if is_prime(m//i):
					c+=1		
		
print(c)

Submission status: Wrong Answer

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

count = 0
for i in range(1, min(A, B)+1):
    if i > min(A, B):
        break
    elif A % i == B % i == 0:
        count += 1
        A /= i
        B /= i

print(count)

Submission status: Wrong Answer

Solution code:
a_b = input().split(" ")
A = int(a_b[0])
B = int(a_b[1])

p_nums = []
range_max = int(min([A, B])**0.5)
if (range_max ** 0.5).is_integer() is False:
    range_max += 1
for i in range(1, range_max):
    is_p_num = True
    if A % i == 0 and B % i == 0:
        for p in p_nums:
            if p == 1:
                continue
            if i % p == 0:
                is_p_num = False
                break
        if is_p_num:
            p_nums.append(i)

print(len(p_nums))

Submission status: Wrong Answer

Solution code:
#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
A, B = map(int, input().split())


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]]


Ps = primes(1000001)
Plen = len(Ps)
Is = [0] * Plen
for i, p in enumerate(Ps):
    while A % p == 0 and B % p == 0:
        A = A // p
        B = B // p
        Is[i] += 1
    if A < p or B < p:
        break
ans = 1
if A > 1000001 and B > 1000001:
    if A % B == 0 or B % A == 0:
        ans += 1
for _ in range(Plen):
    if Is[_] != 0:
        ans += 1
print(str(ans))

Submission status: Wrong Answer

Solution code:
A, B = map(int,input().split())
com_A = []
com_B = []
for i in range(1, int(A/2)+1):
  if A%i==0:
    com_A.append(i)
 
for i in range(1, int(B/2)+1):
  if B%i==0:
    com_B.append(i)
 
set_AB = set(com_A) & set(com_B)
 
import math
 
def isPrimeNumber(n):
  if n == 2:
    return True
  if n < 2 or n&1 == 0:
    return False
  return pow(2, n-1, n) == 1

count = sum([1 for i in set_AB if isPrimeNumber(i)])
print(count)

Submission status: Wrong Answer

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

n=10**6
is_prime=[True]*(n+1)
is_prime[0],is_prime[1]=False,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
prime=[i for i in range(n+1) if is_prime[i]]

min_n=min(a,b)
count=1
for i in prime:
    if i>(min_n+1)//2:break
    elif a%i==0 and b%i==0:
        count +=1
print(count)

Submission status: Wrong Answer

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

c=[]

def gcd(x, y,count,v):
    while y > 0:
      l=x//y
      x, y = y, x%y
      if l not in v:
        count+=l
        v.append(l)
    return count

k=gcd(a,b,0,c)

if a == 1 or b == 1:
  print(1)
else:
  print(k)

Submission status: Wrong Answer

Solution code:
def euc(x,y):
  while x != y:
    if x > y:
      x -= y
    if x < y:
      y -= x
  return x

A,B = list(map(int, input().split()))
k = euc(A,B)
r = 1
s = 0
w = 1
while r**2 <= k:
  r += 1
  if k % r == 0:
    s += 1
    while k % r == 0:
      k /= r
    if k == 1:
      w = 0
s += w 
print(s)

Submission status: Wrong Answer

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

l = []
for i in range(n):
    if a % (i+2) == 0 and b % (i +2) == 0:
        l.append(i+2)

primes = [2]
for x in l:
    if all(x % prime !=0 for prime in primes):
        primes.append(x)
    
print(len(primes)+1)

Submission status: Wrong Answer

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

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
#print(factorization(n))
if factorization(n)==[1,1]:
  print(1)
else:
  print(len(factorization(n))+1)

Submission status: Wrong Answer

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

ans = 1

n = 2

while n <= int(max(a, b)**0.5):
    if a%n == 0 and b%n == 0:
        a = a//n
        b = b//n
        ans += 1
    
    n += 1
print(ans)

Submission status: Wrong Answer

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

import math

def tn(n):
  m=n
  factor=[]
  tmp=int(math.sqrt(n))+1
  for num in range(2,tmp):
    t=0
    while n%num==0:
      n//=num
      if t==0:
        factor.append(num)
        t=1
  if factor==[]:
    factor.append(m)
  factor.append(1)
  return factor

listA=tn(A)
listB=tn(B)
anslist=set(listA) & set(listB)
ans=len(anslist)
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	A,B = inputMap()
	an = min(A,B)

	if an == 1:
		print(1)

	if an >= 285311670611:
		print(7)
	elif an >= 823543:
		print(6)
	elif an >= 3125:
		print(5)
	elif an >= 27:
		print(4)
	elif an >= 4:
		print(3)
	else:
		print(2)


def getPrimeNumList(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]]

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import sys


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

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

    def divisors(n):
        ans = []
        val = n
        for i in range(2, n):
            if val % i == 0:
                val = val // i
                ans.append(i)
            if i > val // 2:
                break
        return ans

    gcd_val = gcd(a, b)
    divs = divisors(gcd_val)
    # ans = 1
    # for div in sorted(divs):
    #     if div == 1:
    #         continue
    #     if gcd_val % div == 0:
    #         ans += 1
    #         while gcd_val % div == 0 and gcd_val > 1:
    #             gcd_val = gcd_val // div
    # print(ans)


main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, deque
from functools import reduce
import math

input = sys.stdin.readline


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

    # divisors.sort()
    return divisors


def main():
    A, B = map(int, input().split())
    k = []
    if min(A, B) == 1:
        print(1)
    else:
        prime_list = make_divisors(min(A, B))

        for p in prime_list:
            if A % p == 0 and B % p == 0:
                for i in k:
                    if i != 1 and p % i == 0:
                        break
                else:
                    k.append(p)
        print(len(k))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
num_line=input().rstrip().split(" ")
numA=int(num_line[0])
numB=int(num_line[1])

if(numA>=numB):
    NumMin=numB
else:
    NumMin=numA

lst_p=[]
import math

def trial_division(target):
    dest = int(math.sqrt(target))
 
    for j in range(2,dest+1):
        if target % j == 0:
            return
    lst_p.append(target)

for i in range(2,NumMin):
    trial_division(i)

#print(lst_p)
lst2_p=[]
lst2_p.append(1)
  
for i in range(len(lst_p)):
    tst=lst_p[i]
    print(tst)
    lst2_p.append(tst)
    if numA%tst!=0:
        lst2_p.remove(tst)
    
    elif numB%tst!=0:
        lst2_p.remove(tst)


print(len(lst2_p))

Submission status: Wrong Answer

Solution code:
A, B = [int(v) for v in input().split(' ')]

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

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

cf_array = cf(A, B)

count = 0
for i in range(0, len(cf_array)):
    v1 = cf_array[i]
    for j in range(i + 1, len(cf_array)):
        v2 = cf_array[j]
        if gcd(v1, v2) == 1:
            count += 1
            
       
print(count)

Submission status: Wrong Answer

Solution code:
a, b = map(int, input().split())
g = []
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b, a%b)
g.append(gcd(a,b))
g.append(1)
j = 1
for i in range(2,g[0]):
    if not a%i and not b%i:
        c = True
        for k in range(1, len(g)):
            if gcd(g[k],i)!=1:
                c = False
                break
        if c:
            g.append(i)
print(len(g)-1)

Submission status: Wrong Answer

Solution code:
import math

def prime_enemerate(A):
    a=[i for i in range(5,A+1) if i%2!=0 and i%3!=0]
    a_judge=[i for i in range(5,int(math.sqrt(A))+1) if i%2!=0 and i%3!=0]

    while len(a_judge)!=0:
        a0=a_judge[0]
        a=[i for i in a if i%a0!=0 or i==a0]
        a_judge=[i for i in a_judge if i%a0!=0]

    return [2,3]+a

A,B=map(int,input().split())
judge_max=int(math.sqrt(max(A,B)))
prime=prime_enemerate(judge_max)
result=0

for i in prime:
    if A%i==0 and B%i==0:
        result+=1

print(result+1)

Submission status: Wrong Answer

Solution code:
import fractions

primes = [2]


def is_prime(n):
    for p in primes:
        if p * p > n:
            break
        if n % p == 0:
            return False

    return True


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

G = fractions.gcd(A, B)

res = 1

if G % 2 == 0:
    res += 1
    G /= 2

for i in range(3, int(G ** 0.5) + 1, 1):
    if not is_prime(i):
        continue
    primes.append(i)
    if G % i == 0:
        res += 1
        G /= i

if G > 1 and is_prime(G) and G not in primes:
    res += 1

print(res)

Submission status: Wrong Answer

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

n=10**6
is_prime=[True]*(n+1)
is_prime[0],is_prime[1]=False,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
prime=[i for i in range(n+1) if is_prime[i]]

min_n=min(a,b)
count=1
for i in prime:
    if i>min_n//2:break
    elif a%i==0 and b%i==0:
        count +=1
print(count)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	A,B = inputMap()
	an = min(A,B)

	if an >= 285311670611:
		print(7)
	elif an >= 823543:
		print(6)
	elif an >= 3125:
		print(5)
	elif an >= 27:
		print(4)
	elif an >= 4:
		print(3)
	else:
		print(2)


def getPrimeNumList(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]]

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

temp = fractions.gcd(a, b)

c = []
for i in range(1, temp):
    if a%i==0 and b%i==0:
        c.append(i)
c = set(c)

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]]

d = set(primes(temp))

ans = c&d
        
print(len(ans)+1)

Submission status: Wrong Answer

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

C=[1]
for i in range(2,min(A,B)+1):
    if A % i == 0 and B % i == 0:
        C.append(i)
#print(C)

#for i in itertools.combinations(C, 2):
#    print(i)

NG=[]
ans=0

for i in itertools.combinations(C, 2):
    a,b=i
    if a in NG:
        continue
    if b in NG:
        continue

    z=fractions.gcd(a,b)
    #print(a,b)
    #print(z)
    
    if z == 0:
        NG.append(max(a,b))

print(len(C)-len(NG))

Submission status: Wrong Answer

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

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
#print(factorization(n))
if len(factorization(n))==1:
  print(1)
else:
  print(len(factorization(n))+1)

Submission status: Wrong Answer

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

    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
 
a, b = map(int,input().split())
 
c = 1
m = min(a,b)
for i in range(1,int(m**0.5)+1):
	if a % i == 0 and b % i == 0:
		if is_prime(i):
			c+=1
		if i != m//i:
			if a % (m//i) == 0 and b % (m//i) == 0:
				if is_prime(m//i):
					c+=1		
		
print(c)