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:
import fractions

a, b = map(int, input().split())
count = 0
# a, b = (12, 18)

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 = make_divisors(a)
d = make_divisors(b)
e = []
for i in c:
    if i in d:
        e.append(i)

print(e)
e.pop(0)
e.sort()

gcd_list = [1]
for i in e:
    count = 0
    for j in gcd_list:
        if fractions.gcd(i, j) != 1:
            break
        else:
            count += 1
        if count == len(gcd_list):
            gcd_list.append(i)

# for i in range(len(e)):
#     for j in range(i+1, len(e)):
#         if math.gcd(e[i], e[j]) == 1:
#             print(e[i], e[j])
#             count += 1

print(len(gcd_list))

Submission status: Wrong Answer

Solution code:
import fractions

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

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(1 + len(factorization(N)))

Submission status: Wrong Answer

Solution code:
def f(n):
    result = set()
    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
            result.add(i)

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

    if len(result) == 0:
        result.add(n)

    return result


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

fa = f(a)
fb = f(b)

print(len(fa & fb)+1)

Submission status: Wrong Answer

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

list =[]
result = [1]
for i in range(2,min(N)):
  if N[0] % i == 0 and N[1]% i == 0:
    list.append(i)
    

for j in list:
  if int(j)%2:
    result.append(j)
  
print(len(result))

Submission status: Wrong Answer

Solution code:
def check(a,b):
    if b == 0 :
        return a
    return check(b,a%b)
def check2(x,y):
    for i in range(2,min(x,y)+1):
        if x % i == 0 and y % i == 0 :
            return i
A,B = map(int,input().split())
memo = [0 for i in range(min(A,B))]
memo[0] = 1
ans = 1
while True :
    if check(A,B)== 1 :
        break
    p = check2(A,B)
    if memo[p] == 0 :
        memo[p-1] = 1
        ans += 1
    A = (A//p)
    B = (B//p)


print(ans)

Submission status: Wrong Answer

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

#import numpy as np
import math
import fractions
gcd = fractions.gcd(a,b)

pn=[2];A=int(math.sqrt(gcd))+1
for L in range(3,A+1):
    chk=True
    for L2 in pn:
        if L%L2 == 0:chk=False
    if chk==True:pn.append(L)

count = 1
for i in pn:
    if gcd %i == 0:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
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
for _ in range(Plen):
    if Is[_] != 0:
        ans += 1
print(str(ans))

Submission status: Wrong Answer

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

def factorization(n):
    s = set()
    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)
    return s

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

num = min(A,B)
tmps = {}
p = 2
for p in range(2, math.ceil(num**0.5)+1):
    if A % p == 0 and B % p == 0:
        tmps[p] = True
    p += 1

if num != 1 and  A % num == 0 and B % num == 0:
    tmps[num] = True

#print(tmps)
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())


def frac(num):
		arr = []
		tmp = num
		for i in range(2, int(-(-A ** 0.5 // 1)) + 1):
				if tmp % i == 0:
						cnt = 0
						while tmp % i == 0:
								cnt += 1
								tmp //= i
						arr.append(i)

		if tmp != 1:
				arr.append(tmp)

		if arr == []:
				arr.append(A)
		return arr


listA = frac(A)
listB = frac(B)

AB = set(listA) & set(listB)
sum = len(AB)
if A != 0 and B != 0:
		print(sum+1)
else:
		print(sum)

Submission status: Wrong Answer

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

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

M = gcd (A, B)
now = 2
result = 1
inner = 0

while list[0] > now and now < M:
    while list[0] % now == 0 and list[1] % now == 0:
        inner = 1
        list[0] = list[0] // now
        list[1] = list[1] // now
    if inner == 1:
        inner = 0
        result += 1
    now += 1

print(result)

Submission status: Wrong Answer

Solution code:
import fractions

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

# 公約数の中の素数の数を考えれば良いのではないか？

n = fractions.gcd(A, B)

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 = list(set(table))
    return table

data = divisor(n)
# print(data)
data.remove(1)
ans = []

while data != []:
  p = data[0]
  ans.append(p)
  data = [e for e in data if e % p != 0]

ans.insert(0, 1)

print(len(ans))

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

if prime(a) and prime(b) and a==b:
  print(2)
  exit()

l = []
for i in range(1, max(int(math.sqrt(a))+2, int(math.sqrt(b))+2)):
  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 j != 0:
      if b%j == 0 and prime(j):
        l.append(j)
    k = b//i
    if k != 0:
      if a%k == 0 and prime(k):
        l.append(k)
#print(set(l))
print(len(set(l)))

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()
	ans = 0

	lin = cf(A,B)
	lin.append(1)
	lin.sort()
	#ansln =copy.deepcopy(lin)

	ans = 1
	for i, val in enumerate(lin):
		flg = True
		for j, vol in enumerate(lin):
			if val >= vol:
				continue

			ck = cf(val,vol)
			if len(ck) == 0:
				pass
			else:
				flg = False
				lin.remove(vol)
				break

		if flg == True:
			ans += 1

	#print(lin)
	print(len(lin))

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


if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import math
import sys
import itertools
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

a,b = IL()
num = int(math.sqrt(max(a,b)))
yakusuu = []
ansl = []
ans = 0

for i in range(1,num+1):
  if a%i == 0 and b%i == 0:
    yakusuu.append(i)

for i in yakusuu:
  num2 = int(math.sqrt(i))
  for k in range(2,num2+1):
    if i%k == 0:
      break
  else:
    ansl.append(i)

for i in range(len(ansl)):
  for j in range(len(ansl)):
    if i == j:
      continue
    else:
      aa, bb = ansl[i], ansl[j]
      if aa == 1:
        continue
      else:
        num3 = min(aa,bb)
        for k in range(2,num3+1):
          if aa%k == 0 and bb%k == 0:
            break
        else:
          continue
        break
  else:
    ans += 1

#print(yakusuu)
#print(ansl)
print(ans)


"""
for i in itertools.combinations(ansl, 2):
  print(i)
  aa, bb = i
  if aa == 1:
    ans += 1
  else:
    num3 = min(aa,bb)
    for k in range(2,num3+1):
      if aa%k == 0 and bb%k == 0:
        break
    else:
      ans += 1

#print(yakusuu)
print(ansl)
print(ans)
"""

Submission status: Wrong Answer

Solution code:
import math

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

A,B = [int(i)for i in input().split()]
C = gcd(A,B)

def answer(C):
    ans = 1
    maxif = int(math.sqrt(C))+3
    for i in range(2,maxif+3):
        if C%i==0:
            ans+=1
            while C%i==0:
                C=C//i
    return(ans)



print(answer(C))

Submission status: Wrong Answer

Solution code:
import math
from math import ceil
import random

def is_prime(q,k=10000):
    q = abs(q)
    if q == 2 or q == 1: 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())
yakusu = []
for i in range(1, ceil(math.sqrt(max(a, b)))+1):
    if a % i == 0 and b % i == 0 and is_prime(i):
        yakusu.append(i)
print(len(yakusu))

Submission status: Wrong Answer

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

#print(x,y)

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
x_li=(make_divisors(x))
y_li=(make_divisors(y))
z_li=(list(set(x_li)&set(y_li)))
#print(z_li)

import math
count=1
for n in z_li:
  if n == 1:
    count=count+1
    continue
  for k in range(2, int(math.sqrt(n)) + 1):
    if n % k == 0:
      break;
    else:
      count = count+1
print(count)

Submission status: Wrong Answer

Solution code:
import math

A,B=map(int,input().split())
max=max(A,B)
rng=math.ceil(math.sqrt(max))
divisor=[1]
for i in range(2,rng+2):
    if A%i==0 and B%i==0:
        for x in divisor:
            if i%x==0 and x!=1:
                break
        else:
            divisor+=[i]

print(len(divisor))

Submission status: Wrong Answer

Solution code:
from math import sqrt, ceil

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

count = 1
divisors = []
if A % 2 == B % 2 == 0:
    divisors.append(2)
    count += 1

for i in range(3, ceil(sqrt(min(A, B))), 2):
    if A % i != 0 or B % i != 0:
        continue
    for j in divisors:
        if i % j == 0:
            break
    else:
        divisors.append(i)
        count += 1

if count == 1 and min(A, B) != 1 and max(A, B) % min(A, B) == 0:
    count += 1

print(count)

Submission status: Wrong Answer

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

while A&C != 0 and B%C != 0:
  if A < B:
    B = C
  else:
    A = C
  C = abs(A-B)

i = 2
ans = 1
while C > 1:
  if C%i == 0:
    ans += 1
    while C%i == 0:
      C //= i
  i += 1

print(ans)

Submission status: Wrong Answer

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

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]

prime = [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541]

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

Submission status: Wrong Answer

Solution code:
import fractions
import heapq

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

cd = []
max_cd = fractions.gcd(A, B)

for i in range(1, max_cd + 1):
    if not max_cd % i == 0:
        continue

    a = max_cd // i

    if i > a:
        break

    heapq.heappush(cd, i)
    heapq.heappush(cd, a)

l = []

for i in range(0, len(cd)):
    c = heapq.heappop(cd)
    if not l:
        l.append(c)
    else:
        join = True
        for j in range(0, len(l)):
            k = l[j]
            if fractions.gcd(c, k) != 1:
                join = False
                break
        if join:
            l.append(c)

print(len(l))

Submission status: Wrong Answer

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

print(x,y)

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
x_li=(make_divisors(x))
y_li=(make_divisors(y))
z_li=(list(set(x_li)&set(y_li)))
print(z_li)

import math
count=1
for n in z_li:
  if n == 1:
    count=count+1
    continue
  for k in range(2, int(math.sqrt(n)) + 1):
    if n % k == 0:
      break;
    else:
      count = count+1
print(count)

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
    if i > d - c or c == 1:
        break
    i += 1

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

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

def sosuu(a):
	sosuu_list = set()
	while 1:
		flag = True
		for i in range(2,a+1):
			if a % i == 0 and a != i:
				a = a//i
				sosuu_list.add(i)
				flag = False
				break
		if flag:
			sosuu_list.add(a)
			return sosuu_list

a = sosuu(a)
b = sosuu(b)

cnt = Counter(a)
cnt2 = Counter(b)
cnt.update(cnt2)
# print(cnt)
cnt = sorted(cnt.items(),reverse=1)
ans = 1
for i,n in cnt:
	if n == 2:
		ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

def common_divisor(n):
  if n == 1:
    return [1]
  if n ==2:
    return [1,2,4]
  ret = []
  for i in range(1,math.ceil(math.sqrt(n))):
    if n%i==0:
      ret.append(i)
      ret.append(n//i)      
  return sorted(ret)

ca = common_divisor(a)
cb = common_divisor(b)

sa = set(ca)
c = sa.intersection(cb)

count = 0
for ci in c:
  if len(common_divisor(ci))<=2:
    count+=1    

print(count)

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(2, temp):
    if a%i==0 and b%i==0:
        c.append(i)

d = copy.copy(c)
for ele in c:
    d = [e for e in d if e%ele!=0 or e==ele]

print(len(d)+1)

Submission status: Wrong Answer

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

# from math import gcd
from fractions import gcd

def coprime2(a, b):
    return gcd(a, b) == 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()
    return divisors



def solve(A: int, B: int):
    x = list(set(make_divisors(A)) & set(make_divisors(B)))
    
    ans = 0
    nn = len(x)
    for i in range(nn):
        t = [x[i]]
        for j in range(i+1,nn):
            f = True
            for k in t:
                if(coprime2(x[j],k) != 1):
                    f = False
            if(f):
                t.append(x[j])
                ans = max(ans, len(t))
    if(len(x) == 1 and x[0] == 1):
        print(1)
    else:
        print(ans)
            
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    a, b = map(int, input().split(' '))
    d_s = make_divisors(a, b)

    ans = 0
    for d in d_s:

        flg = True
        for j in d_s[1:]:
            if d == j:
                continue
            if d % j == 0:
                flg = False
                break
        if flg:
            ans += 1
    print(ans)


def make_divisors(a, b):
    divisors = []
    n = max(a, b)
    for i in range(1, int(n**0.5)+1):
        if a % i == 0 and b % i == 0:
            divisors.append(i)
    return divisors


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from math import sqrt
import sys
#input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))
A, B = inpl()
A = B = (10**9 + 7)*6

def primes(N):
    sieve = [1]*(N+1)
    sieve[:2] = [0, 0]
    P = []
    for i in range(2, N+1):
        if sieve[i]:
            P.append(i)
            for j in range(2*i, N+1, i):
                sieve[j] = 0
    return P

P = primes(10**6)

ans = 1

ext = []

ais = True
bis = True

S = min(A, B)
for p in P:
    if p > min(A, B):
        break
    ans += int(A%p == B%p == 0)
    while A%p == 0:
        A //= p
    while B%p == 0:
        B //= p
else:
    if A > 1:
        ans += int(B%A == 0)
    elif B > 1:
        ans += int(A%B == 0)

print(ans)

Submission status: Wrong Answer

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

def sieve(n):
    """Sieve of Eratosthenes"""
    if n < 2:
        is_prime = [False for _ in range(n+1)]
        return is_prime

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

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

    return primes

def factorization(n, primes):
    d = dict()
    temp = n
    for i in primes:
        if i > temp:
            break

        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            d[i] = cnt
    
    if temp != 1:
        d[temp] = 1
    
    if len(d) == 0:
        d[n] = 1
    
    return d

def main():
    input = sys.stdin.readline
    A, B = map(int, input().split())
    A, B = min(A, B), max(A, B)
    primes = sieve(10**6 + 1)

    Af = factorization(A, primes)
    Bf = factorization(B, primes)
    cnt = 1
    for a in Af.keys():
        if a in Bf.keys():
            cnt += 1

    return cnt

if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

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

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

print(len(factorization(fractions.gcd(A,B)))+1)

Submission status: Wrong Answer

Solution code:
import math
A, B = [int(i) for i in input().split()]
# 公約数リストを作る
C = [1]
for i in range(2, int(math.sqrt(max(A, B)))+1):
    if A%i == 0 and B%i == 0:
        C.append(i)
        if A == B and i != A//i:
            C.append(A//i)
        else:
            if i != A//i and B%(A//i) == 0:
                C.append(A//i)
            if i != B//i and A%(B//i) == 0:
                C.append(B//i)
C.sort()
for i in range(len(C)-1, 0, -1):
    for j in range(1, i):
        if C[i]%C[j] == 0:
            del C[i]
            break
print(len(C))

Submission status: Wrong Answer

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

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

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

print(len(divisor(A,B))+1)

Submission status: Wrong Answer

Solution code:
A, B = map(int, input().split())
N = [i for i in range(1, min(A//2, B//2)+1) if A%i == 0 and B%i==0]
M = 1

for i in range(len(N)):
	if i != 0:
		for m in N[i-1::-1]:
			if N[i] % m == 0:
				break
		if m == N[0]:
			M = N[i]

print(M)

Submission status: Wrong Answer

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

import fractions
gcd = fractions.gcd(A, B)

n = 1
count = 0
while n <= gcd:
    if gcd % n == 0:
        #print("matched {}".format(n))
        count += 1
        gcd //= n
    n += 1

print(count)

Submission status: Wrong Answer

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

if a < b:
    a, b = b, a
while a % b != 0:
    a, b = b, a % b
# print(b)

n = b
a = []

while n % 2 == 0:
  if 2 not in a:
    a.append(2)
  n //= 2
f = 3
while n > 1:
  if n % f == 0 and f not in a:
    a.append(f)
    n //= f
  else:
    f += 2

N = len(a)

# print(a)
print(N+1)

Submission status: Wrong Answer

Solution code:
import math

def gcd(a,b):
    if a%b==0:
        return b
    else:
        return gcd(b,a%b)
    
a,b=list(map(int,input().strip().split()))
c=gcd(a,b)
d=0
for i in range(2,math.ceil(math.sqrt(c)+2)):
    if c%i==0:
        d=d+1
        c=c//i
print(d+1)

Submission status: Wrong Answer

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

#最大公約数を求める
max_val = max(a, b)
min_val = min(a, b)

while(1):
  if max_val % min_val ==0:
    break
  else:
    tmp = max_val % min_val
    max_val = min_val
    min_val = tmp
    
#print(min_val)

list = []

for i in range(1, min_val//2 + 1):
  if min_val % i == 0:
    list.append(i)
    
#list.append(min_val)
    
#print(list)
sum = 0
for i in range(len(list)):
  for j in range(len(list)):
    if (list[j] % list[i]) == 1:
      sum += 1
 
print(sum)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math

counter = 0

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

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

if(B > A):
    tmp = B
    B = A
    A = tmp

minimum = euqlid(A, B)

for i in range(minimum):
    if(minimum % (i + 1) == 0):
        judge = True
        for j in range(int(math.sqrt(i) - 1)):
            if(i % (j + 1) == 0):
                judge = False
                break
        if(judge):
            counter += 1

if(B == 1):
    print(1)
else:
    print(counter)

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)
  return divisors

def make_cd(x, y):
  div1=make_divisors(x)
  div2=make_divisors(y)
  cd=[]
  for i in div1:
    for j in div2:
      if i==j:
        cd.append(i)
        break
  return cd

A, B=map(int, input().split())
if A<B:
  A,B=B,A
cd=make_cd(A, B)
ok=[True for _ in range(len(cd))]
for i in range(1, len(cd)):
  if not ok[i]:
    continue
  for j in range(i+1, len(cd)):
    if cd[j]%cd[i]==0:
      ok[j]=False
print(sum([1 if ok[i] else 0 for i in range(len(cd))]))
'''
is_prime=[True for _ in range(B)]
for i in range(2, int(B**0.5)+1):
  if not is_prime[i]:
    continue
  for j in range(i*2, n+1, i):
    is_primt[j]=False
'''

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) +2):
        if n%i==0 and n!=2:
            num=0
            break
        else:
            continue
    return num

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

ans=0
for i in range(1, int(math.sqrt(p) + 1e-9) +2):
    if p%i==0 and q%i==0:
        ans+=func(i)

if func(p)==1 and q%p==0:
    ans+=1
    
print(ans)

Submission status: Wrong Answer

Solution code:
import math
def is_prime(n):
	if n == 1: return True
	for k in range(2, int(math.sqrt(n)) + 1):
		if n % k == 0:
			return False
	return True
 
a, b = map(int,input().split())
 
c = 0
for i in range(1,min(a,b)+1):
	if a % i == 0 and b % i == 0:
		if is_prime(i):
			c+=1			
		else:
			break
		
print(c)

Submission status: Wrong Answer

Solution code:
from math import sqrt
A,B = map(int,input().split())
dA = set()
dB = set()
r = int(sqrt(max(A,B))) + 1
for i in range(1,r):
    if A % i == 0:
        dA.add(i)
        # dA.add(A//i)
    if B % i == 0:
        dB.add(i)
        # dB.add(B//i)
# print(dA,dB)
CD = dA & dB
# print(CD)
#print(len(CD))

m = max(CD)
flg = [True] * (m+1)
flg[0] = False
for i in range(2,m+1):
    if i not in CD: flg[i] = False
    if flg[i]:
        t = i
        i += t
        while i <= m:
            flg[i] = False
            i += t
# print(flg)

isP = False
if A==B:
    isP = True
    m = max(A,B)
    for i in range(2,r):
        if m % i == 0:
            isP = False
            break

print(sum(flg)+isP)

Submission status: Wrong Answer

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

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

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

    return arr

res = dict(factorization(fractions.gcd(a,b)))
print(len(res))

Submission status: Wrong Answer

Solution code:
import math
A, B = [int(i) for i in input().split()]
# 公約数リストを作る
C = []
for i in range(1, int(math.sqrt(max(A, B)))+1):
    if A%i == 0 and B%i == 0:
        C.append(i)
        if A == B and i != A//i:
            C.append(A//i)
        else:
            if i != A//i and B%(A//i) == 0:
                C.append(A//i)
            if i != B//i and A%(B//i) == 0:
                C.append(B//i)
C.sort()
for i in range(len(C)-1, 0, -1):
    for j in range(1, i):
        if C[i]%C[j] == 0:
            del C[i]
            break
print(len(C))

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
    if i > d - c:
        break
    i += 1

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

print(ans)

Submission status: Wrong Answer

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

def soinsu(n):
  c = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      while temp%i==0:
        temp //= 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:
#D
from fractions import gcd
#from math import gcd
import collections
a, b = map(int,input().split())
tmp = gcd(a, b)

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

if tmp == 1:
    l = 1
    ans = 1
else:
    l = prime_factorize(tmp) + [1]
    print(l)
    clist = collections.Counter(l)
    ans = len(clist.keys())
print(ans)