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: Time Limit Exceeded

Solution code:
import random


A, B = [int(str) for str in input().split()]

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

def is_prime(q,k=2):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし(但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        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

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


prime_list = [1] + [i for i in range(1, gcd(A, B) + 1) if is_prime(i)]
print(len([i for i in prime_list if A % i == 0 and B % i == 0]))

Submission status: Time Limit Exceeded

Solution code:
a,b = map(int, input().split())
def cf(x1,x2):
    cf=[]
    for i in range(3,x1+1,2):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

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

def coprime(a, b):
    return gcd(a, b) == 1
  
num = cf(a,b)

num_2 = [1,2]
num_2.extend(num)

if len(num_2) == 2:
    print(1)
else:
    ans_num = []
    m_n = len(num_2)
    for i in range(m_n):
        if i == m_n:
            break
        else:
            for j in range(i+1,m_n):
                if coprime(num_2[i],num_2[j]):
                    ans_num.append(num_2[i])
                    ans_num.append(num_2[j])
                else:
                    ans_num.remove(num_2[j])
    print(len(set(ans_num)))

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
m,n = map(int,input().split())
# div = [0]
div = [1]
flg = 0

if m % 2 == 0 and n % 2 == 0:
    div.append(2)

# while i < 0:
    # if m 
for i in range(3,m,2):
    if m % i == 0 and n % i == 0 and i % 2 == 1:
        # ans += 1
        # m = m / i
        # n = n / i
        for j in range(1,len(div)):
            if i % div[j] == 0:
                flg = 1
                break
        if flg == 0:
            div.append(i)
        else:
            flg = 1
    

    # print(student[i]-1)
    # toukou[student[i]-1] = i+1
# print(" ".join(map(str,div)))
print(len(div))

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
kouyakusu = [i+1 for i in range(N) if (N%(i+1) == 0) and (M%(i+1) == 0)]
count = 1

def gcd(a, b):
  while b > 0:
    mod = a % b
    a = b
    b = mod
  if a == 1:
    return True
  else:
    return False
res = 0 
nk = len(kouyakusu)
for i in range(2 ** nk):
  value = []
  for j in range(nk):
    if((i >> j) & 1):
      value.append(kouyakusu[j])
  fault = False
  if res < len(value):
    for v1 in value:
      if fault == True:
        break
      for v2 in value:
        if v1 > v2:
          if gcd(v1, v2) == False:
            fault = True
            break
    if fault == False:
      res = len(value)
print(res)

Submission status: Time Limit Exceeded

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[n] = 1
            return primes

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

            primes.setdefault(factor, 0)
            primes[factor] += 1

            n //= factor

        return primes


prime = Prime()

#import numpy as np

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

prime_a = list(prime.find_factors(a).keys())
prime_b = list(prime.find_factors(b).keys())
#pa = np.array(prime_a)
#pb = np.array(prime_b)

#print(pa, pb)

print(1+len(set(prime_a)&set(prime_b)))
#print(1 + np.intersect1d(pa, pb).size)

Submission status: Time Limit Exceeded

Solution code:
a, b = map(int, input().split())
def primes(n):
  if n >= 2:
    prime_nums = [2]
    for i in range(3, n + 1):
      for p in prime_nums:
        if i % p == 0:
          break
      else:
        prime_nums.append(i)
  return prime_nums
if a == 1 or b == 1:
  print(1)
else:
  Z = primes(max(a, b))
  ans = 1
  for i in range(len(Z)):
    if a%Z[i] == b%Z[i] == 0:
      ans += 1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

a,b=map(int,input().split())
e=euclid(a,b)
#print("gcm",e)
l=primes(e+1)
#print("primes",l)
ans=1
for i in l:
  if e<i:
    break
  if e%i==0:
    #print("i",i)
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
aa, bb = map(int, input().split())
A = max(aa, bb)
B = min(aa, bb)


def get_max(a, b):
    while True:
        c = a % b
        if c == 0:
            return b
        a = b
        b = c


B = get_max(A, B)

temp = []
for i in range(1, B + 1):
    if B % i == 0:
        temp.append(i)

flag = [0] * len(temp)
count = len(temp)
for i in range(0, len(temp)):
    for j in range(i + 1, len(temp)):
        if flag[j] == 0:
            max_ = get_max(temp[i], temp[j])
            if max_ != 1:
                flag[j] = 1
                count -= 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

from collections import deque

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
    
A, B = map(int,input().split())
array = deque(sorted(cf(A, B)))
A = []
tmp = 0

for i in range(len(array)):
    tmp = array.popleft()
    if tmp != 0:
        array = deque(list(filter(lambda x: x % tmp != 0, array)))
        A.append(tmp)
    if array == deque([]):
        break
print(len(A) + 1)

Submission status: Time Limit Exceeded

Solution code:
import math

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

AB_divs = cf(A, B)

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

primes = []

for v in AB_divs:
    if is_prime(v):
        primes.append(v)

primes.insert(0, 1)
print(len(primes))

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

A, B = map(int, input().split())
lst = len(cf(A,B))

print(lst)

Submission status: Time Limit Exceeded

Solution code:
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

a, b = map(int, input().split())
ab = cf(a, b)
i = 0
for ab_i in ab:
    for ab_j in ab[i+1:]:
        if ab_j%ab_i==0:
            for k, ab_k in enumerate(ab):
                if ab_k == ab_j:
                    del ab[k]
    i += 1
print(len(ab)+1)

Submission status: Time Limit Exceeded

Solution code:
import math
def is_prime(n):
    if n == 1: return False
    # 2以外の偶数は素数ではないので無視する
    if n != 2:
        if n % 2 == 0:
            return False
    # 3以外の偶数は素数ではないので無視する
    if n != 3:
        if n % 3 == 0:
            return False
    # 5以外の偶数は素数ではないので無視する
    if n != 5:
        if n % 5 == 0:
            return False
    # 7以外の偶数は素数ではないので無視する
    if n != 7:
        if n % 7 == 0:
            return False
    # 11以外の偶数は素数ではないので無視する
    if n != 11:
        if n % 11 == 0:
            return False
            
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

a, b = map(int, input().split())
count = 1
for i in range(2,min(a,b)+1):
    if a % i == 0 and b % i == 0:
        if is_prime(i) == True:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import fractions
s = input().split()
a = int(s[0])
b = int(s[1])
c = fractions.gcd(a, b)
d = 1
for i in range(2, c+1):
  if c % i == 0:
    while c % i == 0:
      c = c / i
    d = d + 1
print(d)

Submission status: Time Limit Exceeded

Solution code:
temp = list(map(int, input().split()))
A = temp[0]
B = temp[1]
if(A>B):
  temp = A
  A = B
  B = temp
#これで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)

    divisors.sort()
    return divisors
  
def judge(n):
  ans = 0
  for i in range(2, n):
    if(n%i==0):
      ans = 1
      break
  return ans

a = make_divisors(A)
b = make_divisors(B)
con = []
if(A==B):
  con = a
else:
  amax = max(a)
  bmax = max(b)
  while(a[0]!=amax and b[0]!=bmax):
    if(a[0]==b[0]):
      con.append(a[0])
      a.pop(0)
      b.pop(0)
    else:
      if(a[0]>b[0]):
        b.pop(0)
      else:
        a.pop(0)
count = 0
for i in range(len(con)):
  if(judge(con[i])==0):
    count += 1
if(A==1):
  print(1)
else:
  print(count)

Submission status: Time Limit Exceeded

Solution code:
a,b = map(int,input().split())
if min(a,b) <=2:
    if max(a,b) % 2 !=0:
        print(1)
        exit()
    else:
        print(2)
        exit()

comm = [1,2]
end = int(((max(a,b)) + 1)/2) + 1
if end >= min(a,b):
    end = min(a,b)+1

for i in range(3,end,2):
    if a % i ==0 and b % i == 0:
        flag1 = True
        for j in comm[1:]:
            if i % j == 0:
                flag1 = False
                break
        if flag1:
            comm.append(i)

print(len(comm))

Submission status: Time Limit Exceeded

Solution code:
def is_prime(n, cf):
    for i in cf:
        if i * i > n:
            return 1  # False
        if n % i == 0:
            return 0  # True
    else:
        return 1


def cf(a, b):
    return [i for i in range(2, (min(a, b)) + 1) if a % i == 0 and b % i == 0]


a, b = map(int, input().split())
# a, b = 12, 18
data = cf(a, b)
ans = 0
for n in data:
    ans += is_prime(n, data)
print(ans + 1)
# def sieve(n):
#     is_prime = list(repeat(True, len(n)))
#     prime = []
#     p = 0
#     for i in range(len(n)):
#         if is_prime[i]:
#             p += 1
#             prime.append(n[i])
#             for j in range(2 * n[i], n, i):
#                 is_prime[j] = False
#     return p, prime

# def sieve(n):
#     is_prime = list(repeat(True, n))
#     prime = []
#     p = 0
#     for i in range(2, n):
#         if is_prime[i]:
#             p += 1
#             prime.append(i)
#             for j in range(2 * i, n, i):
#                 is_prime[j] = False
#     return p, prime

# print(sieve(n))
# print(sieve(10000))

Submission status: Time Limit Exceeded

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

#numには入力値の大きいほうの数字が入る
num = (min(A,B))
primeNum=[]
j=result=0
for i in range(2,num):
  flag=False  
  for j in range(2,i):
    if i%j==0:
      flag=True
      break
  #素数だったら
  if flag==False:
    # primeNum.append(i)
    while A % i == 0 and B % i == 0:
      A = A // i
      B = B // i
      flag=True
    j+=1
    if flag==True:
      result+=1

    if min(A,B)<i:
      break  


# print("jikankeisoku")

# #primeNumにはmax(A,B)までの素数が入っている。素因数分解に使用する。
# resultNum=[0]*len(primeNum)
# result=1


# j=0
# result=0
# for i in primeNum:
#   flag=False
#   while A % i == 0 and B % i == 0:
#     A = A // i
#     B = B // i
#     resultNum[j]+=1
#     flag=True
#   j+=1
#   if flag==True:
#     result+=1

#   if min(A,B)<i:
#     break  
# # print(resultNum)
print(result+1)

Submission status: Time Limit Exceeded

Solution code:
a,b = map(int,input().split())
import math 
import fractions
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

#ユークリッドの互除法
gc = fractions.gcd(a,b)
if gc == 1:
	print(1)
	exit()

list1 = [1]
cout = 0 #1がfalse判定される
for i in range(2,gc+1):
	if is_prime(i):
		list1.append(i)
for i in range(len(list1)):
	if a % list1[i] == 0 and b % list1[i] == 0:
		cout += 1

"""
for i in range(1,gc+1):
	if a % i == 0 and b % i == 0:
		if is_prime(i):
			cout+= 1
"""
print(cout)

Submission status: Time Limit Exceeded

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

def is_prime(n):
    for i in range(2, n):  
        if n % i == 0:
            return False
    return True
  
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


gcd = fractions.gcd(A, B)
divisors = make_divisors(gcd)
count = 0
for i in divisors:
  count += is_prime(i)
print(count)

Submission status: Time Limit Exceeded

Solution code:
#公約数を求める
def cf(x1,x2):
    cf=[1]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

a, b = map(int, input().split())
li = cf(a,b)
li.sort(reverse=True)
end=0
j=0
for i in li:
    for j in range(2,i):
        if i%j!=0:
            break
    if j==i-1:
        print(i)
        break

Submission status: Time Limit Exceeded

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

prime = Prime()

a, b = map(int, input().split())
primes = prime.find_factors(prime.gcd(a, b))

print(len(set(primes)) + 1)

Submission status: Time Limit Exceeded

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

#numには入力値の大きいほうの数字が入る
num = (max(A,B))
primeNum=[]
j=result=0
for i in range(2,num):
  flag=False  
  for j in range(2,i):
    if i%j==0:
      flag=True
      break
  #素数だったら
  if flag==False:
    # primeNum.append(i)
    while A % i == 0 and B % i == 0:
      A = A // i
      B = B // i
      flag=True
    j+=1
    if flag==True:
      result+=1

    if min(A,B)<i:
      break  


# print("jikankeisoku")

# #primeNumにはmax(A,B)までの素数が入っている。素因数分解に使用する。
# resultNum=[0]*len(primeNum)
# result=1


# j=0
# result=0
# for i in primeNum:
#   flag=False
#   while A % i == 0 and B % i == 0:
#     A = A // i
#     B = B // i
#     resultNum[j]+=1
#     flag=True
#   j+=1
#   if flag==True:
#     result+=1

#   if min(A,B)<i:
#     break  
# # print(resultNum)
print(result+1)

Submission status: Time Limit Exceeded

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)
# print(a)
ans = 1
for aa in a:
    if b % aa == 0 and aa != 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(int(1e6))

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

import math
def seachPrimeNum(N):
    max = int(math.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

min_v = min(A, B)
if min_v < 2:
    primes = list()
else:
    primes = seachPrimeNum(min(A,B))

prime_factors_count = 0
for f in primes:
    if A % f:
        pass
    elif B % f:
        pass
    else:
        prime_factors_count += 1

print(prime_factors_count + 1)

Submission status: Time Limit Exceeded

Solution code:
import math 

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

def sieve_of_eratosthenes(n): 
    candidate = [i for i in range(2, n+1)] 
    prime = []
    limit = math.sqrt(n) + 1 

    while True:
        p = min(candidate) 
        if limit <= p:
            prime.extend(candidate) 
            break
        prime.append(p) 

        candidate = [i for i in candidate if i % p != 0]

    return prime

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]

yakumax = max(yakusu)
if yakumax == 1:
	prime = [1]
elif yakumax == 2:
  prime = [1, 2]
else:
  prime = sieve_of_eratosthenes(yakumax)
  prime.append(1)

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import itertools
import math

a,b = [int(x) for x in stdin.readline().rstrip().split()]

def isPrime(n):
  if n < 2:
    return False
  if n == 2:
    return True
  for p in range(2, n):
      if n % p == 0:
        return False
  return True

if a == 1:
    print(1)
    exit()

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

li2 = list(itertools.combinations(cf(a,b),2))
flat = [flatten for inner in li2 for flatten in inner]
print(len(list(set(flat))))

Submission status: Time Limit Exceeded

Solution code:
# D - Disjoint Set of Common Divisors
A, B = map(int, input().split())

d = min(A, B)//2
#print(d)
tmp = 0
DP =[1]
for i in range(2,d+1):
    if A % i == 0 and B % i == 0:
        if len(DP) == 1:
            DP.append(i)
        else:
            for j in range(1,len(DP)):
                if i % DP[j] == 0:
                    tmp = 0
                    break
                else:
                    tmp = 1
            if tmp == 1:
                DP.append(i)

    else:
        pass

print(len(DP))

Submission status: Time Limit Exceeded

Solution code:
import fractions
a, b = map(int, input().split())
gcd = fractions.gcd(a, b)
memorizedMax = 1
primes = [ 1 ]
for i in range(2, int(gcd) + 1):
    if gcd % i == 0:
        isPrime = True
        for j in range(2, int(i**0.5) + 1):
            if i % j == 0:
                isPrime = False
                break
        if isPrime:
            primes.append(i)
print(len(primes))

Submission status: Time Limit Exceeded

Solution code:
a, b = map(int, input().split())
divisor = []
upper = min(a, b)//2+1
if a%2 and b%2:
    for i in range(3, upper, 2):
        divable = False
        if a % i == 0 and b % i == 0:
            for j in range(len(divisor)):
                if i % divisor[j] == 0:
                    divable = True
                    break
            if not divable:
                divisor.append(i)
else:
    for i in range(2, upper):
        divable = False
        if a % i == 0 and b % i == 0:
            for j in range(len(divisor)):
                if i % divisor[j] == 0:
                    divable = True
                    break
            if not divable:
                divisor.append(i)
print(len(divisor)+1)

Submission status: Time Limit Exceeded

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

import math
from fractions import gcd

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

# 最大公約数
g = gcd(A, B)

if g == 1:
    print(1)
    exit()


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

prime = get_sieve_of_eratosthenes(g)

a = []
count = 0
for p in prime:
    if A%p == 0 and B%p == 0:
        count += 1

print(count+1)

Submission status: Time Limit Exceeded

Solution code:
#import sys

#input = sys.stdin.readline

import heapq

def main():
#    h,w,a,b = map(int, input().split())
    a,b=map(int,input().split())
    m=2
    k=1
    c=max(a,b)
    count=1
    sosu=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
    for i in range(len(sosu)):
        if a%sosu[i]==0 and b%sosu[i]==0:
            count+=1
            a//=sosu[i]
            b//=sosu[i]

    while m < c:
        m = 6 * k +1
        if a % m == 0 and b % m == 0:
            count += 1
        k += 1
    k = 1
    m = 2
    while m < c:
        m = 6 * k -1
        if a % m == 0 and b % m == 0:
            count += 1
        k += 1
    print(count)
#    for i in range(h):
#            print(aaa)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

count = 1
div = 3
if a % 2 == 0 and b % 2 == 0:
    count += 1
while a % 2 == 0:
    a //= 2
while b % 2 == 0:
    b //= 2
if a < b:
    a, b = b, a
while b > 1:
    if a % div == 0 and b % div == 0:
        count += 1
    while a % div == 0:
        a //= div
    while b % div == 0:
        b //= div
    div += 2
    if a < b:
        a, b = b, a

print(count)

Submission status: Time Limit Exceeded

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

def make_divisors(a,b):
    ans = 1
    i = 2
    m = []
    while i <= min(A,B):
    #for i in range(1, int(min(a,b)**0.5)+1):
        if a%i == 0 and b%i == 0:
            ans += 1
            m.append(i)
        i += 1
        while i <= min(A,B):
            for mi in m:
                if i%mi == 0:
                    i += 1
                else:
                    break
            else:
                continue
            break
            #if i != n // i:
                #divisors.append(n//i)
    return ans

print(make_divisors(A,B))