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 main():
    x,y = map(int,input().split())
    tmp = []
    for i in range(2,max(2,min(int(x ** 0.5)+1, int(y ** 0.5 )+1))):
        if x % i ==0 and y % i == 0:
            tmp.append(i)
            while True:
                if x % i == 0:
                    x = x//i
                else:
                    break
            while True:
                if y % i == 0:
                    y = y//i
                else:
                    break


    print(len(tmp) + 1)
    # print(tmp)
    # for i,a in enumerate(tmp):
    #     if a < 4:
    #         tmp[i] = 1
    #         continue
    #     j = 2
    #     for j in range(2,int(a**0.5)+1):
    #         if a % j == 0:
    #             tmp[i] = 0
    #             break
    #     if tmp[i] != 0:
    #         tmp[i] = 1
    # print(sum(tmp))
    # print(tmp)

    # cnt = 0
    # # print(tmp)
    # flg = 0
    # for i,a in enumerate(tmp):
    #     # print('out' + str(i) + ' ' + str(a))
    #     if a == 1:
    #         continue
    #     leng = len(tmp)
    #     for j in range(i+1,leng):
    #         # print(j)
    #         # print(tmp)
    #         # print(leng)
    #         if flg == 1:
    #             j -=1
    #         flg = 0
    #         if j >= leng:
    #             break
    #         # print(str(j) + ' ' + str(leng) + ' ' + str(tmp[j]))
    #         if tmp[j] % a == 0:
    #             tmp.pop(j)
    #             leng -=1
    #             j -= 1
    #             # print(tmp)
    #             # print(j)
    #             flg = 1
    #
    #                 # print(j)
    #                 # print(a)
    #

    # print(len(tmp))
    # print(tmp)
if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

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

bb = int((b ** 0.5) // 1)

ans = 1
for i in range(2,bb+1):
    if a % i == 0 and b % i == 0:
        ii = int((i ** 0.5) // 1)
        s = 1
        for j in range(2, ii+1):
            if i % j == 0:
                s = 0
                break
        if s == 1:
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
# ABC-142-D
A, B = map(int, input().split())
ans = 1

#最大公約数
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

def factorize(x):
    factor = []
    for num in range(2, int(x**0.5)+1):
        while x % num == 0:
            x //= num
            factor.append(num)
        if x != 1:
            factor.append(x)
    return set(factor)
    
gcd_AB = gcd(A, B)
prime = factorize(gcd_AB)
ans += len(prime)
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from math import sqrt
a,b = map(int, input().split())
xa,xb = a,b

sa = set([1])
i = 2
while a>1:
    if i>sqrt(xa):
        sa.add(a)
        break
    while a%i==0:
        sa.add(i)
        a //= i
    i += 1

sb = set([1])
i = 2
while b>1 and i<int(sqrt(xb))+1:
    if i>sqrt(xb):
        sb.add(b)
        break
    while b%i==0:
        sb.add(i)
        b //= i
    i += 1

print(len(sa & sb))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from math import sqrt
a,b = map(int, input().split())
xa,xb = a,b

sa = set([1])
i = 2
while a>1:
    if i>sqrt(xa):
        sa.add(i)
        break
    while a%i==0:
        sa.add(i)
        a //= i
    i += 1

sb = set([1])
i = 2
while b>1 and i<int(sqrt(xb))+1:
    if i>sqrt(xb):
        sb.add(i)
        break
    while b%i==0:
        sb.add(i)
        b //= i
    i += 1

print(len(sa & sb))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from math import sqrt
a,b = map(int, input().split())
xa,xb = a,b

sa = set([1])
i = 2
while a>1 and i<int(sqrt(xa))+1:
    while a%i==0:
        sa.add(i)
        a //= i
    i += 1

sb = set([1])
i = 2
while b>1 and i<int(sqrt(xb))+1:
    while b%i==0:
        sb.add(i)
        b //= i
    i += 1

print(len(sa & sb))

Submission status: Wrong Answer

Solution code:
A,B = map(int,input().split())
 
alist = set()
blist = set()
 
for i in range(2,int(A**0.5)+2):
    while A%i == 0:
        A = A//i
        alist.add(i)
alist.add(A)
 
for i in range(2,int(B**0.5)+2):
    while B%i == 0:
        B = B//i
        blist.add(i)
blist.add(B)

print(len(alist&blist)+1)

Submission status: Wrong Answer

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

#a,bの最大公約数
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

li = {1}
g = gcd(A,B)

for i in range(2,int(g**0.5)+100):
    while g%i == 0:
        g = g//i
        li.add(i)


print(len(li))

Submission status: Wrong Answer

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

#a,bの最大公約数
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

li = {1}
g = gcd(A,B)

for i in range(2,int(g**0.5)+1):
    while g%i == 0:
        g = g//i
        li.add(i)


print(len(li))

Submission status: Wrong Answer

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

alist = {1}
blist = {1}

for i in range(2,10**6+7):
    while A%i == 0:
        A = A//i
        alist.add(i)

for j in range(2,10**6+7):
    while B%j == 0:
        B = B//j
        blist.add(j) 

#print(alist,blist)

print(len(alist&blist))

Submission status: Wrong Answer

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

alist = set()
blist = set()

for i in range(2,10**6+7):
    while A%i == 0:
        A = A//i
        alist.add(i)

for j in range(2,10**6+7):
    while B%j == 0:
        B = B//j
        blist.add(j) 

print(len(alist&blist)+1)

Submission status: Wrong Answer

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

alist = set()
blist = set()

for i in range(2,int(A**0.5)+10):
    while A%i == 0:
        A = A//i
        alist.add(i)

for i in range(2,int(B**0.5)+10):
    while B%i == 0:
        B = B//i
        blist.add(i) 

#print(alist,blist)

print(len(alist&blist)+1)

Submission status: Wrong Answer

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

alist = set()
blist = set()

for i in range(2,int(A**0.5)+1):
    while A%i == 0:
        A = A//i
        alist.add(i)

for i in range(2,int(B**0.5)+1):
    while B%i == 0:
        B = B//i
        blist.add(i) 

#print(alist,blist)

print(len(alist&blist)+1)

Submission status: Wrong Answer

Solution code:
import fractions

  
def isprime(x):
    count = 1
    for i in range(2,int(x**0.5)+1):
        if x % i == 0:
            count += 1
            break
      
    return count

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



ans=1
for i in range(2,int(g**0.5)+1):
    if g % i == 0:
        if isprime(i) == 1:
            ans += 1
        if i != g//i:
            if isprime(g//i) == 1:
                ans += 1
       

print(ans)

Submission status: Wrong Answer

Solution code:
import fractions

  
def isprime(x):
    count = 1
    for i in range(2,int(x**0.5)+1):
        if x % i == 0:
            count += 1
      
    return count

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



ans=1
for i in range(2,int(g**0.5)+1):
    if g % i == 0:
        if isprime(i) == 1:
            ans += 1
        if i != g//i:
            if isprime(g//i) == 1:
                ans += 1
       

print(ans)

Submission status: Wrong Answer

Solution code:
import fractions
def getlist(x):
    l = []
    if x == 1:
    	return l
    else:
        for i in range(2,int(x**0.5)+1):
            if x % i == 0:
                l.append(i)
            
      
        return l
  
def isprime(x):
    count = 1
    for i in range(2,int(x**0.5)+1):
        if x % i == 0:
            count += 1
      
    return count

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

g1 = getlist(g)

ans=1
for i in g1:
    if isprime(i) == 1:
        ans+=1
       

print(ans)

Submission status: Wrong Answer

Solution code:
import fractions
def getlist(x):
    l = []
    
    for i in range(2,int(x**0.5)+2):
        if x % i == 0:
            l.append(i)
            while x%i == 0:
                x = x//i
      
    return l
  
def isprime(x):
    count = 1
    for i in range(2,x):
        if x % i == 0:
            count += 1
      
    return count

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

g1 = getlist(g)

ans=1
for i in g1:
    if isprime(i) == 1:
        ans+=1
       

print(ans)

Submission status: Wrong Answer

Solution code:
import fractions
def getlist(x):
    l = []
    
    for i in range(2,int(x**0.5)+2):
        if x % i == 0:
            l.append(i)
            while x%i == 0:
                x = x//i
      
    return l
  
def isprime(x):
    count = 1
    for i in range(2,int(x**0.5)+1):
        if x % i == 0:
            count += 1
      
    if count == 1:
        return True
    else:
        return False

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

g1 = getlist(g)

ans=1
for i in g1:
    if isprime(i):
        ans+=1
       

print(ans)

Submission status: Wrong Answer

Solution code:
def getlist(x):
    l = []
    
    for i in range(1,int(x**0.5)+1):
        if x % i == 0:
            l.append(i)
      
    return l
  
def isprime(x):
    count = 0
    for i in range(1,int(x**0.5)+1):
        if x % i == 0:
            count += 1
      
    if count == 1:
        return True
    else:
        return False

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

la = getlist(a)
lb = getlist(b)
l = []
for i in la:
    if i in lb:
        l.append(i)

ans=0
for i in l:
    if isprime(i):
        ans+=1
       

print(ans)

Submission status: Wrong Answer

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

def mygcd(a, b):
    if a < b:
        return mygcd(b, a)
    elif b == 0:
        return a
    else:
        return mygcd(b, a % b)

gcd = mygcd(A, B)

divdic = {}
gcd_tmp = gcd
for p in range(2, 10 ** 6 + 1):
    if gcd_tmp <= 1: break
    if gcd_tmp % p > 0: continue
    #
    for i_p in range(65):
        if gcd_tmp % p == 0:
            gcd_tmp //= p
        else:
            break
    #
    divdic[str(p)] = i_p

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

Submission status: Wrong Answer

Solution code:
def isprime(x):
  count = 0
  for i in range(1,int(x**0.5)+1):
    if x % i == 0:
      count += 1
      
  if count == 1:
    return True
  else:
    return False
  
a,b = map(int,input().split())
c = min(a,b)
l=[]
for i in range(1,int(c**0.5)+1):
  if a%i==0 and b%i==0:
    l.append(i)
    
ans=0
for i in l:
  if isprime(i):
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
def isprime(x):
  for i in range(1,int(x**0.5)+1):
    if x % i == 0:
      break
    
  return True
a,b = map(int,input().split())
c = min(a,b)
l=[]
for i in range(1,int(c**0.5)+1):
  if a%i==0 and b%i==0:
    l.append(i)
    
ans=0
for i in l:
  if isprime(i):
    ans+=1

print(ans)

Submission status: Wrong Answer

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

def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

A=prime_decomposition(a)
B=prime_decomposition(b)
ans=0
for i in A:
    if i in B:
        ans+=1

print(ans)