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: Runtime Error

Solution code:
#D
import math

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

kouyaku = math.gcd(a, b)
#ruto = round(math.sqrt(kouyaku))
ans = 1

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

for i in pn:
    if kouyaku % i == 0:
        ans += 1
print(ans)

Submission status: Runtime Error

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:
  status = True
  if j == 2 or j == 3:
    result.append(2)
    continue
  if j % 2 != 0 or j%3 != 0: 
    for k in range(j):
      if j%k == 0:
        status = False
        break
      
    if status :
      result.append(j)
  
  
print(len(result))

Submission status: Runtime Error

Solution code:
# coding: utf-8

def greatest_common_divisor(a, b):
    assert a > b
    while b != 0:
        a, b = b, a%b
    return a

def main():
    a, b = input().split()
    a, b = int(a), int(b)

    if b > a:
        a, b = b, a

    relative_primes = []
    gcd = greatest_common_divisor(a, b)
    for i in range(2, gcd+1):
        if gcd % i > 0:
            continue
            
        flg = True
        for rp in relative_primes:
            if i % rp == 0:
                flg = False
                continue
        if flg:
            relative_primes.append(i)
    print(len(relative_primes)+1)
    

main()

Submission status: Runtime Error

Solution code:
import math
from fractions import gcd
def get_primenumber(number):
    prime_list = []
    search_list = list(range(2,number+1))
    while True:
        if search_list[0] > math.sqrt(number):
            prime_list.extend(search_list)
            break
        else:
            head_num = search_list[0]
            prime_list.append(head_num)
            search_list.pop(0)
            search_list = [num for num in search_list if num % head_num != 0]
    return prime_list

A, B = map(int, input().split())
g = gcd(A, B)
if g==1:
    print(1)
else:
    pn = get_primenumber(int(math.sqrt(g)))
    print(len(pn))

Submission status: Runtime Error

Solution code:
# 2019/09/28
from fractions import gcd

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


# 約数列挙

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

diva=divisors(a)
divb=divisors(b)
div=set()
for aa,bb in zip(diva,divb):
    if aa in divb:
        div.add(aa)
    if bb in diva:
        div.add(bb)

# エラトステネスの篩
def sieve(n):
    end=int(pow(n,0.5))+1
    is_prime=[True]*(n+1) 
    is_prime[0]=False
    is_prime[1]=False

    for i in range(2,end):
        if not is_prime[i]:continue
        for j in range(i*2,n+1,i):
        #for j in range(i*(i|0),n+1,i):
            is_prime[j]=False
    return [i for i in range(n+1) if is_prime[i]]

prime=sieve(max(div))

cnt=1
res=[]
for e in div:
    if e in prime:
        res.append(e)


cnt+=len(res)
for i in div:
    if i==1:continue
    for j in res:
        if j==1:continue
        if i==j:continue
        if i in res and j in res:continue
        if gcd(i,j)==1:continue
        else:break
        cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
import numpy as np

#A, B = (int(i) for i in input().split())

A , B = 420, 660
d = []
#print(A, B)

if A > B:
    A_arr = np.array([A] * B)
    B_arr = np.array([B] * B)
    arr = np.arange(1, B + 1)
else:
    A_arr = np.array([A] * A)
    B_arr = np.array([B] * A)
    arr = np.arange(1, A + 1)

(A_arr % arr == 0) * (B_arr % arr == 0)

gcds = np.nonzero((A_arr % arr == 0) * (B_arr % arr == 0))

ret = set()

for i in gcds:
    for j in gcds:
        if np.gcd(i, j) == 1:
            ret.add(j)
    
print(len(ret))

Submission status: Runtime Error

Solution code:
from math import sqrt, ceil, gcd
def cf(x1,x2):
    cf=[1]
    x=era_prime(min(x1,x2)+1)
    for i in x:
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf


def era_prime(N):
    temp = [True]*(N+1)
    temp[0] = temp[1] = False
    for i in range(2, ceil(sqrt(N+1))):
        if temp[i]:
            temp[i+i::i] = [False]*(len(temp[i+i::i]))                            
    primes = [ n for n in range(N+1) if temp[n] ]
    return primes

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

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 resolve():
    a,b=map(int,input().split())
    g=cf(a,b)
    G=gcd(a,b)
    ax=make_divisors(G)
#    print(g)
#    g=make_divisors(a,b)
#    print(g)
    ans=1
    for h in ax:
        if is_prime(h):
            ans+=1
    print(ans)
resolve()

Submission status: Runtime Error

Solution code:
'''
Created on 2019/09/28

@author: oiwaiman
'''

import math
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

gcd_ab = factorization(math.gcd(A, B))
cnt = 0
for i in gcd_ab:
    cnt+=1

print(cnt+1)