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

from math import sqrt, ceil

def main():

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

    divs = [1]
    for i in range(2, ceil(sqrt(max(a, b)))):
        if (a/i).is_integer() and (b/i).is_integer():
            divs.append(i)
            while (a/i).is_integer() and (b/i).is_integer():
                a = a/i; b = b/i
    print(len(divs))

main()

Submission status: Wrong Answer

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

so = [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 89, 97, 101, 103, 107, 109, 113, 127, 131]
count = 0

for i in so:
    if A < i:
        break
    if A % i == 0 and B % i == 0:
        count += 1
print(count)

Submission status: Wrong Answer

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

primes = 0

i = 1

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

    i = 2
    while i*i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

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

ceiling = gcd_recursive(a,b)

while i <= ceiling:
    if a%i == 0 and b%i == 0:
        if is_prime(i):
           primes += 1
    i += 2

if ceiling < 2:
    print(primes - 1)
else:
    print(primes + 1)

Submission status: Wrong Answer

Solution code:
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())
C=max(A,B)
lis=make_divisors(min(A,B))
lis.sort()
l=len(lis)
ans=[1]
if l>1:
    j=lis[1]
    for i in range(l):
            if C%lis[i]==0 and pow(j,lis[i]-1,lis[i])==1:
                ans.append(lis[i])
    ans.append(j)
    print(len(ans))
else:
    print(1)

Submission status: Wrong Answer

Solution code:
import math

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

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

	return gcd(b, a%b)


G = gcd(A,B)


def sosuhantei(n):
	d = math.floor(n**(1/2))
	cond = True
	for i in range(2,d+1):
		if n % i == 0:
			cond = False
			break
	return cond 


sosu = []
g = math.floor(G**(1/2)) 

yaku = []

for i in range(2,g+1):
	if G % i == 0:
		yaku.append(i)
		yaku.append(G//i)

yaku = list(set(yaku))

cnt = 0
for i in range(len(yaku)):
	if sosuhantei(yaku[i]):
		cnt += 1

print(cnt + 1)

Submission status: Wrong Answer

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

def soinsu(n):
  c = []
  t = n
  for i in range(2, n):
    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:
from math import ceil,sqrt
a,b= list(map(int,input().split()))
#

def GBD(a,b):
    if a < b:
        a,b = b,a

    while b > 0:
        r = a % b
        a = b
        b = r
    return a

c = GBD(a,b)
l = [1]
d = 2
flag = 1
while c > d:
    while  c%d == 0:
        if flag == 1:
            l.append(d)
            flag = 0
        c = c//d

    d += 1
    flag = 1
l.append(int(c))
print(len(l))

Submission status: Wrong Answer

Solution code:
inp = input().split()
a = int(inp[0])
b = int(inp[1])

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

  return divisors

def gcd(a, b):
  while b != 0:
    a, b = b, a % b
  return a
  
a_div = make_divisors(a)
b_div = make_divisors(b)

common_div = list(set(a_div) & set(b_div))
common_div.sort()

out = []
for i in range(len(common_div)):
  for j in range(len(common_div)):
    if j == i:
      continue
    if gcd(common_div[i], common_div[j]) != 1:
      #out.append(max(common_div[i], common_div[j]))
      out.append(common_div[j])
      break

d = set(common_div).difference(set(out))
print(len(d))

Submission status: Wrong Answer

Solution code:
import math

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

def cf(x1,x2):
    cf=[]
    for i in range(3,x1+1,2):
        if  is_prime(i):
            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

num = cf(a,b)
num_2 = [1,2]
num_2.extend(num)
print(len(num_2))

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
	if a==0:
		return(b)
	return(gcd(b%a,a))
a,b=map(int,input().split())
g=gcd(a,b)
divide=2
ans=1
if g%divide==0:
	ans+=1
	while(g%divide==0):
		g//=divide
for divide in range(3,int(g**(1/2))+2,2):
	if g%divide==0:
		ans+=1
		while(g%divide==0):
			g//=divide
	divide+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import math

D = input().split(' ')
A = int(D[0])
B = int(D[1])

if A < B:
    max = int(B / 2) + 1
else:
    max = int(A / 2) + 1

d = []

for i in range(1, max):
    if A % i == 0 and B % i == 0:
        flg = 1
        for j in d:
            if i % j == 0 and j != 1:
                flg = 0
                break

        if flg == 1:
            d.append(i)

        if len(d) == 0:
            d.append(1)

print(len(d))

Submission status: Wrong Answer

Solution code:
import itertools
import math 

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

def divisor(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(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1

if is_prime(a) and is_prime(b):
    print(1)
    import sys
    sys.exit()

a_L = divisor(a)
b_L = divisor(b)

kouyaku = set(a_L) & set(b_L)

new_L = []


for val in kouyaku:
    if is_prime(val):
        new_L.append(val)


new_L.append(1)
#counter =0

#v = itertools.combinations(list(new_L),2)


#for i in v:

#    if math.gcd(i[0], i[1]) == 1:
        #print(i[0],i[1])
#        counter +=1
#print(counter)

print(len(new_L))

Submission status: Wrong Answer

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

minAB = min(A,B);

#hurui = [True] * (minAB+1)
"""
upper = int(math.sqrt(minAB+1))
ans = 1

for i in range(2, upper+1):

    if not(hurui[i]):
        continue
    
    for j in range(2*i, minAB+1, i):
        hurui[j] = False

    if A % i == 0  and B % i == 0:
        ans += 1
"""
ans = 1
print(ans)

Submission status: Wrong Answer

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

gcd_AB = gcd(A, B)
cd = []
for i in range(2, int(math.sqrt(gcd_AB)) + 2):
    if A % i == 0 and B % i == 0:
        cd.append(i)

count = 1
for i in range(len(cd)):
    if is_prime(cd[i]) == True:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import math

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


A,B=map(int,input().split())
#numには入力値の大きいほうの数字が入る
num = (min(A,B))

# print("hai",is_prime(4))

primeNum=[]
j=result=0
for i in range(2,num):
    flag=False
    if is_prime(i)==True:
      print(i)
      while A % i == 0 and B % i == 0:
        A = A // i
        B = B // i
        flag=True
      j+=1
      if flag==True:
        result+=1
      if min(A,B)<i:
        break

print(result+1)

Submission status: Wrong Answer

Solution code:
def divisor(n):
    i = 1
    table = []
    while i * i <= n:
        if n % i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
    
a,b = map(int,input().split())

aset = set(divisor(a))
bset = set(divisor(b))

cset = aset & bset
clist = list(cset)
if len(clist) == 1:
    print(1)
    exit()

coprime = [1]
coprime.append(clist[1])

#print(clist)

for j in range(2,len(clist)):
    for k in range(1,len(coprime)):
        if clist[j] % coprime[k] == 0:
            break
    else:
        coprime.append(clist[j])

#print(coprime)
print(len(coprime))

Submission status: Wrong Answer

Solution code:
import itertools
from fractions import gcd

a, b = 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:
            if cf:
                flg = True
                if i > 2 and i % 2 == 0:
                    break
                for l in cf:
                    if gcd(l, i) != 1:
                        flg = False
                        break
                if flg:
                    cf.append(i)
            else:
                cf.append(i)
    return cf


print(len(cf(a, b)))

Submission status: Wrong Answer

Solution code:

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

C = gcd(A,B)
E = make_divisors(C)
F = E[-1]
memo = [False] * (F+1)
ans = 0
for e in E:
    if not(memo[e]):
        ans += 1
        j = e
        if e == 1:continue
        while j < len(memo):
            memo[j] = True
            j += e

print(ans)

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)//2)+1
count=1
for i in prime:
    if min_n<i:break
    elif a%i==0 and b%i==0:
        count +=1
print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np
def so(n):
    for i in range(3, int(np.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True
A, B = map(int, input().split())
M = np.min([A, B])
n = 1
if (A % 2 == 0) and (B % 2 == 0):
    n = 2
for i in range(3, int(np.sqrt(M)) + 1, 2):
    if so(i):
        if (A % i == 0) and (B % i == 0):
            n = n + 1
print(n)

Submission status: Wrong Answer

Solution code:
import math 

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

def sieve_of_eratosthenes(n): 
    candidate = [i for i in range(2, n+1)] 
    prime = []
    limit = math.sqrt(n) + 1 

    while True:
        p = min(candidate) 
        if limit <= p:
            prime.extend(candidate) 
            break
        prime.append(p) 

        candidate = [i for i in candidate if i % p != 0]

    return prime

def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n % i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    
    return list(set(table))
  
ma = max(A, B)
mi = min(A, B)

yakusu = [d for d in divisor(mi) if ma % d == 0]

yakumax = max(yakusu)
if yakumax == 1:
	prime = [1]
elif yakumax == 2:
  prime = [1, 2]
else:
  prime = sieve_of_eratosthenes(500)
  prime.append(1)

c = 0
for y in yakusu:
  if y in prime:
    c += 1

if len(yakusu) <= 1:
  print(0)
else:
  print (c)

Submission status: Wrong Answer

Solution code:
import math
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<2:
        return False
    elif n == 2:
        return True
    elif n%2 == 0:
        return False
    
    for i in range(3, n + 1, 2):
        if n%(i*i) == 0:
            return False
    return True


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

lis_ab = cf(a,b)
for i in lis_ab:
    if is_prime(i):
        cnt = cnt+1
print(cnt)

Submission status: Wrong Answer

Solution code:
import math

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

# 試し割り法(2以外の偶数は捨てる方法を追加)
def check_prime(n):
    flag = True

    # n:evenかつ2でないならば素数でない
    # n=1は素数でない,n=0も実装しやすいように入れておく
    if (n % 2 == 0 and n != 2) or n == 0 or n == 1:
        flag = False
        return(flag)

    # n:oddまたは2のときは考える
    else:
        # 2からrootnまでに約数は存在しうる
        for i in range(2, math.floor(math.sqrt(n))+1):
            if n % i == 0:
                flag = False
                break
        return(flag)

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

    # divisors.sort()
    return divisors

div = make_divisors(min(A, B))

cnt = 1
for n in div:
    if B % n == 0:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

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

ans_list =[]

for i in range(1, min(a, b)+1):
  
  if a%i==0 and b%i==0:
    ans_list.append(i)
    a //= i
    b //= i
    if a in ans_list or b in ans_list:
      break

print(len(ans_list))

Submission status: Wrong Answer

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

so = [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 89, 97,1101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 197, 199, 211, 223, 227, 229, 233, 239, 241]
a = []

for i in so:
    if A < i:
        break
    if A % i == 0 and B % i == 0:
        a.append(i)
print(a)
print(len(a))

Submission status: Wrong Answer

Solution code:
import math


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

def dv(x1, x2):
    ret = []
    v = int(math.sqrt(min(x1, x2))) + 1

    check = [0] * (v + 1)

    for n in range(2, v):
        if check[n] == 1:
            continue

        if x1 % n == 0 and x2 % n == 0:
            ret.append(n)

            cnt = 1
            while n * cnt <= v:
                check[n * cnt] = 1
                cnt += 1

    return ret


cf = [1] + dv(A, B)
print(len(cf))

Submission status: Wrong Answer

Solution code:
A,B =map(int,input().split())
if A<B:
    A,B =B,A
foo = 1
while foo != 0:
    A,B = B, A%B
    #print(A,B)
    foo = B

foo =A

plis=[2];A=10**4
for L in range(3,A):
    chk=True
    for L2 in plis:
        if L%L2 == 0:chk=False
    if chk==True:plis.append(L)

ans = 1
for p in plis:
    if  foo % p ==0:
        ans += 1
        foo = foo//p
    while foo % p == 0:
        foo = foo//p

if foo==1:
    print(ans)
elif int(foo**0.5)**2 ==foo:
    print(ans+1)
else:
    print(ans+2)

Submission status: Wrong Answer

Solution code:
import fractions
import math
a,b = [int(i) for i in input().split()]

gcd = fractions.gcd(a,b)

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
l = [i for i in range(2, int(math.ceil(gcd**0.5) +1)) if gcd % i == 0]

print(len([i for i in l if is_prime(i)]) +1)

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
	if a==0:
		return(b)
	return(gcd(b%a,a))
a,b=map(int,input().split())
g=gcd(a,b)
divide=2
ans=1
if g%divide==0:
	ans+=1
	while(g%divide==0 and g!=0):
		g//=divide
for divide in range(3,int(g**(1/2))+1,2):
	if g%divide==0:
		ans+=1
		while(g%divide==0 and g!=0):
			g//=divide
	divide+=1
print(ans)

Submission status: Wrong Answer

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

n = 2

while n <= int(max(A, B)**0.5+1):
    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:
#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 gcd(a, b):
    while b:
        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 = input().split()
 
A = int(A)
B = int(B)

#cf_list = cf(A, B)

#so_list = [1]
#for i in cf_list:
#  count = 0
#  for so in so_list:
#    
#    if cf(i, so) == []:
#      count +=1
#  if count == len(so_list):
#    so_list.append(i)
gcd_num =gcd(A,B)

gcd_list = factorization(gcd_num)

t = len(gcd_list)
if t == 1:
  print(t)
else:
  print(t+1)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline
A, B = map(int, input().split())


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

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

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

    return arr


af = factorization(A)
bf = factorization(B)
print(af)
print(bf)
ans = 1
for afi in af:
    if afi in bf:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

    return divisors


def only_prime(s):
    result = []
    for i in s:
        if not result:
            result.append(i)
        else:
            flag = True
            for j in result:
                if i % j == 0:
                    flag = False
                    break
            if flag:
                result.append(i)
    return result


a, b = list(map(int, input().split()))
cfa = make_divisors(a)
cfb = make_divisors(b)
cf_set = only_prime(sorted(cfa & cfb))

print(len(cf_set) + 1)

Submission status: Wrong Answer

Solution code:
inp = input().split()
a = int(inp[0])
b = int(inp[1])

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

  return divisors

def gcd(a, b):
  while b != 0:
    a, b = b, a % b
  return a
  
a_div = make_divisors(a)
b_div = make_divisors(b)

common_div = list(set(a_div) & set(b_div))

out = []
for i in range(len(common_div)):
  for j in range(len(common_div)):
    if j == i:
      continue
    if gcd(common_div[i], common_div[j]) != 1:
      out.append(max(common_div[i], common_div[j]))
      break

d = set(common_div).difference(set(out))
print(len(d))

Submission status: Wrong Answer

Solution code:
import math

D = input().split(' ')
A = int(D[0])
B = int(D[1])

if A < B:
    max = int(B / 2) + 1
else:
    max = int(A / 2) + 1

d = []

for i in range(1, max):
    if A % i == 0 and B % i == 0:
        flg = 1
        for j in d:
            if i % j == 0 and j != 1:
                flg = 0

        if flg == 1:
            d.append(i)

        if len(d) == 0:
            d.append(1)

print(len(d))

Submission status: Wrong Answer

Solution code:
import math

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

def func(n):
    num=1
    for i in range(2,int(math.sqrt(n) + 1e-9) +3):
        if n%i==0 and n!=i:
            num=0
            break
        else:
            continue
    return num

p=min(A,B)
q=max(A,B)

ans=0
check=[]
for i in range(1, int(math.sqrt(p)+ 1e-9)+3):
    if p%i==0:
        check.append(i)
        check.append(p/i)

for i in check:
    if q%i==0:
        ans+=func(i)

print(ans)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np

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

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

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

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[-1][0]

N=gcd(A,B)

if N==1:
    print(1)
else:
    ms = factorization(N)
    pl = seachPrimeNum(ms)
#    print(N,ms,pl)
    print(len(pl))

Submission status: Wrong Answer

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

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)
k=gcd(a,b)
if k==1:
  print(1)

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(reverse=True)
    return divisors
m=make_divisors(k)
x=len(m)
n=len(m)



for _ in range(n-1):
  for i in range(1,len(m)):
    if gcd(m[i],m[0])!=1:
      x-=1
      m.pop(0)
      break
    if i+1 == len(m):
      m.pop(0)
      break
print(x)

Submission status: Wrong Answer

Solution code:
import sys
import math

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


def InputToInt():
    A = input().split()
    for i in range(len(A)):
        A[i] = int(A[i])
    return A

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


if __name__ == '__main__':
    A, B = InputToInt()
    G = gcd(A, B)
    p = primes(int(math.sqrt(G)))

    c = 1
    if G == 1:
        print('1')
        sys.exit()
    
    for P in p:
        if G < P:
            break

        dc = 0
        while G%P == 0:
            G = G//P
            dc = 1
        c += dc
    print(c)

Submission status: Wrong Answer

Solution code:
import fractions

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

lst = []
for i in range(1,int(min(A, B)**0.5+1)):
    if A % i == 0 and B % i == 0:
        lst.append(i)

if len(lst) == 1:
    print(1)
else:
    check = [lst[1]]
    for i in range(1, len(lst)):
        for c in check:
            if lst[i] % c == 0:
                break
        else:
            check.append(lst[i])
    print(len(check)+1)

Submission status: Wrong Answer

Solution code:
import math
import random
import sys
#from sympy import isprime
# 整数xが素数かどうかを判定する
 
'''
def is_prime(n):
    if n < 2:
        return False
    else:
        for i in range(2, n):
            if i * i > n:
                break
            elif n % i == 0:
                return False
        return True
'''
def is_prime(n, k=50):
    assert n > 0
    if n == 2:
        return True
    elif n == 1 or n%2 == 0:
        return False
    d = n-1
    s = 0
    while d%2 == 0:
        d //= 2
        s +=1
    for i in range(k):
        a = random.randint(1, n-1)
        if pow(a, d, n) != 1:
            for r in range(0,s):
                if pow(a, d*2**r, n) == n-1:
                    break
                else:
                    return False
    return True

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

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

if a < b:
    A = a
    B = b
else:
    A = b
    B = a

maxg = gcd(A,B)
#print(maxg)
gcd = []
for i in range(1,maxg+1):
    if A % i == 0:
        gcd.append(i)


ansg = [] # 公約数
for j in gcd:
    if B%j == 0:
        ansg.append(j)
#素数を数える
#print(ansg)
ans = 0
for k in ansg:
    if is_prime(k) == True:
        ans += 1

print(ans+1)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
a,b=map(int,input().split())
c=gcd(a,b)
if c==1:
  print(1)
  exit()
D=[]
P=[]
def E(c):
    P=[]
    E=[i+1 for i in range(1,int(c**0.5)+1)]
    while True:
        p=E[0]
        if int(c**0.25)+1<=p:
            return P+E
        P.append(p)
        E=[e for e in E if e%p!=0]
P=E(c)
f=True
for p in P:
  if c%p==0:
    f=False
    break
if f:
  print(2)
  exit()
for i in range(2, int(-(-gcd(a,b)**0.5//1))+1):
  if c%i==0:
    D.append(i)
    while c%i==0:
      c//=i
  if c==1:
    break
print(len(D)+1)

Submission status: Wrong Answer

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

max_num = max(A, B)

sqrt = int(max_num ** 0.5)
is_prime = [True] * (sqrt + 1)
is_prime[0] = False
is_prime[1] = False
for i in range(2, sqrt + 1):
    if not is_prime[i]:
        continue
    for j in range(i * 2, sqrt + 1, i):
        is_prime[j] = False
primes = [i for i in range(sqrt + 1) if is_prime[i]]

count = 1
for i in primes:
    if A % i == 0 and B % i == 0:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import sys


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


def furui(data):
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data


a, b = map(int, input().split())
# a, b = 1, 1
if a == 1 and b == 1:
    print(0)
    sys.exit()
a = make_divisors(a)
a = furui(a)
b = make_divisors(b)
b = furui(b)
print(len(set(a) & set(b)) + 1)

Submission status: Wrong Answer

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

p_nums = []
for i in range(1, int(max([A, B])**0.5) + 1):
    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:
import fractions
import math

tmp = list(map(int,(input().split())))
a = tmp[0]
b = tmp[1]

#limit = min(fractions.gcd(a, b), int(math.sqrt(a)), int(math.sqrt(b)))
limit = min(int(math.sqrt(a)), int(math.sqrt(b)))
cnt = 0
for i in range(2, limit+1):
  flag = False
  while (a % i == 0) and (b % i == 0):
    a = a // i
    b = b // i
    flag = True
  if flag:
    cnt += 1
    
print (cnt+1)

Submission status: Wrong Answer

Solution code:
import sys,queue,copy
sys.setrecursionlimit(10**8)
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

a,b = inpl()

A = max(a,b)
B = min(a,b)

Alist =list()
i = 1
while i <= A/i :
    if A%i==0:
        Alist.append(i)
        Alist.append(A/i)
    i += 1
i=1
Blist =list()
while i <= B/i :
    if B%i==0:
        Blist.append(i)
        Blist.append(B/i)
    i += 1

Clist = list()
for i in range (len(Alist)):
    if Alist[i] in Blist:
        Clist.append(Alist[i])

Clist.sort()
Clist = list(set(Clist))
anslist = list()
for i in range(len(Clist)):
    if Clist[i]==1:
        anslist.append(Clist[i])
    elif len(anslist) == 1:
        anslist.append(Clist[i])
    elif len(anslist) >= 2:
        for j in range(1,len(anslist)):
            if Clist[i] % anslist[j] == 0:
                break
        else:
            anslist.append(Clist[i])

print(len(anslist))

Submission status: Wrong Answer

Solution code:
inp = input().split()
a = int(inp[0])
b = int(inp[1])

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

  return divisors

def gcd(a, b):
  while b != 0:
    a, b = b, a % b
  return a
  
a_div = make_divisors(a)
b_div = make_divisors(b)

common_div = list(set(a_div) & set(b_div))

out = []
for i in range(len(common_div)):
  for j in range(i, len(common_div)):
    if j == i:
      continue
    if gcd(common_div[i], common_div[j]) != 1:
      out.append(max(common_div[i], common_div[j]))
      break

d = set(common_div).difference(set(out))
print(len(d))

Submission status: Wrong Answer

Solution code:
from sys import stdin

a, b = [int(x) for x in stdin.readline().split()]

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

c = 1
lim = int(a**0.5)
n = 0
i = 2
while a > 1 and i <= lim:
    n = 0
    while a % i == 0:
        a //= i
        n += 1
    if n > 0:
        print(i, n, a)
        c += 1
    i += 1
if a > 1:
    c += 1

print(c)

Submission status: Wrong Answer

Solution code:
import math
data = input().split(" ")
a = int(data[0])
b = int(data[1])
c = math.sqrt(a)
p = []
if c <= math.sqrt(b):
	c = math.sqrt(b)
prime = [2, 3]
for n in range(5, int(c), 2):
	isprime = True
	for i in range(1, len(prime)):
		if prime[i] ** 2 > n:
			break
		if n % prime[i] == 0:
			isprime = False
			break
	if isprime:
		prime.append(n)

for d in prime:
	if d >= c:
		break
	if a % d == 0:
		if b % d == 0:
			p.append(d)
print(len(p)+1)

Submission status: Wrong Answer

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

List = cf(a, b)
import fractions

def check(x1, x2):
  if fractions.gcd(x1, x2) == 1:
    return 1
  else:
    return 0

Answer = []
for i in range(len(List)):
  if i == 0:
    Answer.append(List[i])
  else:
    checker = 1
    for j in range(len(Answer)):
      checker *= check(Answer[j],List[i])
    if checker == 1:
      Answer.append(List[i])
    else:
      break

print(len(Answer)+1)

Submission status: Wrong Answer

Solution code:
import fractions
import math
a,b = [int(i) for i in input().split()]

gcd = fractions.gcd(a,b)

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
gcd = 777
l = [i for i in range(2, gcd +1) if gcd % i == 0]

print(len([i for i in l if is_prime(i)]) +1)