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:
A, B = map(int, input().split())
ls = []
ans = 0
for i in range(1, max(int(A**0.5)+1, int(B**0.5)+1)):
  if A%i==0 and B%i==0:
    for n in range(2,int(i**0.5)+1):
      if i%n==0:
        break
    else:
      ans += 1
    j = A//i
    if j%i==0 or j<=i:
      continue
    for n in range(2,int(j**0.5)+1):
      if j%n==0:
        break
    else:
      ans += 1
print(ans)

Submission status: Wrong Answer

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 g2%i == 0:
            cnt += 1
            while g%i == 0:
                g //= i

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)

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

primes = []
for i in range(2, 10**3+10):
    if all(i%p for p in primes):
        primes.append(i)
# print(primes)

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

g = gcd(A, B)
count = 0
for p in primes:
    if g < p:
        break
    if g%p == 0:
        count += 1

print(count+1)

Submission status: Wrong Answer

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

import math

def prime(n):
  i = 1
  while i < int(math.sqrt(n)):
    i += 1
    if n%i == 0:
      return False
  else:
    return True

#print(prime(5))

l = []
for i in range(1, min(int(math.sqrt(a))+1, int(math.sqrt(b))+1)):
  if i == 1:
    l.append(i)
  else:
    if a%i == 0 and b%i == 0 and prime(i):
      l.append(i)
    j = a//i
    if b%j == 0 and prime(j):
      l.append(j)
    k = b//i
    if a%k == 0 and prime(k):
      l.append(k)
#print(set(l))
print(len(set(l)))

Submission status: Wrong Answer

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

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

import numpy as np

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

t = seachPrimeNum(10*15)

c = 1

for i in range(len(t)):
    if a % t[i] == 0:
        c += 1

print(c)

Submission status: Wrong Answer

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
    return set(table)
G=list(divisor(A) & divisor(B))
ans=0

for i,g in enumerate(G):
    if g==1:
        ans+=1
        continue
    for j,g_right in enumerate(G[i+1:]):
        if g_right%g == 0:
            G.remove(g_right)
    ans+=1
print(ans)

Submission status: Wrong Answer

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

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(12):
    a = [2,3,5,7,11,13,17,19,23,29,31,37][k]
    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: Wrong Answer

Solution code:
a, b = map(int, input().split())
common_div = [1]
for i in range(2, int(min(a, b) ** 0.5) + 1):
    # if map(lambda x: i % x == 0, common_div[1:])
    for v in common_div[1:]:
        if i % v == 0:
            break
    else:
        if a % i == 0 and b % i == 0:
            common_div.append(i)

print(len(common_div))

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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
print(ans)

Submission status: Wrong Answer

Solution code:
import math
A,B = map(int, input().split())
num_set = set()
i=2
while True:
    if(A%i==0 and B%i==0):
        num_set.add(i)
        A = A//i
        B = B//i
    elif(i > math.sqrt(A) or i > math.sqrt(B)):
        break
    else:
        i = i+1
print(len(num_set)+1)

Submission status: Wrong Answer

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

ld=divisor(gcd(a,b))

cnt=0
for i in range(len(ld)):
    cnta=0
    for j in range(len(ld)):
        if i==j:
            break
        if gcd(ld[i],ld[j]) !=1:
            cnta = cnta+1
        #print(i,i,ld[i],ld[j],gcd(ld[i],ld[j]))
    if cnta==0:
        cnt=cnt+1

print(cnt)

#print(ld)

Submission status: Wrong Answer

Solution code:
import math

prime = [2]


def is_prime(n: int) -> bool:
    for p in prime:
        if p * p > n:
            break
        if n % p == 0:
            return False
    return True


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

for i in range(2, 10 ** 6 + 1):
    if not is_prime(i):
        continue
    prime.append(i)
    
    if A % i == 0 and B % i == 0:
        res += 1

print(res)

Submission status: Wrong Answer

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)

Submission status: Wrong Answer

Solution code:
import math

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

a, b = map(int, input().split())
x    = gcd(a, b)
y    = int(math.sqrt(x))
ps   = [1, 2, 3, 5, 7, 11, 13]
p    = ps[-1]

def check(p):
	q = int(math.sqrt(p))
	
	for i in range(2, len(ps)):
		if p % ps[i] == 0:
			return False
		if q < ps[i]:
			break
	
	return True

while p <= y:
	p += 2
	while check(p) == False:
		p += 2
	ps.append(p)

print(sum(1 for p in ps if x % p == 0))

Submission status: Wrong Answer

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

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

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

g = gcd(N, M)

##### is_prime #####
prime = [True] * (int(g ** 0.5) + 500000)
prime[0] = False
prime[1] = False
for n in range(2, len(prime)):
    if prime[n] == False:
        continue

    for v in range(n * 2, len(prime), n):
        prime[v] = False

p = [v for v in range(len(prime)) if prime[v] == True]

ans = 0
for v in p:
    if g % v == 0:
        ans += 1

print(ans + 1)

Submission status: Wrong Answer

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

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

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

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

if d%c == 0 and not c == 1:
    ans += 1
    

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
#nの素数判定
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

#nの約数列挙
def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            ass.append(n//i)
    return ass #sortされていない

#nの素因数分解(O(n**0.5)
def prime_factor(n):
    ass = []
    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

if __name__ == '__main__':
    ta, tb = map(int,input().split())

    # めんどくさいのでa<=bの場合で考える
    if ta > tb:
        a = tb
        b = tb
    else:
        a = ta
        b = tb

    a_div_set = set(divisor(a))
    b_div_set = set(divisor(b))
    common_div_set = (a_div_set & b_div_set)

    answer = 0
    for e in common_div_set:
        if e == 1 or is_prime(e):
            answer += 1
    print(answer)

Submission status: Wrong Answer

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

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

ret = 0
x = gcd(A, B)
prime = [2, 3]

for i in range(5, x + 1, 2) :
    if i * i > x :
        break
    j = 0
    flg = False
    while prime[j] * prime[j] <= i :
        if i % prime[j] == 0 :
            flg = True
            break
        j += 1
    if flg :
        continue
    prime.append(i)
    
ret = 0
for p in prime :
    if x % p == 0 :
        ret += 1
print(ret + 1)

Submission status: Wrong Answer

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

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

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

g = gcd(N, M)

##### is_prime #####
prime = [True] * (int(g ** 0.5) + 100000)
prime[0] = False
prime[1] = False
for n in range(2, len(prime)):
    if prime[n] == False:
        continue

    for v in range(n * 2, len(prime), n):
        prime[v] = False

p = [v for v in range(len(prime)) if prime[v] == True]

ans = 0
for v in p:
    if g % v == 0:
        ans += 1

print(ans + 1)

Submission status: Wrong Answer

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

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(3):
    a = [2,7,61][k]
    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: Wrong Answer

Solution code:

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


a,b = map(int, input().split())
if a>b:
  a,b = b,a

a_div = divisor(a)
b_div = divisor(b)
ab_div = [ai for ai in a_div if ai in b_div]

#print(a_div)
#print(b_div)
#print(ab_div)
ret = [t1 for t1 in ab_div if sum([t1%t2==0 for t2 in ab_div])==1]
#print(ret)
print(1+len(ret))

Submission status: Wrong Answer

Solution code:
def solve(x, y):
  if x<y:
    x, y = y, x
  cd=[]
  for i in range(2, int(y**0.5)+1):
    if x%i==0 and y%i==0:
      flag=True
      for z in cd:
        if i%z==0:
          flag=False
          break
      if flag:
      	cd.append(i)
      tmp=y//i
      if x%tmp==0:
        flag=True
        for z in cd:
          if tmp%z==0:
            flag=False
            break
        if flag:
      	  cd.append(tmp)
  return len(cd)+1
  
A, B=map(int, input().split())
print(solve(A, B))

Submission status: Wrong Answer

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 g2%i == 0:
            cnt += 1
            while g%i == 0:
                g //= i

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import fractions

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


def sieve_of_eratosthenes(N):
    prime_list = [True for _ in range(N + 1)]
    prime_list[0] = False
    prime_list[1] = False
    for p in range(2, int(N ** 0.5) + 1):
        if prime_list[p]:
            for i in range(2 * p, N + 1, p):
                prime_list[i] = False

    return prime_list


gcd_ = fractions.gcd(a, b)
prime_list = sieve_of_eratosthenes(gcd_)
L = []
if gcd_ % 2 == 0:
    for i in range(1, gcd_):
        if gcd_ % i == 0:
            L.append(i)

if gcd_ % 2 == 1:
    for i in range(1, gcd_):
        if gcd_ % i == 0:
            L.append(i)

ans = 1
for l in L:
    if prime_list[l]:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

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

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

g = gcd(N, M)

##### is_prime #####
prime = [True] * (int(g ** 0.5) + 10000)
prime[0] = False
prime[1] = False
for n in range(2, len(prime)):
    if prime[n] == False:
        continue

    for v in range(n * 2, len(prime), n):
        prime[v] = False

p = [v for v in range(len(prime)) if prime[v] == True]

ans = 0
for v in p:
    if g % v == 0:
        ans += 1

print(ans + 1)

Submission status: Wrong Answer

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

def gcd(a, b):
  if b > a:
    a, b = b,a
  a, b = b, a % b
  if b == 0:
    return a
  else:
    return 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)
  return divisors

N = gcd(A, B)
if N == 1:
  print (1)
  sys.exit()

L = [2]
D = sorted(make_divisors(N))
for i in D[1:]:
  for j in L:
    if i % j == 0:
      break
  else:
    L.append(i)
print (len(L)+1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

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

def divisor(a, b):
    if a < b:
        b, a = a, b
    res = []
    ra = int(a**0.5) + 1 
    for i in range(1, ra):
        if a % i == 0:
            if b % i == 0:
                res.append(i)
                if i != a / i and b % (a/i) == 0:
                    res.append(int(a / i))
            else:
                if i != a / i and b % (a/i) == 0:
                    res.append(int(a / i))
    return sorted(res)

Y = divisor(A, B)
print(Y)
ans = 0
for i in range(len(Y)):
    if is_prime(Y[i]):
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys,fractions
sys.setrecursionlimit(100000)

def ins(): return input().split()
def ii(): return int(input())
def iil(): return list(map(int,ins()))
def lin(): return list(input())
def iin(): return map(int,ins())

a,b = iin()
t = fractions.gcd(a,b)

p=[0,0]+[1]*999999
k=len(p)
for i in range(k//2+1):
    if p[i]==0:continue
    for q in range(2*i,k,i):
        p[q]=0
cnt = 1
for i,j in enumerate(p):
    if j==1 and t%i==0:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import math

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

maxp = int(math.sqrt(max(a,b)))

primes = [1]
is_prime = [True] * (maxp + 1)
#print(is_prime)
for i in range(2, maxp+1):
    #print(i)
    if is_prime[i]:
        primes.append(i)

    j = i * i
    while j <= maxp:
        is_prime[j] = False
        j += i
cnt = 0
#print(primes)
for p in primes:
    if a % p == 0 and b % p == 0:
        cnt += 1

if cnt == 1 and max(a, b) % min (a, b) == 0 and max(a, b) > 1:
    cnt += 1
print(cnt)

Submission status: Wrong Answer

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

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

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

g = gcd(N, M)

##### is_prime #####
prime = [True] * (int(g ** 0.5) + 10)
prime[0] = False
prime[1] = False
for n in range(2, len(prime)):
    if prime[n] == False:
        continue

    for v in range(n * 2, len(prime), n):
        prime[v] = False

p = [v for v in range(len(prime)) if prime[v] == True]

ans = 0
for v in p:
    if g % v == 0:
        ans += 1

print(ans + 1)

Submission status: Wrong Answer

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(1+len(set(fact(A))&set(fact(B))))

Submission status: Wrong Answer

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

def gcd(p, q):
    if p < q:
        p, q = q, p
    while q != 0:
        p, q = q, p % q
    return p

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

res = len(factorization(gcd(a, b)))

print(res if res == 1 else res + 1)

Submission status: Wrong Answer

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

input = sys.stdin.readline


def sieve_of_eratosthenes(target):
    dest = int(math.sqrt(target))
    target_list = list(range(2, target + 1))
    prime_list = []

    while True:
        num_min = min(target_list)
        if num_min >= dest:
            prime_list.extend(target_list)
            break
        prime_list.append(num_min)

        i = 0

        while True:
            if i >= len(target_list):
                break
            elif target_list[i] % num_min == 0:
                target_list.pop(i)
            i += 1

    return(prime_list)

def main():
    A, B = map(int, input().split())
    k = set([1])
    try:
        prime_list = sieve_of_eratosthenes(min(A, B))

        for p in prime_list:
            if A % p == 0 and B % p == 0:
                k.add(p)
        print(len(k))
    except:
        print(1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


fa = factorize(A)
fa = factorize(A)

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

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

Submission status: Wrong Answer

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 == 0:
            break
        if n % i == 0: #割り切れるとき
            if m % i == 0:
                divisors.append(i)
            while n % i == 0 and n != 1:
                n //= i
            if n == 1:
                break
    divisors.sort()
    return divisors

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

Submission status: Wrong Answer

Solution code:
A, B = map(int, input().split())
ls = []
ans = 0
for i in range(1, max(int(A**0.5)+1, int(B**0.5)+1)):
  if A%i==0 and B%i==0:
    for n in range(2,int(i**0.5)+1):
      if i%n==0:
        break
    else:
      ans += 1
    j = A//i
    if i==j:
      continue
    for n in range(2,int(j**0.5)+1):
      if j%n==0:
        break
    else:
      ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math

prime = [2]


def is_prime(n: int) -> bool:
    for p in prime:
        if p * p > n:
            break
        if n % p == 0:
            return False
    return True


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

upper = int(min(math.sqrt(A), math.sqrt(B), 10 ** 6)) + 1

for i in range(2, upper):
    if not is_prime(i):
        continue

    prime.append(i)
    cnt_A = 0
    cnt_B = 0

    while A % i == 0:
        cnt_A += 1
        A //= i
    while B % i == 0:
        cnt_B += 1
        B //= i

    if cnt_A > 0 and cnt_B > 0:
        res += 1

print(res)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
a, b = map(int, input().split())
# a, bに何種類共通の素因数があるかを調べればよい.
# 試し割り法で、どちらも素因数だと判断されればOK.10^6まで調べればいい.
ans = 1 # 1の分
if((a % 2) == 0 and (b % 2) == 0):
    ans += 1
while a % 2 == 0:
    a //= 2
while b % 2 == 0:
    b //= 2
f = 3
checker = min(a, b)
while f * f <= checker:
    if( (a % f) == 0 and (b % f) == 0):
        ans += 1
    while a % f == 0:
        a //= f
    while b % f == 0:
        b //= f
    f += 2

print(ans)

Submission status: Wrong Answer

Solution code:
a, b = map(int, input().split())
import itertools
def divisor(n): #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
t1 = divisor(a)
t2 = divisor(b)
t = t1 & t2
n = 0
for x in itertools.combinations(t,2):
    a1 = divisor(x[0])
    a2 = divisor(x[1])
    a = a1 & a2
    if a == {1}:
        n += 1
if a == 1 or b == 1:
    print(1)
else:
    print(n)

Submission status: Wrong Answer

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])
    if arr==[]:
        arr.append([n, 1])
    return arr
a, b = map(int,input().split())
a_set = set()
for tmp in factorization(a):
    num = tmp[0]
    if num not in a_set:
        a_set.add(num)
b_set = set()
for tmp in factorization(b):
    num = tmp[0]
    if num not in b_set:
        b_set.add(num)
ans = a_set & b_set
print(len(ans) + 1)

Submission status: Wrong Answer

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

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

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

if d%c == 0 and not c == 1:
    ans += 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
ans = 1
d = []
a, b = map(int, input().split())
if a == 1 or b == 1:
  print(1)
else:
  list = cf(a,b)
  while len(list) >= 1:
    ans += 1
    z = list[0]
    for i in list:
      if i%z != 0:
        d.append(i)
    list = d
    d = []
print(ans)

Submission status: Wrong Answer

Solution code:
#from collections import defaultdict 
import copy
A,B = map(int, input().split())

# 公約数のリスト
tmp_list = [1]

num = min(A,B)
#tmps = defaultdict(bool)
tmps = {}
p = 2
while p * p <= num:
    if A % p == 0 and B % p == 0:
        #tmp_list.append(p)
        tmps[p] = True
    p += 1

ans_list = []
d = copy.deepcopy(tmps)
for k in tmps.keys():
    if d.get(k, False):
        aaa = copy.deepcopy(d)
        for n in d.keys():
            if k == n:
                continue
            if n > k and n % k == 0:
                aaa.pop(n)
        d = aaa

print(len(d.keys())+1)

Submission status: Wrong Answer

Solution code:
A, B = map(int, input().split())
ls = []
ans = 0
for i in range(1, max(int(A**0.5)+1, int(B**0.5)+1)):
  if A%i==0 and B%i==0:
    for n in range(2,int(i**0.5)+1):
      if i%n==0:
        break
    else:
      ans += 1
    j = A//i
    for n in range(2,int(j**0.5)+1):
      if j%n==0:
        break
    else:
      ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
def is_prime(num):
    if num==2 or num==3:
        return True
    for i in range(2,int(num**0.5)+1):
        if num%i==0:
            return False
    return True

def main():
    a,b=map(int,input().split())
    s,l=min(a,b),max(a,b)
    #sの約数のうち、素数を求める。
    s_sub=s
    s_prime=[1]
    i=2
    while i<=s_sub:
        print(i,s%i==0,is_prime(i))
        if s%i==0:
            if is_prime(i):
                s_prime.append(i)
                s_sub=s//i
        i+=1
    ans=0
    for i in s_prime:
        if l%i==0:
            ans+=1
    print(ans)
    
main()

Submission status: Wrong Answer

Solution code:
a, b = map(int, input().split())
import itertools
def divisor(n): #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
t1 = divisor(a)
t2 = divisor(b)
t = t1 & t2
n = 0
for x in itertools.combinations(t,2):
    a1 = divisor(x[0])
    a2 = divisor(x[1])
    a = a1 & a2
    if a == {1}:
        n += 1
print(n)