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:
#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 < m:
#     if m % i == 0 and n % i == 0 and i % 2 == 1:
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(2,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:
A, B = map(int, input().split())
N = [n for n in range(1, min(A//2, B//2)+1) if A%n == 0 and B%n==0]
J = [True for _ in range(len(N))]
M = [1]

for i in range(1, len(N)):
	if not J[i]:
		continue
	M.append(N[i])
	for j in range(i+1, len(N)):
		if N[j] % N[i] == 0:
			J[j] = False

print(len(M))

Submission status: Time Limit Exceeded

Solution code:
a,b=map(int,input().split())
Cdiv=[]
ans=[]
for i in range(1,min(a,b)+1):
    if a%i==0 and b%i==0:
        Cdiv.append(i)
for i in reversed(Cdiv):
    flag=0
    for j in range(2,i):
        if i%j==0:
            flag+=1
            break
    if flag==0:
        ans.append(i)

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

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 hogehoge(yakusu):
    is_ok = True
    m = len(yakusu)
    for i in range(m):
        c = yakusu[i]
        for j in range(i+1,m):
            d = yakusu[j]
            if len(cf(c,d)) > 1:
                is_ok = False            
    return is_ok

def hogehoge2(stuff):
    max_num = 1
    tmp_num = 1
    for L in range(2, len(stuff)+1):
        for subset in itertools.combinations(stuff, L):
            if len(subset) > tmp_num+1:
                return max_num

            #print(hogehoge(subset))
            if hogehoge(subset):
                max_num = len(subset)
                tmp_num = len(subset)
    return max_num
            

yakusu = cf(a,b)
max_num = hogehoge2(yakusu)
print(max_num)

Submission status: Time Limit Exceeded

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

cf=[]
for i in range(1,min(A,B)+1):
  if A % i == 0 and B % i == 0:
    cf.append(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
    
cnt = 0
for i in range(len(cf)):
  if is_prime(cf[i]) == True:
    cnt += 1

print(cnt+1)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
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 = [x for x in stdin.readline().rstrip().split()]
A = int(A)
B = int(B)
k = cf(A, B)
# print(k)
ans = []
flg = 0
idx = 0
for i in k[::-1]:
    idx = idx + 1
    for l in k[-idx::-1]:
        if i != l:
            # print(i, l)
            # print(len(cf(l,i)))
            if len(cf(l, i)) != 0:
                flg = flg + 1
                break
    if flg == 0:
        ans.append(i)
    flg = 0
# print(ans)
print(len(ans)+1)

Submission status: Time Limit Exceeded

Solution code:
import math

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

def func(n):
    num=1
    for i in range(2,int(math.sqrt(n) + 1e-9) +3):
        if n%i==0 and n!=i:
            num=0
            break
        else:
            continue
    return num

p=min(A,B)
q=max(A,B)

ans=0
for i in range(1, p+1):
    if p%i==0 and q%i==0:
        ans+=func(i)
        
print(ans)

Submission status: Time Limit Exceeded

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

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

result = 1
i = 2
while i <= g:
    if g%i == 0:
        while g%i == 0:
            g//=i
        result += 1
    i += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
kouyakusu = [i+1 for i in range(max(N,M)) 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)
hoge = {}
for v1 in kouyakusu:
  for v2 in kouyakusu:
    if v1 > v2:
      hoge[(v1,v2)] = gcd(v1,v2)

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 hoge[(v1, v2)] == False:
            fault = True
            break
    if fault == False:
      res = len(value)
print(res)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import heapq

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 = cf(A, B)
heapq.heapify(array)
A = []
tmp = 0

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

Submission status: Time Limit Exceeded

Solution code:
import random

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

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

    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        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
 
a, b = map(int,input().split())
 
c = 1
m = gcd(a,b)
for i in range(1,m+1):
	if a % i == 0 and b % i == 0:
		if is_prime(i):
			c+=1
print(c)

Submission status: Time Limit Exceeded

Solution code:
a, b = map(int, input().split())
divisor = []
upper = min(a, b)//2+1
if a%2 or 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:
    two_break = False
    for i in range(2, upper):
        divable = False
        if a % i == 0 and b % i == 0:
            if i % 2 == 0 and two_break:
                continue
            for j in range(len(divisor)):
                if i % divisor[j] == 0:
                    divable = True
                    break
            if not divable:
                divisor.append(i)
                if i == 2:
                    two_break = True
print(len(divisor)+1)

Submission status: Time Limit Exceeded

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

import fractions
gcd = fractions.gcd(A, B)

n = 2
count = 1
gcdmax = gcd
ar = [1]
notappend = False
while n <= gcdmax:
    if gcd % n == 0:
        #print("matched {} under {}".format(n, gcdmax))
        for aar in ar[1:]:
            if n % aar == 0:
                notappend = True
                break
        if notappend == False:
            ar.append(n)
            count += 1
        notappend = False
        gcdmax = gcd // n
    n += 1

#print(ar)
print(count)

Submission status: Time Limit Exceeded

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 result:
        if j%k == 0:
          status = False
          break
      
      if status :
        result.append(j)
  print(len(result))
else:
  print()

Submission status: Time Limit Exceeded

Solution code:
'''連徐法を利用した別バージョン'''
A,B = map(int, input().split())

M = max(A,B)//2
# print(M)
CoP = set([1])

for i in range(1,M):
    Co_flg = 1
#     print(i+1, A % (i+1), B % (i+1))
    while Co_flg:
        
        if A % (i+1) == 0 and B % (i+1) == 0:
            CoP.add(i+1)
            A = A /(i+1)
            B = B /(i+1)
#             print(A,B)
        else:
            Co_flg = 0

# print(CoP)
print(len(CoP))

Submission status: Time Limit Exceeded

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

l = []
for i in range(n//2):
    if a % (i+2) == 0 and b % (i +2) == 0:
        l.append(i+2)

if a % n == 0 and b % n == 0 and n != 1:
    l.append(n)
    
primes = [2]
for x in l:
    if all(x % prime !=0 for prime in primes):
        primes.append(x)

if  a % 2 == 0 or b % 2 == 0:
    ans = len(primes) +1
else:
    ans = len(primes)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

lst = []
for i in range(1,fractions.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: Time Limit Exceeded

Solution code:
a, b = map(int, input().split())
g = []
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b, a%b)
g.append(gcd(a,b))
g.append(1)
j = 1
for i in range(2,g[0]):
    if not a%i and not b%i:
        c = True
        for k in range(1, len(g)):
            if gcd(g[k],i)!=1:
                c = False
                break
        if c:
            g.append(i)
c = True
for i in range(1, len(g)):
    if gcd(g[0],g[i])!=1:
        c = False
        break
if c and g[0] != 1:
    print(len(g))
else:
    print(len(g)-1)

Submission status: Time Limit Exceeded

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

temp = fractions.gcd(a, b)

c = []
for i in range(1, temp+1):
    if a%i==0 and b%i==0:
        c.append(i)
c = set(c)

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]]

d = set(primes(temp))

ans = c&d
        
print(len(ans)+1)

Submission status: Time Limit Exceeded

Solution code:
def gcd(x, y):
  if y == 0:
    return x
  else:
    return gcd(y, x % y) 

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 isPrime(n):
  if n <= 2:
    return True
  for p in range(2, n):
      if n % p == 0:
        return False
  return True
    
a,b = map(int,input().split())
gcd = gcd(a,b)
yks = make_divisors(gcd)
ans = 0
for i in yks:
  if isPrime(i):
    ans +=1
print(ans)

Submission status: Time Limit Exceeded

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

A,B = map(int,input().split())
list = cf(A,B)
c = 1
for i in list:
    for j in list:
        if i % j == 0:
            if i == j:
                c +=1
            else:
                break
print(c)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np

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

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

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)
    primeNum.append(1)
    return primeNum

def yakusuu(A):
    Y=[]
    for i in range(1,math.floor(math.sqrt(A+1))+1):
        if A%i==0:
            Y.append(i)
            Y.append(A//i)
    return(Y)

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[-1][0]

N=gcd(A,B)

if N==1:
    print(1)
else:
    ms = factorization(N)
    pl = seachPrimeNum(ms)
    ya = yakusuu(N)
    count=0
#    print(N,ms,pl,ya)
    for i in range(len(pl)):
        if pl[i] in ya:
            count+=1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

# 2つの数字の公約数を求める
C = A
if A > B:
    C = B
nums = [i for i in range(1,C) if A % i == 0 and B % i == 0]

ans = 0
for i in nums:
    for j in nums:
        if i == j:
            continue
        elif fractions.gcd(i,j) != 1:
            key = max(i,j)
            if key in nums:
                nums.remove(key)
print(len(nums)) if nums else print(1)

Submission status: Time Limit Exceeded

Solution code:
def f(x, y):
    re = []
    for i in range(1, min(x, y)+1):
        if x%i==0 and y%i==0:
            re.append(i)
    return re

a, b = (int(x) for x in input().split())
c = f(a, b)

d = c
for i in range(1,len(c)):
    if i >= len(d):
        break
    e = d
    ap = d[i]
    d = [j for j in d if j%ap!=0]
    if len(d) != len(e):
        d.append(ap)
    d.sort()
print(len(d))

Submission status: Time Limit Exceeded

Solution code:
import itertools, fractions
A, B = map(int, input().split())
if A>=B:
    cd_list = [n for n in range(1, B+1) if A%n==0 and B%n==0]
else:
    cd_list = [n for n in range(1, A+1) if A%n==0 and B%n==0]
prime_list = [1]
for i in range(1, len(cd_list)):
    true_list = [1 if fractions.gcd(cd_list[i], n)==1 else 0 for n in cd_list[:i]]
    if sum(true_list) == len(cd_list[:i]):
        prime_list.append(cd_list[i])
print(len(prime_list))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def so(n):
    if n < 2:
        return False
    elif n ==2:
        return True
    elif n % 2 == 0:
        return False
    for i in range(3, int(np.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True
A, B = map(int, input().split())
M = np.min([A, B])
n = 0
for i in range(1, M + 1):
    if so(i):
        if (A % i == 0) and (B % i == 0):
            n = n + 1
print(n + 1)

Submission status: Time Limit Exceeded

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

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


inputData = input().split()
A, B = [int(x) for x in inputData]
cd = cf(A, B)
ans = set(cd)
list_len_dyn = len(cd)
for i in range(1, len(cd) + 1):
    if i == list_len_dyn:
        break
    to_be_removed = []
    for j in range(i + 1, len(cd)):
        tmp = gcd(cd[i], cd[j])
        if tmp != 1:
            iranai = max(cd[i], cd[j])
            to_be_removed.append(iranai)
    for k in to_be_removed:
        cd.remove(k)
    list_len_dyn = len(cd)
print(len(cd))

Submission status: Time Limit Exceeded

Solution code:
import fractions

primes = [2]


def is_prime(n):
    for p in primes:
        if p * p > n:
            break
        if n % p == 0:
            return False

    return True


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

G = int(fractions.gcd(A, B))

res = 1

if G % 2 == 0:
    res += 1
    G //= 2

for i in range(3, G, 2):
    if i > G:
        break
    if not is_prime(i):
        continue
    primes.append(i)
    if G % i == 0:
        res += 1
        G //= i

if G > 1 and is_prime(G) and G not in primes:
    res += 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

g = fractions.gcd(A, B)

ya = []
for i in range(2,g+1):
    if g % i == 0:
        f =0
        for y in ya:
            if i%y==0:
                f = 1
        if f ==0:
            ya.append(i)

print(len(ya) +1)

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 = set()
        p_add = primes.add
        if self.is_prime(n):
            p_add(n)
            return primes

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

        return primes

if __name__ == '__main__':    
    prime = Prime()

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

    print(len(primes) + 1)

Submission status: Time Limit Exceeded

Solution code:
import fractions as math
def main():
    A,B=map(int, input().split())
    gcd_ab = math.gcd(A,B)
    ans={1}
    i = 2
    while (A>=i and B>=i) and (i <= gcd_ab):
        if A % i == 0 and B % i == 0:
            ans.add(i)
            A //= i
            B //= i
            gcd_ab = math.gcd(A,B)
        else:
            i += 1
    print(len(ans))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import itertools

def answer():
    def make_divisors(n):
        divisors = set()
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                divisors.add(i)
                if i != n // i:
                    divisors.add(n // i)

        # divisors.sort()
        return divisors

    a, b = map(int, input().split())
    g = gcd(a, b)
    set_divisors = make_divisors(g)
    set_divisors.remove(1)
    removed = set()

    for div1, div2 in itertools.combinations(set_divisors, 2):
        if div1 in removed or div2 in removed:
            continue
        item = div1 * div2 / gcd(div1, div2)
        if item in set_divisors:
            removed.add(item)
            set_divisors.remove(item)

    print(len(set_divisors)+1)


if __name__ == '__main__':
    answer()

Submission status: Time Limit Exceeded

Solution code:
# 111
list = [int(item) for item in input().split()]

res_list = []
c=0

if list[0] >= list[1]:
    a = list[0]
    b = list[1]
else:
    a = list[1]
    b = list[0]
    
    
res_list.append(b)

if int(b/2) > 1:
    
    if b % 2 == 0:
        res_list.append(int(b/2))
    
    for i in range(1,int(b/2)):
        if b % i ==0:
            res_list.append(i)

res = []
for k in res_list:
    if a % k == 0:
        res.append(k)

new_res = []

for l in reversed(res):
    flag = 0
    cnt = 0
    for m in res:
        if l % m == 0:
            cnt += 1
    if cnt <=2:
        new_res.append(l)
            
print(len(new_res))

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]
        elif a%sosu[i]==0:
            a//=sosu[i]
        elif b%sosu[i]==0:
            b//=sosu[i]


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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

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

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

ld=cf(a,b)
ld.append(1)

#ld2 = divisor(gcd(a,b))
cnt=0
#print(ld)
ansl=[]
for i in ld:
    flg=0
    for j in ansl:
        #if i==j or i==1:
        #    break
        if gcd(i,j) !=1:
            flg = 1
            #print('flg',i,j)
            #if j in ld:
            #    print('in',i,j,gcd(i,j))
            #    ld.remove(j)
            break
        #print(i,j,gcd(i,j))
    if flg == 0:
        ansl.append(i)


print(len(ansl))

#print(ld)

Submission status: Time Limit Exceeded

Solution code:
import math
from fractions import gcd

def is_prime(n):
  if n == 1: 
    return 1

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

  return 1
  
a, b = map(int, input().split())
ans = 0
for i in range(1, min(a, b) + 1):
  if i > 7 and (i % 2 == 0 or i % 3 == 0 or i % 5 == 0 or i % 7 == 0):
    pass
  else:
    if a % i == 0 and b % i == 0:
      ans += is_prime(i)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : map(int, stdin.readline().split())

def divi(n, d = []):
  res = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      if i in d or not d:
        res.append(i)
      if i != n // i:
        if n // i in d or not d:
          res.append(n // i)
  return res

def isprime(n):
  for i in range(2, n+1):
    if i*i <= n:
      if (n % i == 0):
        return False
  return True

def main():
  a, b = sorted(na())
  x = divi(a)
  y = divi(b, x)
  cnt = 0
  for i, yy in enumerate(y):
    if not isprime(yy):
      continue
    cnt += 1
  print(cnt)
main()

Submission status: Time Limit Exceeded

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

l = []
for i in range(n):
    if a % (i+2) == 0 and b % (i +2) == 0:
        l.append(i+2)

primes = [2]
for x in l:
    if all(x % prime !=0 for prime in primes):
        primes.append(x)

if  a % 2 == 0 or b % 2 == 0:
    ans = len(primes) +1
else:
    ans = len(primes)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
a,b = map(int,input().split())
n = fractions.gcd(a,b)
if n ==1:
    print(1)
else:
    l = [1]
    for i in range(n):
        if n%(i+2)==0:
            l.append(i+2)
            while n%(i+2)==0:
              n = n//(i+2)
        if i>n-1:
            break
    print(len(l))

Submission status: Time Limit Exceeded

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

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

out_A = calc_divi(A)
out_B = calc_divi(B)

tmp = list(set(out_A) & set(out_B))
tmp = sorted(tmp, reverse=True)

out = 0
for i in range(len(tmp)):
  jdg = 0
  for k in range(len(tmp)):
    if tmp[i] > tmp[k]:
      if tmp[k] != 1:
        if tmp[i]%tmp[k] == 0:
          jdg = jdg + 1
          break
  if jdg == 0:
    out = out + 1
          
print(out)

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(3, int(math.sqrt(n)) + 1,2):
		if n % k == 0:
			return False

	return True

gc = fractions.gcd(a,b)
if gc == 1:
	print(1)
	exit()

list1 = [1,2]

cout = 0 #1がfalse判定される
for i in range(3,gc+1,2):
	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

print(cout)

Submission status: Time Limit Exceeded

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

if 1 == A or 1 == B:
    print(1)
    exit()

from fractions import gcd


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

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

count = 0
arr = cf(A, B)
#arr.insert(0, 1)
#print(arr)

import math

def get_sieve_of_eratosthenes(data):
    prime = []
    while True:
        p = data[0]
        if data[-1] == p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

print(len(get_sieve_of_eratosthenes(arr)) + 1)

Submission status: Time Limit Exceeded

Solution code:
import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : map(int, stdin.readline().split())

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

def divi(n, d = []):
  res = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      if i in d or not d:
        res.append(i)
      if i != n // i:
        if n // i in d or not d:
          res.append(n // i)
  return res

def isprime(n):
  for i in range(2, n+1):
    if i*i <= n:
      if (n % i == 0):
        return False
  return True

def main():
  a, b = sorted(na())
  x = divi(a)
  y = divi(b, x)
  res = []
  for i, yy in enumerate(y):
    if not isprime(yy):
      continue
    res.append(yy)
  print(len(res))
main()

Submission status: Time Limit Exceeded

Solution code:

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

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

l = cf(A, B)
m = []
m.append(l.pop(0))
while len(l) > 0:
    m.append(l.pop(0))
    l = list(filter(lambda x:x % m[-1] != 0, l))

print(len(m))

Submission status: Time Limit Exceeded

Solution code:
A, B = (int(i) for i in input().split())

c=0
for i in range(1,min(A,B)+1):
    if (A/i == int(A/i) and B/i == int(B/i)):
        c=c+1
        A=A/i
        B=B/i
print(c)