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:
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())
cf_=cf(a,b)
count_so=0
for x in cf_:
    for y in cf_:
        if x==y:
            count_so+=1
            break
        if cf(x,y)!=[1]:
            break
print(count_so)

Submission status: Time Limit Exceeded

Solution code:
def isPrime(N, arr):
	if N == 1:
		return True
	for i, x in enumerate(arr):
		if x > 1 and N % x == 0:
			return False
	return True

def q_D(A, B):
	target = A
	another = B
	if A > B:
		target = B
		another = A
	yaku = []
	if target == 1:
		yaku.append(1)
	for i in range(int(target/2)):
		x = i + 1
		if target % x == 0 and another % x == 0:
			if isPrime(x, yaku):
				yaku.append(x)
	print(len(yaku))

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

Submission status: Time Limit Exceeded

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

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

def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1

a = cf(A, B)

count = 1

for a in a:
    if is_prime(a):
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import math
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,1+int(math.sqrt(int(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 math

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

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

def primelist(n):
    P = [2]
    flag = 0
    for i in range(3,n+1,2):
        for j in range(len(P)):
            if math.sqrt(i) < P[j]:
                break
            else:
                if i%P[j] == 0:
                    flag += 1
                    break
        if flag == 0:
            P.append(i)
        flag = 0
    P.append(1)
    return(P)

def maxsoin(n):
    x = n
    i = 2
    prime_factors = []
    while x > 1:
      if x % i == 0:
        prime_factors.append(i)
        x = x / i
      else:
        i += 1
    result = max(prime_factors)
    return(result)

N=gcd(A,B)

if N==1:
    print(1)
else:
    ms = maxsoin(N)
    pl = primelist(ms)
    ans=0
    for i in range(len(pl)):
        if N%pl[i]==0:
            ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import math

tmp = list(map(int,(input().split())))
a = tmp[0]
b = tmp[1]

limit = fractions.gcd(a, b)
sqmin = min(int(math.sqrt(a)), int(math.sqrt(b)))
cnt = 0
for i in range(2, limit+1):
  if i > sqmin and i != a and i != b:
    pass
  else:
    flag = False
    while (a % i == 0) and (b % i == 0):
      a = a // i
      b = b // i
      flag = True
    if flag:
      cnt += 1
   
print (cnt+1)

Submission status: Time Limit Exceeded

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

import sys

if small == 1:
    print(1)
    sys.exit(0)

import math
table = [i for i in range(2, small + 1) if (i % 2 != 0)]
limit  = math.sqrt(small)
cd = []
if small % 2 == 0 and big % 2 == 0:
    cd.append(2)
while True:
    if len(table) == 0:
        break
    head = table.pop(0)
    if head > limit:
        break
    table = [v for v in table if (v % head != 0) and (small % head == 0) and (big % head == 0)]
    if (small % head == 0) and (big % head == 0):
        cd.append(head)
cd.extend(table)

print(len([i for i in cd if (small % i == 0) and (big % i == 0)]) + 1)

Submission status: Time Limit Exceeded

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

def calcCommonDivisor(a, b):
    cdiv=[]
    for i in range(1, max(a,b)+1):
        if a%i==0 and b%i==0:
            cdiv.append(i)

    return cdiv

def isPrime(a):
    if a == 1:
        return True

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

    return len(d) == 2

cdiv=calcCommonDivisor(a,b)
if len(cdiv) == 1:
    print(1)
    quit()

ans=0
for i in cdiv:
    if isPrime(i):
        ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import fractions
import itertools


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 input():
    return sys.stdin.readline().rstrip()


def main():
    A, B = map(int, input().split())
    m = fractions.gcd(A, B)
    l = make_divisors(m)
    n = len(l)

    ans = 0
    for bit in range(1 << n):
        group = []
        for i in range(n):
            if bit & (1 << i):
                group.append(l[i])

        flag = True
        for i in itertools.combinations(group, 2):
            if fractions.gcd(i[0], i[1]) != 1:
                flag = False
                break

        if flag:
            ans = max(ans, len(group))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def euc(a,b):
  if a<b:
    a,b=b,a
  while(a%b!=0):
    a,b=b,a%b
    
  return b
 
one,two = [int(x) for x in input().split()]
 
aa = euc(one,two)
 
c=[]
for i in range(1,aa+1):
  if aa%i==0:
  	c.append(i)
    
c1=[(x) for x in c]
 
for i in c:
  for j in c1:
    if i>=j:
      continue
      
    if euc(i,j)!=1 and i!=1 and j!=1:
      if j in c:
        c.remove(j)
      
      
print(len(c))

Submission status: Time Limit Exceeded

Solution code:
A,B=map(int,input().split())
def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1] and n%i==0]
    return is_prime, table
_, A_cf = sieve(A)
_, B_cf = sieve(B)
cf = []
for i in A_cf:
    for j in B_cf:
        if i==j:
            cf.append(i)
print(len(cf)+1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def so(n):
    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 = 1
if (A % 2 == 0) and (B % 2 == 0):
    n = 2
for i in range(3, M, 2):
    if (A % i == 0) and (B % i == 0):
        if so(i):        
            n = n + 1
print(n)

Submission status: Time Limit Exceeded

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

def main():
    A,B=map(int, input().split())
    gcd_ab = 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 = gcd(A,B)
        else:
            i += 1
    print(len(ans))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

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

def common_divisor(n):
  if n == 1:
    return [1]
  ret = []
  for i in range(1,math.ceil(math.sqrt(n))+1):
    if n%i==0:
      ret.append(i)
      ret.append(n//i)      
  return list(set(ret))

ca = common_divisor(a)
cb = common_divisor(b)

sa = set(ca)
c = sa.intersection(cb)

count = 0
for ci in c:
  if len(common_divisor(ci))<=2:
    count+=1    

print(count)

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,gcd(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)):
        if cd[j] % cd[i] == 0:
            to_be_removed.append(cd[j])
            continue
        if gcd(cd[i], cd[j]) != 1:
            to_be_removed.append(cd[j])
    for k in to_be_removed:
        cd.remove(k)
    list_len_dyn = len(cd)
print(len(cd))

Submission status: Time Limit Exceeded

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

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

cnt = 0

for j in lst:    
    flag = 1
    for k in range(2, int(math.sqrt(j))+1):
        if j % k == 0:
            flag = 0
            break
    cnt += flag

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def prime(n):
    num=[i for i in range(n,1,-1) if n%i ==0]
    prime=[]
    p = 2
    while p <=n**0.5 and len(num) != 0:
        p=num.pop()
        prime.append(p)
        num = [i for i in num if i%p != 0]
    return prime
def chk_prime(n):
    for i in range(2,-1*int(-n**0.5//1)):
        if n%i == 0:
            return False
    return True

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

    ans = 1
    if chk_prime(min(a,b)):
        if max(a,b)%min(a,b) == 0 and min(a,b) != 1:
            ans = 2
    else:
        prime_list=prime(int(min(a,b)/2))
        for i in prime_list:
            if a%i == 0 and b%i==0:
                ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

def cf(x, y):
    cf = [1]
    for i in range(2, gcd(x, y)+1):
        if x%i == 0 and y%i == 0:
            cf.append(i)
    return cf

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

ans = 0
for i in cf(A, B):
    if isPrime(i) == True:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

def cf(x1,x2):
    cf=[1]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            d = make_divisors(i)
            d.pop()
            leng = len(set(d)-set(cf[1:]))
            if len(d) == leng:
                cf.append(i)
    return cf

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

c = cf(A, B)
ans =len(c)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
a,b = list(map(int, input().split()))
lst = []
for i in range(1, min(a, b)+1): 
    if a%i==b%i==0: 
        lst.append(i)
#print(lst)

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

ct = 1
for i in lst:
  if is_prime(i):
    ct += 1
print(ct)

Submission status: Time Limit Exceeded

Solution code:
import fractions
a, b = map(int, input().split())
gcd = fractions.gcd(a, b)
primes = [ 1 ]
for i in range(2, int(gcd) + 1):
    if gcd % i == 0:
        if i == 2:
            primes.append(2)
        if i == 3:
            primes.append(3)
        if i % 2 != 0 and i % 3 != 0:
            isPrime = True
            for j in range(5, 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())


def primes(n):
    is_prime = [True] * (n + 1)
    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: True for i in range(n + 1) if is_prime[i]}

import fractions
def common_divisors(a, b):
    a = fractions.gcd(a, b)
    divisors =  [d for d in range(2, a // 2 + 1) if a % d == 0] + [a]
    if not 1 in divisors:
        divisors.append(1) 
    return divisors, a


d, max_a= common_divisors(A, B)
p = set(primes(max_a))
ans = 0
for x in d:
    if x in p:
        ans += 1
#print(p)
#print(d)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
#        for line in sys.stdin:
#            lines.append(line)
        lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]

    a, b = [int(e) for e in lines[0].split(" ")]

    return (a, b)

def gcd(a, b):

    c = min(a, b)
    d = max(a, b)
    r = 0    
    while True:
        r = d % c
        if r == 0:
            break
        d = c
        c = r

    return c

def lcm(a, b):
    g = gcd(a, b)
    return (a * b) // g

def solve(a, b):

    result = []
    for i in range(2, min(a, b) + 1):
        if a % i == 0 and b % i == 0:
            if debug:
                log(i)

            added = True
            for r in result:
                if i % r == 0:
                   added = False
                   break

            if added:
                result.append(i)


    return len(result) + 1


def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r)
    else:
        print("%s" % result)

if __name__ == '__main__':

    main()

Submission status: Time Limit Exceeded

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

def is_prime(n):
    a = 0
    for k in range(1 + 1, int(math.sqrt(n)) + 1):
        if n % k == 0:
            a = 1
    if a == 1: return False
    else :return True

list = [1]
list.extend([i for i in range(1+1, min(A, B)+1) if A % i == 0 and B % i == 0 
and A % i != 2 and B % i != 2 
and A % i != 3 and B % i != 3 
and A % i != 5 and B % i != 5 
and A % i != 7 and B % i != 7 
and A % i != 11 and B % i != 11 and is_prime(i) == True])
print(len(list))

Submission status: Time Limit Exceeded

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


def primes(n):
    is_prime = [True] * (n + 1)
    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: True for i in range(n + 1) if is_prime[i]}

import fractions
def common_divisors(a, b):
    a = fractions.gcd(a, b)
    divisors =  [d for d in range(2, a // 2 + 1) if a % d == 0] + [a]
    if not 1 in divisors:
        divisors.append(1) 
    return divisors


d = common_divisors(A, B)
p = set(primes(max(d)))
ans = 0
for x in d:
    if x in p:
        ans += 1
#print(p)
#print(d)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

def get_divisors(x, y):
  divisors = []
  for i in xrange(1, min(x,y) + 1):
    if x % i == 0 and y % i == 0:
      divisors.append(i)
  return divisors

def main():
  x, y = map(int, raw_input().split())
  if x == 1 or y == 1:
      print(1)
      return

  divisors = get_divisors(x, y)
  results = [0 for _ in xrange(len(divisors))]

  for i, a in enumerate(divisors):
      for b in divisors:
          divs = get_divisors(a, b)
          if len(divs) == 1 and divs[0] == 1:
              results[i] += 1
              continue
          if len(divs) == 2 and divs[0] == 1 and divs[1] == b:
              results[i] += 1
              continue

  print(min(results))


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
A, B = map(int, sys.stdin.readline().split())

a, b = deque([]), deque([])
for i in range(A, 0, -1):
    if A%i ==0:
        a.append(i)
    
for i in range(B, 0, -1):
    if B%i ==0:
        b.append(i)

a,b = set(a), set(b)
L = a&b
#print(L)
cnt =0
for l in L:
    tmp = 0
    for i in range(l-1, 1, -1):
        if l%i==0:
            tmp +=1
            break
    if tmp ==0:
        cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

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

result = []

def gcd(A, B):
    i = 2
    while i < min(A, B):
        if A % i == 0 and B % i == 0:
            if len(result) != 0:
                F = ""
                for j in result:
                    if i % j == 0:
                        F = "NO"
                if F == "":
                    result.append(i)
            else:
                result.append(i)
        i += 1
    return result

print(len(gcd(A, B))+1)

Submission status: Time Limit Exceeded

Solution code:
N = list(map(int, input().split()))
if (N[0] == 1 and N[1] >= 1) or N[1] == 1:
  print(1)
elif N[0] > 1 or N[1] > 1:
  list =[]
  for i in range(2,min(N)):
    if N[0] % i == 0 and N[1]% i == 0:
      if len(list) == 0:
        list.append(i)
      elif len(list) > 0:
        f = True
        for j in list:
          if i % j == 0:
            f = False
            break
        if f :
          list.append(i)
  print(len(list)+1)

Submission status: Time Limit Exceeded

Solution code:
import math
 
def gcd(x, y):
	while y != 0:
		z = x % y
		x = y
		y = z
	return x
 
a, b = map(int, input().split())
x    = gcd(a, b)
y    = x // 2 + 1
ds   = [1]

if x % 2 == 0:
	ds.append(2)

for i in range(3, y + 1, 2):
	if x % i == 0:
		ds.append(i)

if 2 < x:
	ds.append(x)

fs = [True] * len(ds)

for i in range(1, len(fs)):
	if fs[i] == False:
		continue;
	for j in range(i + 1, len(fs)):
		if ds[j] % ds[i] == 0:
			fs[j] = False

print(sum(1 for f in fs if f == True))

Submission status: Time Limit Exceeded

Solution code:
# 1. 最大公約数を求める(ユークリッドの互除法)
# 2. 最大公約数を素因数分解する。
# 3. 2.の結果に含まれる素数を２つのグループに分ける

from collections import defaultdict
import itertools

def main():
  a, b = map(int, input().split())
  c = gojo(a,b)
  
  fac = defaultdict(lambda : 0)
  #print(c)
  fac[1] = 1
  fac = facto(c, fac)
  #print(fac)
  keys = list((fac.keys()))
  print(len(keys))  
  
def facto(n, fac):
  if n == 1:
    return fac
  cursor = 2
  while True:
    if n % cursor == 0:
      fac[cursor] += 1
      n = n // cursor
      if n == 1:
        break
    else:
      cursor += 1
      
  return fac
  
def gojo(a,b):
  if b > a:
    a, b = b, a
  c = a % b
  if c == 0:
    return(b)
  else:
    return gojo(b, c)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

n = 2

while n <= int(max(a, b)):
    if a%n == 0 and b%n == 0:
        while a%n == 0:
            a = a//n
        while b%n == 0:
            b = b//n
        ans += 1
    
    if n == 2:
        n += 1
    else:
        n += 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def prime(n):
    num=[i for i in range(n,1,-1)]
    prime=[]
    p = 2
    while p <=n**0.5 and len(num) != 0:
        p=num.pop()
        prime.append(p)
        num = [i for i in num if i%p != 0 and n%i == 0]
    return prime
def chk_prime(n):
    for i in range(2,-1*int(-n**0.5//1)):
        if n%i == 0:
            return False
    return True

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

    ans = 1
    if chk_prime(min(a,b)):
        if max(a,b)%min(a,b) == 0 and min(a,b) != 1:
            ans = 2
    else:
        prime_list=prime(int(min(a,b)/2))
        for i in prime_list:
            if a%i == 0 and b%i==0:
                ans += 1
    print(ans)

if __name__ == '__main__':
    main()

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]
list2 = [1]
if a%2 == 0 and b%2 == 0:
	list1.append(2)
	list2.append(2)
cout = 0 #1がfalse判定される

for i in range(3,gc+1,2):
	if a%i == 0:
		if is_prime(i):
			list1.append(i)
for i in range(3,gc+1,2):
	if b%i == 0:
		if is_prime(i):
			list2.append(i)

list3 = set(list1) & set(list2)

print(len(list3))

Submission status: Time Limit Exceeded

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

#最大公約数を求める
max_val = max(a, b)
min_val = min(a, b)

while(1):
  if max_val % min_val ==0:
    break
  else:
    tmp = max_val % min_val
    max_val = min_val
    min_val = tmp
    
#print(min_val)

list = []

for i in range(1, min_val//2 + 1):
  if (min_val % i == 0):
    list.append(i)
    
list.append(min_val)

for i in range(len(list)-1,0, -1): # 1は除外
  for j in range(i-1,0,-1):
 #   print("list[i],list[j]",list[i],list[j])
    if list[i] % list[j] == 0 and list[i] > 2:
      list[i] = 0

#print(list)
for i in range(len(list)-1 ,0,-1):
  if list[i]==0:
    list.pop(i)
      
#print(list)
#sum = 0
#for i in range(len(list)):
 # for j in range(i,len(list)):
  #  if (list[j] % list[i]) == 1:
   #   sum += 1
 
print(len(list))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

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)
    if A == []:
        A.append(tmp)
    else:
        for i in range(len(A)):
            if tmp % A[i] == 0:
                break
            else:
                if i == len(A) - 1:
                    A.append(tmp)
    #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 math
a,b = list(map(int,input().split()))
cf=[1]
ccf=[1]
for i in range(2,min(a,b)+1):
  if a % i == 0 and b % i == 0:
    cf.append(i)
for ii in range (len(cf)):
  q=0
  if cf[ii] == 1: 
    q =1
  for k in range(2, int(math.sqrt(cf[ii])) + 1):
    if cf[ii] % k == 0:
      q=1
  if q ==0:
    ccf.append(cf[ii])
print(len(ccf))

Submission status: Time Limit Exceeded

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


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


ans = 1
for i in range(2, fractions.gcd(A, B)+1):
    if i > 2 and i % 2 == 0:
        continue
    if A % i == 0 and B % i == 0:
        prime = is_prime(i)
        if prime:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

def divisors(n):
    for i in range(2, n+1):
        if n % i == 0:
            yield i

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

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

    if b > a:
        a, b = b, a
	
    relative_primes = []
    for div in divisors(b):
        if a % div != 0:
            continue
        flg = True
        for rp in relative_primes:
            if div % rp == 0:
                flg = False
                continue
        if flg:
            relative_primes.append(div)
    print(len(relative_primes)+1)
    

main()

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())
li = cf(A,B)
c = 1
for i in li:
    for j in li:
        if i % j == 0:
            if i == j:
                c +=1
            else:
                break
print(c)

Submission status: Time Limit Exceeded

Solution code:
A,B=input().split()
a=int(A)
b=int(B)
m=1
n=1
while n<=min(a,b):
  if a%n==0:
    if b%n==0:
      m=n
      n=n+1
    else:
      n=n+1
  else:
    n=n+1
if m==1:
  print(1)
elif m==2:
  print(2)
else:
  x=3
  u=0
  v=0
  while x<=m:
    t=2
    while t<=x-1:
      if x%t==0:
        u=u+1
        t=t+1
      else:
        u=u
        t=t+1
    if u==0:
      if m%x==0:
        v=v+1
      else:
        v=v
    else:
      v=v
    u=0
    x=x+1
  print(v+2)

Submission status: Time Limit Exceeded

Solution code:
import copy, math
A, B = map(int, input().split())
C = 1
ac = copy.deepcopy(A)
bc = copy.deepcopy(B)
while C != 0:
    C = ac % bc
    ac, bc = bc, C

a_list = []
for b in range(1, ac+1):
    if A % b == 0 and B % b == 0:
        a_list.append(b)

b_list = []
for a in a_list:
    if a == 1:
        pass
    elif a == 2:
        pass
    else:
        for x in range(2, int(math.sqrt(a))+1):
            if a % x == 0:
                b_list.append(a)
a_set = set(a_list)
b_set = set(b_list)
ans = a_set - b_set
print(len(ans))

Submission status: Time Limit Exceeded

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

#最大公約数を求める
max_val = max(a, b)
min_val = min(a, b)

while(1):
  if max_val % min_val ==0:
    break
  else:
    tmp = max_val % min_val
    max_val = min_val
    min_val = tmp
    
#print(min_val)

list = []

for i in range(1, min_val//2 + 1):
  if (min_val % i == 0):
    list.append(i)
    
list.append(min_val)

for i in range(len(list)-1,0, -1): # 1は除外
  for j in range(i-1,0,-1):
 #   print("list[i],list[j]",list[i],list[j])
    if list[i] % list[j] == 0 and list[i] > 2:
      list[i] = 0

#print(list)
for i in range(len(list)-1 ,0,-1):
  if list[i]==0:
    list.pop(i)
      
#print(list)
sum = 0
for i in range(len(list)):
  for j in range(i,len(list)):
    if (list[j] % list[i]) == 1:
      sum += 1
 
print(len(list))

Submission status: Time Limit Exceeded

Solution code:
a,b = map(int,input().split())
c = []
for i in range(2,min(a,b)+1):
    if a % i == 0 and b % i == 0:
       c.append(i)
for k in range(len(c)):
    for j in range(len(c)):
        if (c[k])%(c[j])==0:
           if c[k] != c[j]:
              c[k] =2
c.append(1)
print(len(set(c)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
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
def so(x1,x2):
  if len(cf(x1,x2)) == 1:
    return 1
  else:
    return 0
A,B = map(int,input().split())
count = 1
C = cf(A,B)
for i in range(len(C)):
  for j in range(len(C)-(i+1)):
    if so(C[i],C[i+(j+1)]) == 0:
      C[i+(j+1)] = 0
print(np.count_nonzero(C))

Submission status: Time Limit Exceeded

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

minAB = min(A,B);

upper = int(math.sqrt(minAB+1))
ans = 1

for i in range(2, minAB+1):
    if A % i != 0 or B % i != 0:
        continue;
    falg = True
    for j in range(2, i-1):
        if(i % j == 0):
            falg = False
            break
    if falg:
        ans+=1
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a,b=map(int,input().split())
i=1
small = min(a,b)
ab=[]
j=0
while i <= small :
    if b%i==0 and a%i==0 :
        flag = 0
        j=0
        while j < len(ab):
            if ab[j]!=1 and i % ab[j] == 0:
                flag=1
            j+=1
        if flag == 0:
            ab.append(i)

    i+=1


print(len(ab))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
from fractions import gcd

ans=0
aaa=0

a,b=map(int,input().split())
c=gcd(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
s=make_divisors(c)
#print(s)
for i in s:
    aaa=0
    if i%2==0:
        aaa=1
    if i>=3 and i%2==1:
        for j in range(2,i):
            #print(i,j)
            if i%j==0:
                aaa=1
                break
            else:
                aab=0
    if aaa==0:
        ans+=1
if c%2==0:
	ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd as bltin_gcd
import itertools

def coprime2(a, b):
    return bltin_gcd(a, b) == 1

A, B = map(int, input().split())
koyakusuu_list = []
for a in range(1, A+1):
    if a == 1:
        koyakusuu_list.append(1)
    elif B % a == 0 and A % a == 0:
        flag = 0
        for kouyakusuu in koyakusuu_list:
            if coprime2(a, kouyakusuu):
                continue
            else:
                flag += 1
        if flag == 0:
            koyakusuu_list.append(a)

print(len(set(koyakusuu_list)))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from math import sqrt, ceil

def main():

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

    divs = [1]
    for i in range(2, min(a, b)+1):
        if (a/i).is_integer() and (b/i).is_integer():
            divs.append(i)
            while (a/i).is_integer() and (b/i).is_integer():
                a = a/i; b = b/i
    print(len(divs))

main()

Submission status: Time Limit Exceeded

Solution code:
A,B=map(int,input().split())
import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000000)
def gcd(a,b):#最大公約数を返す。Euclid
    if a<b:
        a,b=b,a
    if b==0:
        return a
    return gcd(b,a%b)
c=gcd(A,B)
#print(c)
if c==1:
    print(1)
else:
    sqrtc=int(c**(1/2))
    lf=[0 for i in range(c-1)]#2,3,,,,c
    #print(lf)
    for i in range(sqrtc):
        if lf[i]==0:
            for j in range(i+2,c//(i+2)+1):
                lf[(i+2)*j-2]=1
    #print(lf)
    ans=1
    for i in range(c-1):
        if lf[i]==0 and c%(i+2)==0:
            ans+=1

    #print(c-sum(lf)+1)
    print(ans)