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

ans = [1]

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
 
cflist = cf(a,b)
 
import fractions
import itertools
 
for i in cflist:
        ans.append(i)
        for j in itertools.combinations(ans, 2):
                if 1 == fractions.gcd(j[0],j[1]):
            		    pass
                else:
                        ans.pop()
                        break
 
print(len(ans))

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

import math

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

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

    return True

d = common_divisors(A, B)

ans = 0
for x in d:
    if is_prime(x):
        ans += 1
#print(p)
#print(d)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#ABC142_D
A,B = map(int,input().split())
L = []
if A > B:
    N = A
else :
    N = B
for i in range(1,N+1):
    if (A % i == 0.0) and (B % i == 0.0):
        L.append(i)
L.reverse()
i = 0
while i < len(L)-1:
    j = i + 1
    while j < len(L)-1:
        if int(L[i]) % int(L[j]) == 0 :
            del L[i]
            j -= 1
            i -= 1
        j += 1
    i += 1
print(len(L))

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

import math

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

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

    return True

d = common_divisors(A, B)
p = set(primes(max(d)))
ans = 0
for x in d:
    if is_prime(x):
        ans += 1
#print(p)
#print(d)
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:
            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:
A, B = map(int, input().split())

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


done = {}
def is_coprime(a,b):
	if (a,b) in done:
		return done[a,b]
	if b == 1:
		return True
	for i in range(2, min(A,B)):
		if a % i == 0 and b % i == 0:
			done[(a,b)] = False
			return False
	done[(a,b)] = True
	return True


def getMaxLen(sofar, divisors):
	if len(divisors) == 0:
		return len(sofar)
	curr_max = getMaxLen(sofar,divisors[1:])
	for i in range(len(divisors)):
		d = divisors[i]
		flag = False
		for s in sofar:
			if not is_coprime(d,s):
				flag = True
				break
		if flag:
			continue
		new = sofar.copy()
		
		new.append(d)
		curr_max = max(curr_max, getMaxLen(new, divisors[i+1:]))
	return curr_max

print(getMaxLen([], divisors))

Submission status: Time Limit Exceeded

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


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


a = make_divisors(A)
b = make_divisors(B)
L = []
for x in a:
    if x in b:
        L.append(x)
L.sort()
L = L[1:]#1を消す

ans = 1
for l in L:
    flag = False
    for i in range(2, l):
        if l % i == 0:
            flag = True
            break
    if flag:
        continue
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def div(n):
    a = []
    for i in range(2,n+1):
        while n % i == 0:
            a.append(i)
            n //= i
    return a

a,b = map(int,input().split())
c = list(set(div(a)) & set(div(b)))
ans = len(c)
print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
a,b=list(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(1,gcd(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

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

tmp=cf(a,b)
sum=0
y=[]
for k in tmp:
  if is_prime(k):
    sum += 1

print(sum)

Submission status: Time Limit Exceeded

Solution code:
A,B=map(int,input().split())
def cf(a,b):
  cf=[]
  for i in range(1,min(a,b)+1):
    if a%i==0 and b%i==0:
      cf.append(i)
  return cf
x=[x for x in cf(A,B) if all(x%y!=0 for y in range(2,x))]
print(len(x))

Submission status: Time Limit Exceeded

Solution code:
def gcd(a,b):
    if a<b:
        tmp = a
        a = b
        b = tmp
    while a!=b and b!= 0:
        c = a%b
        a = b
        b = c
    return a

a,b = list(map(int,input().split()))
g = gcd(a,b)
ans = 1
d = []
p = []
for i in range(1,int(g**0.5)+1): #因数リスト
    if g%i==0:
        if i!=1:
            d.append(i)
        if g//i!=1:
            d.append(g//i)
d = list(dict.fromkeys(d))
        
f = [True]*len(d)
for i in range(len(d)):
    for j in range(i):
        if d[i]>d[j] and d[i]%d[j]==0:
            f[i] = False
        if d[i]<d[j] and d[j]%d[i]==0:
            f[j] = False
print(f.count(True)+1)

Submission status: Time Limit Exceeded

Solution code:
def gcd(x,y):
    if x < y:
        x, y = y, x
    if y == 0:
        return x
    if  x % y == 0:
        return y
    else:
        return gcd(y, x%y)
     
def f(n):
    li = []
    while True:
        for i in range(2, n+1):
            if n % i == 0:
                n = n // i
                li.append(i)
                break
            else:
                continue
        else:
            break
    return li
     
a, b = list(map(int, input().split()))
d = gcd(a, b)
print(len(set(f(d))) + 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
A, B = (int(x) for x in input().split())
ls = []
for i in  range(1,int(min(A,B)/2)+2):
    if A%i==B%i==0:
        ls.append(i)

if len(ls)==1:
    print(1)
    sys.exit()
    
i = 1
while(True):
    h = i+1
    while(True):
        if ls[h]%ls[i]==0:
            del ls[h]
            h-=1
            #print(ls)
            #print(h)
        h+=1
        if h>len(ls)-1:
            break
        
    i+=1
    #print(i)
    if i>=len(ls)-1:
        break
print(len(ls))

Submission status: Time Limit Exceeded

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

ans = 1
i = 2
while i <= f:
    if f % i == 0:
        ans += 1
    while f % i == 0:
        f = f//i
    i += 1
    
print(ans)

Submission status: Time Limit Exceeded

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

result = [1]

def gcd(A, B):
    if A == 2 and B == 2:
        result.append(2)
        return result
    if min(A, B) >= 2:
        if A % 2 == 0 and B % 2 == 0:
            result.append(2)
    if min(A, B) >= 3:
        for i in range(3, min(A, B), 2):
            if A % i == 0 and B % i == 0:
                if len(result) != 0:
                    F = ""
                    for j in range(1, len(result)):
                        if i % result[j] == 0:
                            F = "NO"
                    if F == "":
                        result.append(i)
                else:
                    result.append(i)          
        return result

gcd(A, B)
print(len(result))

Submission status: Time Limit Exceeded

Solution code:
def div(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

a,b = map(int,input().split())
c = list(set(div(a)) & set(div(b)))
ans = 0
for i in range(len(c)):
    for j in range(2,c[i]):
        if c[i] % j == 0:
            break
    else:
        ans += 1
print(ans)

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:
      if cursor > 2:
        cursor += 2
      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:
from fractions import gcd
 
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 isPrime(n):
  if n < 2:
    # 2未満は素数でない
    return False
  if n == 2:
    # 2は素数
    return True
  for p in range(2, n):
      if n % p == 0:
        # nまでの数で割り切れたら素数ではない
        return False
  # nまでの数で割り切れなかったら素数
  return True
 
A,B = list(map(int,input().split()))
 
aaa = []
 
aaa = make_divisors(gcd(A,B))
        
count = 0
 
for i in range(len(aaa)):
    if isPrime(aaa[i]) == True:
        count += 1
        
print(count+1)

Submission status: Time Limit Exceeded

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

a,b=map(int,input().split())
MaxValA=1000000000000
NowNumA=2
MaxValB=1000000000000
NowNumB=2
Aans=[1]
Bans=[1]
Allans=[]
startB=0
Allyaku=1
AllCount=0
while MaxValA>NowNumA:
    if a%NowNumA==0:
        MaxValA=a/NowNumA
        Aans.append(NowNumA)
        Aans.append(int(a/NowNumA))
    NowNumA=NowNumA+1
while MaxValB>NowNumB:
    if b%NowNumB==0:
        MaxValB=b/NowNumB
        Bans.append(NowNumB)
        Bans.append(int(b/NowNumB))
    NowNumB=NowNumB+1
for i in range(len(Aans)):
    for j in range(len(Bans)):
        if Aans[i]==Bans[j]:
            Allans.append(Aans[i])
            StartB=j
            break
Allans.sort()
for k in range(len(Allans)):
    if fractions.gcd(Allyaku,Allans[k])==1:
        Allyaku=Allyaku*Allans[k]
        AllCount=AllCount+1
print(AllCount)

Submission status: Time Limit Exceeded

Solution code:
a,b = map(int,input().split())
cnt = 0
if a >= b:
  A = b
else:
  A = a
pn=[2]
for L in range(3,A):
    chk=True
    for L2 in pn:
        if L%L2 == 0:chk=False
    if chk==True:pn.append(L)
pn.append(1)

for i in pn:
  if a%i ==0 and b%i == 0:
    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
a, b = map(int, input().split())
OKs = []
 
if min(a, b) == 1:
  print(1)
  sys.exit()
  
for i in range(2, min(a, b) + 1):
  if a % i != 0:
    continue
  if b % i != 0:
    continue  
  for ok in OKs:
    if i % ok == 0:
      break
  else:
    OKs.append(i)
print(len(OKs) + 1)

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
  l=m/2+2
  while x<=l:
    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
    u=0
    x=x+2
  print(v+2)

Submission status: Time Limit Exceeded

Solution code:
a, b = map(int,input().split())
c = [1]

if a != 1 and b !=1:
    for i in range(2, min(a,b)+1):
        if a % i != 0:
            continue
        elif b % i != 0:
            continue
        else:
            for j in range(1, len(c)):
                if i % c[j] == 0:
                    break
            else:
                c.append(i)
            continue

print(len(c))

Submission status: Time Limit Exceeded

Solution code:
def isprime(g):
    c=0
    for i in range(1,g+1):
        if g%i==0:
            c=c+1
    if c==2:
        return 1
    else:
        return 0

def cd(a,b):
    count=0
    p=[]
    if a>b:
        n=b
    else:
        n=a
    for i in range(1,n+1):
        if a%i==0 and b%i==0:
            p.append(i)

    for i in range(len(p)):
        if isprime(p[i]):
            count += 1
        elif p[i]==1:
            count+=1

    
    return count
p,q=input().split()
print(cd(int(p),int(q)))

Submission status: Time Limit Exceeded

Solution code:
import fractions
import math

A,B = map(int, input().split(" "))
G = fractions.gcd(A,B)

S = set()


def p_fac(N):
  ans = 1
  if (N % 2 == 0):
    ans += 1
    while(N % 2 ==0):
      N = N // 2
  a = 3
  while(a <= N):
    if (N % a == 0):
      ans += 1
      while( N % a == 0):
        N = N // a
    a += 2

  return ans

print(p_fac(G))

Submission status: Time Limit Exceeded

Solution code:
import math, fractions

a, b = map(int, input().split())
n = int(fractions.gcd(a, b))
res = 0
for i in range(3, n):
    if a % i or b % i:
        continue
    dest = int(math.sqrt(i))
    for j in range(2, dest+1):
        if i % j == 0:
            break
    else:
        res += 1
if n >= 2:
    print(res + 2)
else:
    print(res + 1)

Submission status: Time Limit Exceeded

Solution code:
from pprint import pprint
from fractions import gcd
import sys
def input() -> str:
    return sys.stdin.readline()
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n//i)
    return divisors
a, b = map(int, input().split())
cd = sorted(list(make_divisors(a) & make_divisors(b)))
n = len(cd)
divs = [[False for _ in range(n)] for _ in range(n)]
choice = []
answer = 0
for i in cd:
    n = len(choice)
    for j in range(n):
        for k in choice[j]:
            if gcd(i, k) != 1:
                break
        else:
            addition = choice[j] + [i]
            if len(addition) > answer:
                answer = len(addition)
            choice.append(addition)
    choice.append([i])
print(answer if answer > 0 else 1)

Submission status: Time Limit Exceeded

Solution code:
from pprint import pprint
from fractions import gcd
import sys
def input() -> str:
    return sys.stdin.readline()
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n//i)
    return divisors
a, b = map(int, input().split())
cd = sorted(list(make_divisors(a) & make_divisors(b)))
n = len(cd)
divs = [[False for _ in range(n)] for _ in range(n)]
choice = []
answer = 0
for i in cd:
    n = len(choice)
    for j in range(n):
        for k in choice[j]:
            if gcd(i, k) != 1:
                break
        else:
            addition = choice[j] + [i]
            if len(addition) > answer:
                answer = len(addition)
            choice.append(addition)
    choice.append([i])
print(answer if answer != 0 else 1)

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 A % i != 13 and B % i != 13 
and A % i != 17 and B % i != 17 
and A % i != 19 and B % i != 19 
and A % i != 23 and B % i != 23 
and A % i != 29 and B % i != 29 
and A % i != 31 and B % i != 31 
and A % i != 37 and B % i != 37 
and A % i != 41 and B % i != 41 
and A % i != 43 and B % i != 43 
and A % i != 47 and B % i != 47 
and A % i != 53 and B % i != 53 
and A % i != 59 and B % i != 59 
and A % i != 61 and B % i != 61 
and A % i != 67 and B % i != 67 
and A % i != 71 and B % i != 71 
and A % i != 73 and B % i != 73 
and A % i != 79 and B % i != 79 
and A % i != 83 and B % i != 83 
and A % i != 89 and B % i != 89 
and A % i != 97 and B % i != 97 
and A % i != 101 and B % i != 101 
and A % i != 103 and B % i != 103 
and A % i != 107 and B % i != 107 
and A % i != 109 and B % i != 109 
and A % i != 113 and B % i != 113 
and A % i != 127 and B % i != 127 
and A % i != 131 and B % i != 131 
and A % i != 137 and B % i != 137 
and A % i != 139 and B % i != 139 
and A % i != 149 and B % i != 149 
and A % i != 151 and B % i != 151 
and A % i != 157 and B % i != 157 
and A % i != 163 and B % i != 163 
and A % i != 167 and B % i != 167 
and A % i != 173 and B % i != 173 
and A % i != 179 and B % i != 179 
and A % i != 181 and B % i != 181 
and A % i != 191 and B % i != 191 
and A % i != 193 and B % i != 193 
and A % i != 197 and B % i != 197 
and A % i != 199 and B % i != 199 
and A % i != 211 and B % i != 211 
and A % i != 223 and B % i != 223 
and A % i != 227 and B % i != 227 
and A % i != 229 and B % i != 229 
and is_prime(i) == True])
print(len(list))

Submission status: Time Limit Exceeded

Solution code:
import math
A,B=map(int,input().split())
def cf(a,b):
  cf=[]
  for i in range(1,min(a,b)+1):
    if a%i==0 and b%i==0:
      cf.append(i)
  return cf
x=[x for x in cf(A,B) if all(x % y != 0 for y in range(2, x))]
print(len(x))

Submission status: Time Limit Exceeded

Solution code:
def gcd(a,b):
    if a<b: a,b=b,a
    while b: a,b = b, a%b
    return a
def main():
  a, b = map(int, input().split())
  c = gcd(a, b)
  ans = 1
  i = 2
  while c!=1:
    if c%i==0: ans+=1
    while c%i==0: c//=i
    i+=1
  print(ans)
if __name__=="__main__":main()

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(2**31-1)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def gcd(a,b):
    if a % b == 0:
        return b
    else:
        return gcd(b,a%b)
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    A,B = LMIIS()
    g = gcd(A,B)
    cds = set([1])
    d = 2
    while g != 1:
        if g % d == 0:
            g //= d
            cds.add(d)
        else:
            d += 1
    print(len(cds))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
#import sympy as sym
#import numpy as np

def decomposition(n):
    table = []
    for i in range(1, (n // 2) + 1):
        if n % i == 0 and not i in table:
            table.extend([i, n/i])
    return table


def solve(A: int, B: int):
    divA = decomposition(A)
    divB = decomposition(B)
    #print(divA, divB)
    if divA == [] or divB ==[]:
        print(1)
        sys.exit(0)
    divs = list(set(divA) & set(divB))
    #print(divs)
    #cd = np.array(divs[1])
    if len(divs) == 1:
        print(1)
        sys.exit(0)
    
    cd = []
    cd.append(divs[1])
    #print(cd)
    for i in divs[2:]:
        w = [(i % j) for j in cd]
        #print(i, w)

        if all(w):
            #np.append(cd, i)
            cd.append(i)
    
    print(len(cd)+1)



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
a, b = map(int, input().split())
def gcd(a, b):
    while b > 0:
        a, b = b, a%b
    return a
n = gcd(a, b)
def get_primenumber(N):
    #素数リスト
    prime_list = [2]
    #3からNまでの数字を一つずつ取り出す
    for num in range(3,N+1,2):
      #取り出した数字が素数リストの要素で割れなければ素数リストに追加する
      if all( num % prime != 0 for prime in prime_list):
        prime_list.append(num)

    return prime_list
l = get_primenumber(n)
count = 1
for p in l:
    if a % p == 0 and b % p == 0:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
def main():
    inputs = input().split()
    inputs = [int(i) for i in inputs]

    a = inputs[0]
    b = inputs[1]

    min_n = min([a, b])

    kouyaku = []

    for n in range(1, min_n + 1):
        if a % n == 0 and b % n == 0:
            kouyaku.append(n)

    so = [1]
    for i in kouyaku:
        if i == 1: continue

        f = True
        for j in kouyaku:
            if j == 1 or i < j: continue
            if i != j and i % j == 0:
                f = False
                break
        if f is True:
            so.append(i)

    print(len(so))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
a,b=list(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(1,gcd(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

def di(z,y):
  for i in range(len(y)):
    if y[i] != 1 and z % y[i] == 0:
      return False
  for i in range(2,int(np.sqrt(z))+1):
    if z % i == 0:
      return False
  return True

tmp=cf(a,b)
sum=0
y=[]
for j in range(len(tmp)):
  if di(tmp[j],y):
    y.append(tmp[j])
    sum += 1

print(sum)

Submission status: Time Limit Exceeded

Solution code:
tmp = input().split()
A = int(tmp[0])
B = int(tmp[1])

so = [2, 3, 5, 7, 11, 13, 17, 19]
count = 1

for i in range(2, A):
    flag = True
    for j in so:
        if i != j and i % j == 0:
            flag = False
            break
    if not flag:
        continue
    if A % i == 0 and B % i == 0:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import math

a, b = [int(elem) for elem in input().split()]

cf = []
for i in range(1, min(a, b)+1):
    if a % i == 0 and b % i == 0:
       cf.append(i)
       
# dest = int(math.sqrt(min(a, b)))
if len(cf) > 1:
    res = [cf[0], cf[1]]
    cf.pop(0)
    cf.pop(0)

    j = 0
    while True:
        if j >= len(cf):
            break
        flag = 0
        for elem in res[1:]:
            if cf == []:
                break
            if gcd(cf[j], elem) != 1:
                cf.pop(j)
                flag = 1
                break
        if flag == 0:
            res.append(cf[j])
            cf.pop(j)
else:
    res = [cf[0]]
print(len(res))

Submission status: Time Limit Exceeded

Solution code:
a, b = map(int,input().split())
c = [1]

if a != 1 and b !=1:
    for i in range(2, a+1):
        if a % i != 0:
            continue
        elif b % i != 0:
            continue
        else:
            for j in range(1, len(c)):
                if i % c[j] == 0:
                    break
            else:
                c.append(i)
            continue

print(len(c))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd


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


def co_prime(arr, i):
    for x in arr:
        if not coprime(x, i):
            return False
    return True


a, b = [int(x) for x in input().split(' ')]
first = True
divs = []
for i in range(1, min(a, b) + 1): 
    if a % i==b % i==0:
        if first:
            divs.append(i)
            first = False
        else:
            if co_prime(divs, i):
                divs.append(i)

print(len(divs))

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
    u=0
    x=x+2
  print(v+2)

Submission status: Time Limit Exceeded

Solution code:
"""
see https://qiita.com/daikw/items/f48d6ac374255763463d
"""

import math
import random


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]


class MillerRabin:
    """
    see https://qiita.com/srtk86/items/609737d50c9ef5f5dc59
    """

    def __init__(self, witnesses=None):
        if witnesses is None:
            self.witnesses = MillerRabin._witnesses
        else:
            self.witnesses = witnesses

    @staticmethod
    def _witnesses(num):
        def _get_range():
            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 seed_primes[:_get_range()]

    @staticmethod
    def _random_witnesses(num):
        return [random.randint(1, num - 1) for _ in range(100)]

    def is_prime(self, n):
        d = n - 1
        while d & 1 == 0:
            d >>= 1

        witnesses = self.witnesses(n)
        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


class BruteForce:
    @staticmethod
    def is_prime(n):
        for k in range(2, int(math.sqrt(n)) + 1):
            if n % k == 0:
                return False
        return True


miller_rabin = MillerRabin()


def is_prime(n):
    """
    see https://qiita.com/gushwell/items/ff9ed83ba55350aaa369
    """
    if n == 1:
        return False
    if n in seed_primes:
        return True
    if any(map(lambda x: n % x == 0, seed_primes)):
        return False

    if n < 200000:
        return BruteForce.is_prime(n)
    else:
        return miller_rabin.is_prime(n)


def gcd(a, b):
    import fractions
    return fractions.gcd(a, b)
    # if a < b:
    #     return gcd(b, a)
    # if b == 0:
    #     return a
    # while b:
    #     a, b = b, a % b
    # return a


class PollardsRho:
    def find_factor(self, n, seed=1):
        """
        see
        https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
        https://qiita.com/gushwell/items/561afde2e00bf3380c98
        """
        def f(x):
            p = seed_primes[seed % len(seed_primes)]
            return (p * x + seed) % n

        if is_prime(n):
            return n

        x, y, d = 2, 2, 1
        count = 0
        while d == 1:
            count += 1
            x = f(x)
            y = f(f(y))
            d = gcd(abs(x - y), n)

        if d == n:
            return self.find_factor(n, seed + 1)
        return self.find_factor(d)

    def factorize(self, n):
        primes = {}
        if is_prime(n):
            return {n: 1}

        while n > 1:
            factor = self.find_factor(n)
            primes.setdefault(factor, 0)
            primes[factor] += 1
            n //= factor

        return primes


class Fermat:
    @staticmethod
    def is_prime(n):
        if n == 1:
            return False
        if n == 2:
            return True

        for k in range(100):
            a = random.randint(2, n - 1)

            if gcd(n, a) != 1:
                return False

            if pow(a, n - 1, n) != 1:
                return False

        return True


import fractions

a, b = list(map(int, input().split()))
x = fractions.gcd(a, b)

dic = PollardsRho().factorize(x)
print(len(dic) + 1)

Submission status: Time Limit Exceeded

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

A, B = map(int, input().split())
if A > B:
    A, B = B, A
c = gcd(A, B)
li = [1]

for i in range(2, c+1):
    if i > c:
        break
    if c%i == 0:
        li.append(i)
        while c%i == 0:
            c = c//i

print(len(li))

Submission status: Time Limit Exceeded

Solution code:
a,b=map(int,input().split())
lista=[]
import fractions
gcd=fractions.gcd(a,b)

for i in range(2,gcd+1): 
    if gcd% i == 0: 
        lista.append(i)

#print(lista)
listb=[]
for i in range(len(lista)):
    flag = True
    for j in range(len(listb)):
        if lista[i]%listb[j]==0:
            flag = False    
    if flag==True:
        listb.append(lista[i])

print(len(listb)+1)