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

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

lst = []
for i in range(1,math.gcd(A, B)+1):
    if A % i == 0 and B % i == 0:
        lst.append(i)

if len(lst) == 1:
    print(1)
else:
    check = [lst[1]]
    for i in range(1, len(lst)):
        for c in check:
            if lst[i] % c == 0:
                break
        else:
            check.append(lst[i])
    print(len(check)+1)

Submission status: Runtime Error

Solution code:
#%%

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

#%%

from fractions import gcd


#%%
n = gcd(a, b)

#%%

vv = set([i for i in range(1, int(n // 2) + 1) if n % i == 0])

def get_prime_and_1_list(N):
    l = [i for i in range(2, N + 1)]
    p = [1]
    while l[0] <= int(N ** 0.5):
        p.append(l[0])
        t = l[0]
        l = [i for i in l if i % t != 0]

    p.extend(l)
    
    return p

p = set(get_prime_and_1_list(n))

print(len(vv & p))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

import sympy as sym
import itertools

def cf(x1,x2):
    cf=[]
    for i in range(1,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

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

    li = cf(a,b)
    out = []
    for v in itertools.combinations(li, 2):
        if v[0] in out:
            continue
        elif v[1] in out:
            continue
        elif sym.gcd(v[0], v[1]) != 1:
            out.append(max(v[0], v[1]))

    print(len(li) - len(out))




if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math
A,B = map(int, raw_input().split())
m = int(math.sqrt(min(A, B)) +100)

ans = 0
disjoints = [True]*m
for n in range(1, m):
    if A%n == 0 and B%n == 0:
        if disjoints[n]:
            ans += 1
            if n > 1:
                for i in range(n, m+1, n):
                    disjoints[i] = False
if ans == 0:
    ans = 1
print(ans)

Submission status: Runtime Error

Solution code:
N = list(map(int, input().split()))
if N[0] == 1 or N[1] == 1:
  print(1)
elif N[0] > 1 or N[1] > 1:
  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 or j == 5 or j == 7:
      result.append(j)
      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))
else:
  print()

Submission status: Runtime Error

Solution code:
input = raw_input

def isprime(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(" "))

a = []
for i in range(1,int(math.sqrt(A))+1):
    if A % i == 0:
        a.append(i)
        if i != A / i:
            a.append(A/i)

b = []
for i in range(1,int(math.sqrt(B))+1):
    if B % i == 0:
        b.append(i)
        if i != B / i:
            b.append(B/i)
c = 0
for i in a:
    if i in b and isprime(i):
        c += 1
print(c)

Submission status: Runtime Error

Solution code:
A, B = map(int, input().split())
def primes(n):
    ass = []
    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
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass


prime_list = primes(min(A, B))
ans = 1
print(1)

Submission status: Runtime Error

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    ass.sort()
    return ass

def main():
    """ main """
    A,B = map(int, input().split())
    ds = divisor(gcd(A,B))
    if len(ds) == 1:
        print(1)
        return 0
    ds = ds[1:]
    dp = [1]*len(ds)
    for i in range(len(ds)):
        if dp[i]:
            for j in range(i+1,len(ds)):
                if ds[j]%ds[i] == 0:
                    dp[j] = 0
    ans = 1
    for d in dp:
        if d == 1: ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from math import gcd, sqrt


def is_prime(n):
    flag = True
    for k in range(2, int(sqrt(n)) + 1):
        if n % k == 0:
            flag = False
            return

    if flag:
        return n


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 main():
    a, b = map(int, input().split())
    coms = make_divisors(gcd(a, b))
    # print(coms)
    ans = [is_prime(i) for i in coms]
    # print(ans)
    ans2 = [a for a in ans if a is not None]
    print(ans2)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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
    table = list(set(table))
    return table
"""
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
"""

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


a_L = divisor(a)
b_L = divisor(b)

kouyaku = set(a_L) & set(b_L)

new_L = []


for val in kouyaku:
    if is_prime(val):
        new_L.append(val)


new_L.append(1)


import itertools
import math 

counter =0

v = itertools.combinations(list(new_L),2)


for i in v:

    if math.gcd(i[0], i[1]) == 1:
        print(i[0],i[1])
        counter +=1
#print(counter)

print(len(new_L))

Submission status: Runtime Error

Solution code:
from sympy import isprime
A,B = map(int,input().split())
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
result = cf(A,B)
res = 1
for i in result:
  a=isprime(i)
  if a==True:
    res += 1
print(res)