Problem:


Score : 400 points

Problem Statement

Given are positive integers A and B.

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

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

At most, how many divisors can we choose?

Definition of common divisor

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

Definition of being coprime

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

Definition of dividing

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

Constraints

All values in input are integers.

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

Input

Input is given from Standard Input in the following format:

A B

Output

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

Sample Input 1

12 18

Sample Output 1

3

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

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

Sample Input 2

420 660

Sample Output 2

4

Sample Input 3

1 2019

Sample Output 3

1

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



Sample input:
12 18


Sample output:
3

Submission status: Wrong Answer

Solution code:

def divisor(n): #nの約数を全て求める
  i = 2
  table = []
  while i * i <= n:
    if n%i == 0 and sum([i%ti==0 for ti in table])==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(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:
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)

sosu = [1]
d = math.ceil(G**(1/2))
flg = [i for i in range(1, d+1)]


for i in range(2,d+1):
	if flg[i-1] == 0:
		continue
	if G % i == 0:
		sosu.append(i)
		ind = i
		while ind <= d:
			flg[ind-1] = 0
			ind += i


print(len(sosu))

Submission status: Wrong Answer

Solution code:
import math
import numpy as np

a, b = [int(v) for v in input().split()]
sieve = np.array(range(2, math.ceil(math.sqrt(min(a, b))) + 1))

count = 1
while len(sieve) > 0:
    val = sieve[0]
    if a % val == 0 and b % val == 0:
        count += 1
    sieve = sieve[sieve % val != 0]

print(count)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 28 18:51:59 2019
ABC142D
@author: maezawa
"""
import collections

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

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

# making a prime number list
np = int(10**4.5+1) # prime number list less than np
is_prime = [True]*(np+1)

is_prime[0] = False
is_prime[1] = False

for i in range(2, np//2+1): # Sieve of Eratosthenes
    if is_prime[i] == True:
        for j in range(2*i,np+1,i):
            is_prime[j] = False

prime_numbers = [i for i in range(np+1) if is_prime[i]]

# prime factorization
num = gcdab#10**9+7 # a number to be factorized. 
# The maximum number to factrize is np**2. 

facts = [] # list of prime factors
for prime in prime_numbers:
    if prime > num//2:
        break
    dnum = num
    while dnum%prime == 0: 
        facts.append(prime)
        dnum = dnum//prime

mul = 1
for i in facts:
    mul *= i
if mul != num: # if large prime number (> np) is missing
    facts.append(num//mul) # append it

pfs = collections.Counter(facts)
print(len(pfs)+1)

Submission status: Wrong Answer

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

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

def count_(upper_num):
    data = [2] + list(range(3,upper_num+1,2))
    idx = 0
    length = len(data)
    while idx < length:
        prime = data[idx]
        data = [d for d in data if (d==prime or d % prime != 0)]
        idx += 1
        length = len(data)
    
    return data

def make_divisors(n):
    divisors = [1]
    i = 2 
    max_int = n
    while n >1:
        if len(divisors) == 1 and i >= int(n**0.5)+1:
            break
        # nを合う数字で割り切れたら、その割った数と商をリストに追加する。
        # nが平方数のとき、同じ数字が2回追加されてしまうので3行したのif文がある
        if n % i == 0:
            divisors.append(i)
            while n%i == 0:
                n = n//i
        i += 1

    divisors.sort()
    return divisors

print(len(make_divisors(gcd(A,B))))

Submission status: Wrong Answer

Solution code:
import fractions
A,B=list(map(int,input().split()))
gcd=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
so=factorization(gcd)
print(len(so)+1)

Submission status: Wrong Answer

Solution code:
import math

A,B=map(int,input().split())
min=min(A,B)
rng=math.ceil(math.sqrt(min))
count=0
for i in range(1,rng+1):
    if A%i==0 and B%i==0:
        count+=1

print(count)

Submission status: Wrong Answer

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

dx=[]
i=2
while i*i<=x:
    if x%i==0:
        dx.append(x//i)
        dx.append(i)
    i+=1

dy=[]
i=2
while i*i<=y:
    if y%i==0:
        dy.append(y//i)
        dy.append(i)
    i+=1


xny=sorted(list(set(dx).intersection(set(dy))))

N=len(xny)
count=1
for i in range(N):
    needToDel=False
    for j in range(i):
        if xny[i]%xny[j]==0:
            needToDel=True
            break
    if needToDel==False:
        count+=1
print(count)

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])
    if min(A, B):
        print(1)
        return
    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))

if __name__ == '__main__':
    main()

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

Submission status: Wrong Answer

Solution code:
def gcd(x,y):
    if x<y:
        x,y = y,x
    while y>0:
        x,y = y,x%y
    return x
INFTY = 10**6
P = [1 for i in range(INFTY+1)]
P[0] = 0
P[1] = 0
for i in range(2,int((INFTY+1)**0.5)+1):
    for j in range(i*i,INFTY+1,i):
        P[j] = 0
Q = []
for i in range(INFTY):
    if P[i]==1:
        Q.append(i)
A,B = map(int,input().split())
x = gcd(A,B)
cnt = 1
ind = 0
for y in Q:
    if x%y==0:
        ind = 1
        cnt += 1
if ind==0:
    cnt = 2
print(cnt)

Submission status: Wrong Answer

Solution code:
import fractions

A, B = map(int, input().split())
d = fractions.gcd(A, B)
#print('d={}'.format(d))

# make a prime list
# nまでの自然数が素数かどうかを表すリストを返す、エラストテネスの篩 O(nloglogn)
def make_prime_checker(n):
    is_prime = [False, True, False, False, False, True] * (n//6+1)
    del is_prime[n+1:]
    is_prime[1:4] = False, True, True
    for i in range(5, int(n**0.5)+1):
        if is_prime[i]:
            is_prime[i*i::i] = [False] * (n//i-i+1)
    return is_prime
 
primes = [p for p, is_prime in enumerate(make_prime_checker(10**6)) if is_prime]
 
ans = 1
for p in primes:
    if d % p == 0:
        ans += 1
        #print('p={}'.format(p))
    elif p > d:
        break
print(ans)

Submission status: Wrong Answer

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

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

ans = 1
anslist = [1]
        
chk = True
for L2 in pn:
    if c%L2 == 0 : chk = False
if chk == True:
    anslist.append(c)
    ans+=1
#print(pn)


for i in range(len(pn)-1):
    if(c%pn[i]==0):
        ans+=1
        anslist.append(pn[i])
        chk = True
        for j in range(len(pn)-1):
            if((c//pn[i])%pn[j] == 0):
                chk = False
        if(chk == True):
            ans+=1
            anslist.append(c//pn[i])
print(ans)
#print(anslist)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
A,B=map(int, raw_input().split())

n=gcd(A,B)
K=int(n**0.5)+2


s=set()

for i in range(2,K):
	if n%i==0:
		s.add(i)
		n/=i

print len(s)+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 math
def factrial(n):
    factor = set()
    for i in range(1, int(math.sqrt(n)+1)):
        if n % i == 0:
            factor.add(i)
            factor.add(n//i)
    return factor

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

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

fact_a = factrial(a)
fact_b = factrial(b)
fact_int = list(fact_a & fact_b)

choice = []
for i in fact_int:
    prime = True
    for j in choice:
        if gcd(i, j) != 1:
            prime = False
            break
    if prime:
        choice.append(i)

print(len(choice))

Submission status: Wrong Answer

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

pn=[2];A=10000
for L in range(3,A):
    chk=True
    for L2 in pn:
        if L%L2 == 0:chk=False
    if chk==True:pn.append(L)
ans = 0
for x in range(1,int((C+1)**0.5)+1+1):
	if C%x==0 and x in pn:
		ans+=1
print(ans+1)

Submission status: Wrong Answer

Solution code:
import math
ans=1
a,b=map(int, input().split())
d = []
for i in range(1, max(int(a**0.5)+1,int(b**0.5)+1)):
    if a % i == 0 and b % i == 0:
        d.append(i)
        if i != a // i :
            d.append(a//i)
        if  i != b // i:
            d.append(b//i)
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
for i in d:
    if is_prime(i):
        ans+=1
print(ans)

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:
import sys
import os
sys.setrecursionlimit(100000)

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

A, B = map(int,input().split())
gcdAB = gcd(A,B)
P = []
for i in range(2,gcdAB):
    if gcdAB%i==0:
        P.append(i)
        gcdAB /=i
    i+=2
cnt =1
for p in P:
    if p!= 0:
        cnt +=1
print(cnt)

Submission status: Wrong Answer

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

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

def main():
    A, B = map(int, input().split())
    cf = []
    if A % 2 == 0 and B % 2 == 0:
        cf.append(2)
    cf.extend(i for i in range(3, int(math.sqrt(max(A, B)) + 1) + 1, 2) if A % i == 0 and B % i == 0)
    a = []
    for i in cf:
        for j in a:
            if gcd(i, j) != 1:
                break
        else:
            a.append(i)
    print(len(a) + 1)




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def prime_table(n):
    list = [True for _ in range(n + 1)]
    i = 2
    while i * i <= n:
        if list[i]:
            j = i + i
            while j <= n:
                list[j] = False
                j += i
        i += 1

    table = [i for i in range(n + 1) if list[i] and i >= 2]
    return table


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


a, b = map(int, input().split())
Mx = max(a, b)
LIM = int(Mx ** 0.5)

tbl = prime_table(LIM)

ans = 1
# 1

for p in tbl:
    if a % p == 0 and b % p == 0:
        ans += 1

if LIM < a and is_prime(a) and b % a == 0:
    ans += 1

if LIM < b and is_prime(b) and a % b == 0:
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
import math

def prime(x):
  if x==2:
    return True
  else:
      for j in range(2,math.ceil(math.sqrt(x))+1):
        if x%j==0:
          return False
          break
        else:
          pass
      else:
        return True
  
a,b = map(int,input().split())
ab = gcd(a,b)
cnt = 0
for i in range(1,math.ceil(math.sqrt(ab))+1):
  if ab%i==0:
    if prime(i):
      cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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


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

g = gcd(A, B)

print(len(factorize(g)) + 1)

Submission status: Wrong Answer

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

aa = set()
bb = set()

waru = 2
while waru ** 2 <= a:
    if a % waru == 0:
        aa.add(waru)
        a = a // waru
        continue
    waru += 1

aa.add(a)

waru = 2
while waru ** 2 <= b:
    if b % waru == 0:
        bb.add(waru)
        b = b // waru
        continue
    waru += 1

bb.add(b)


print(len(aa & bb) + 1)

Submission status: Wrong Answer

Solution code:
def make_divisors(n):
    divisors = [1]
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            if len(divisors) == 1:
                divisors.append(i)
            else:
                for _divisors in divisors[1:]:
                    if i % _divisors == 0:
                        break
                else:
                    divisors.append(i)
    return divisors

def main():
    a, b = map(int, open(0).read().split())

    div_a = make_divisors(a)
    div_b = make_divisors(b)

    cnt = 0
    for _div_a in div_a:
        if _div_a in div_b:
            cnt += 1

    ans = cnt
    print(ans)
    return()

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math

a, b = [int(v) for v in input().split()]
sieve = list(range(2, math.ceil(math.sqrt(min(a, b))) + 1))

count = 1
while len(sieve) > 0:
    val = sieve.pop(0)
    if a % val == 0 and b % val == 0:
        count += 1
    sieve = [v for v in sieve if v % val != 0]

print(count)

Submission status: Wrong Answer

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

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

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

gcdv = gcd(A, B)
ans = len(fac(gcdv))

if ans == 1:
    print(1)
else:
    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))
print (D)
for i in D[1:]:
  for j in L:
    if i % j == 0:
      break
  else:
    L.append(i)
print (len(L)+1,L)

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)
        m=m//(i+2)
print(ans)

Submission status: Wrong Answer

Solution code:
import fractions

a, b = map(int, input().split())
gcd = 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(len(factorization(gcd))+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:
    ans += 1
    

print(ans)

Submission status: Wrong Answer

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


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

count = 1
for i in range(2, n):
    if n % i == 0:
        while n % i == 0:
            n = n // i
        count += 1
    if i > n:
        break

print(count)

Submission status: Wrong Answer

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

ans = 0
C = int(min(A,B)**0.5)+1
X = [True]*(C+1)
X[0] = X[1] = False
for i in range(2,C+1):
    if X[i]:
        X[i::i] = [False]*(C//i)
        if A%i==0 and B%i==0:
            ans+=1
print(ans+1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
from fractions import gcd
L = 10**6+1
isPrime = [True] * L
isPrime[0] = False
isPrime[1] = False
primes = []
for n in range(2, L):
  if isPrime[n]:
    primes.append(n)
    isPrime[2*n::n] = [False] * ((L-n-1) // n)

def primeFactorization(n):
  ret = dd(int)
  for p in primes:
    while n % p == 0:
      ret[p] += 1
      n //= p
  return  ret

A, B = map(int, input().split())
g = gcd(A, B)
ps = primeFactorization(g)
print(len(ps) + 1)

Submission status: Wrong Answer

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

res = []
for i in range(2, min(max(A, B)-min(A, B), A, B)+1):
    if A % i == 0:
        if B % i == 0:
            for x in res:
                if i % x == 0:
                    break
            else:
                res.append(i)

print(len(res)+1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
#ABC142D
import sys
import math
#sys.setrecursionlimit(100000)

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

#n=int(input())
tmp = input().split()
a,b = list(map(lambda a: int(a), tmp))


tmp=gcd(a,b)

#limit=math.ceil(math.sqrt(tmp))

count=1
#print(limit)

for i in range(2,tmp):
	if (tmp%i==0):
#		print(i)
		count+=1
	while (tmp%i==0):
		tmp=tmp//i
	if(i>tmp):
		break

print(count)

Submission status: Wrong Answer

Solution code:
def gcd(a : int, b: int):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

a, b = map(int, input().split())
g = gcd(a, b)
ans = set([1])
for i in range(2, 1000000):
    while g % i == 0:
        g = g // i
        ans.add(i)

print(len(ans))

Submission status: Wrong Answer

Solution code:
import math
#試し割法
def trial_division(n):
    #素因数を格納するリスト
    factor = []
    #2から√n以下の数字で割っていく
    tmp = int(math.sqrt(n)) + 1
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    #リストが空ならそれは素数
    if not factor:
        return [1]
    else:
        factor.append(n)
        return factor
    return [1]

a,b = input().split(' ')
a = int(a)
b = int(b)
aSet= set(trial_division(a)+[1]+[a])
bSet = set(trial_division(b)+[1]+[b])

ngo = aSet&bSet
print(len(ngo))

Submission status: Wrong Answer

Solution code:
import math

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(math.sqrt(n))+3):
        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 = [int(x) for x in input().split()]
import fractions
gcd = fractions.gcd(a,b)
factors = factorization(gcd)
print
print(len(factors)+1)

Submission status: Wrong Answer

Solution code:
import math
import random


class Prime:
    seed_primes = [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]

    def is_prime(self, n):
        """
        prime test (hybrid)

        see also: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """
        is_prime_common = self.is_prime_common(n)
        if is_prime_common is not None:
            return is_prime_common

        if n < 2000000:
            return self.is_prime_brute_force(n)
        else:
            return self.is_prime_miller_rabin(n)

    def is_prime_common(self, n):
        if n == 1: return False
        if n in Prime.seed_primes: return True
        if any(map(lambda x: n % x == 0, self.seed_primes)): return False

    def is_prime_brute_force(self, n):
        """
        brute force prime test
        use with is_prime_common if you want to skip seed_primes

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

    def is_prime_miller_rabin(self, n):
        """
        miller rabin prime test
        use with is_prime_common if you want to skip seed_primes

        see also
            algorithm: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
            implementation: https://qiita.com/srtk86/items/609737d50c9ef5f5dc59
            improvement: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """

        d = n - 1
        while d & 1 == 0:
            d >>= 1

        # use one of these lines / upper is more efficient.
        witnesses = self.get_witnesses(n)
        # witnesses = [random.randint(1, n - 1) for _ in range(100)]

        for w in witnesses:
            y = pow(w, d, n)

            while d != n - 1 and y != 1 and y != n - 1:
                y = (y * y) % n
                d <<= 1

            if y != n - 1 and d & 1 == 0:
                return False

        return True

    def get_witnesses(self, num):
        def _get_range(num):
            if num < 2047:
                return 1
            if num < 1373653:
                return 2
            if num < 25326001:
                return 3
            if num < 3215031751:
                return 4
            if num < 2152302898747:
                return 5
            if num < 3474749660383:
                return 6
            if num < 341550071728321:
                return 7
            if num < 3825123056546413051:
                return 9
            return 12

        return self.seed_primes[:_get_range(num)]

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

    @staticmethod
    def f(x, n, seed):
        """
        pseudo prime generator
        :param x:
        :param n:
        :param seed:
        :return: pseudo prime
        """
        p = Prime.seed_primes[seed % len(Prime.seed_primes)]
        return (p * x + seed) % n

    def find_factor(self, n, seed=1):
        """
        find one of factor of n
        this function is based to Pollard's rho algorithm

        see also
            algorithm: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
            implementation: https://qiita.com/gushwell/items/561afde2e00bf3380c98

        :param n:
        :param seed:
        :return: factor
        """
        if self.is_prime(n):
            return n

        x, y, d = 2, 2, 1
        count = 0
        while d == 1:
            count += 1
            x = self.f(x, n, seed)
            y = self.f(self.f(y, n, seed), n, seed)
            d = self.gcd(abs(x - y), n)

        if d == n:
            return self.find_factor(n, seed+1)
        return self.find_factor(d)

    def find_factors(self, n):
        primes = []
        if self.is_prime(n):
            primes.append(n)
            return primes

        while n > 1:
            factor = self.find_factor(n)
            primes.append(factor)
            n //= factor

        return primes

class FutureMath:
    def gcd(self, a, b):
        if a < b:
            return self.gcd(b, a)
        if b == 0:
            return a
        while b:
            a, b = b, a % b
        return a

    def gcd_(self, list):
        result = list[0]
        for el in list[1:]:
            result = self.gcd(result, el)
        return result

    def lcm(self, a, b):
        return a * b // self.gcd(a, b)

    def lcm_(self, list):
        result = list[0]
        for el in list[1:]:
            result = self.lcm(result, el)
        return result

    def divisors(self, n):
        result = list()
        for i in range(1, n+1):
            if n % i == 0:
                result.append(i)
        return result

fm = FutureMath()

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

prime = Prime()
primes = prime.find_factors(gcd)

print(primes)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

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 gcd(n,m):
    if m == 0:
        return n
    else:
        return gcd(m,n % m)

P = primes(10**6)
f = defaultdict(lambda : 0)
for i in P:
    f[i] = 1
a,b = LI()
g = gcd(a,b)
lst = make_divisors(g)
ans = 1
for i in lst:
    if f[i] == 1:
        ans += 1
print(ans)

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 b%a == 0:
    ans += 1
    

print(ans)

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

c = 1

for item in t:
    if a % item == 0:
        c += 1

print(c)

Submission status: Wrong Answer

Solution code:
import fractions
import math
A, B = map(int, input().split())
GCD = fractions.gcd(A, B)
def eratosthenes(limit):
  E = [1] * (limit + 1)
  E[0], E[1] = 0, 0
  prime_table = []
  for i, e in enumerate(E):
    if e == 0:
      continue
    prime_table.append(i)
    for j in range(i, limit + 1, i):
      E[j] = 0
  return prime_table
E = eratosthenes(int(math.sqrt(GCD)))
print(len([e for e in E if GCD % e == 0]) + 1)

Submission status: Wrong Answer

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


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

count = 0
for i in range(2, n):
    if n % i == 0:
        while n % i == 0:
            n = n // i
        count += 1
    if i > n:
        break

print(count or 1)

Submission status: Wrong Answer

Solution code:
def gcd(x,y):
    if x<y:
        x,y = y,x
    while y>0:
        x,y = y,x%y
    return x
INFTY = 10**6
P = [1 for i in range(INFTY+1)]
P[0] = 0
P[1] = 0
for i in range(2,int((INFTY+1)**0.5)+1):
    for j in range(i*i,INFTY+1,i):
        P[j] = 0
Q = []
for i in range(INFTY):
    if P[i]==1:
        Q.append(i)
A,B = map(int,input().split())
x = gcd(A,B)
cnt = 1
for y in Q:
    if x%y==0:
        cnt += 1
print(cnt)

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

c = 0

for item in t:
    if a % item == 0:
        c += 1

print(c)