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:
ans = 1
x1, x2 = map(int, input().split())
for i in range(2,min(x1,x2)+1):
  if x1 % i == 0 and x2 % i == 0:
    ans += 1
    while x1%i == x2%i == 0:
      x1 //= i
      x2 //= i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools

A, B = map(int, sys.stdin.readline().split())

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

a = set(a)
b = set(b)
L = a&b
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:
# print(a,b)
import math

def getDivisors(a,b):
  divisors = []
  for i in range(1,min(num)):
    if (a%i==0 and b%i==0):
      divisors.append(i)
  return divisors


def getCoprime(divisors):
  comprimes = [1]
  c = 2
  for i in divisors[1:]: 
    for j in divisors[c:]:
      if (len(getDivisors(i, j)) == 1):
        comprimes.append(i)
        comprimes.append(j)
    c += 1
  return set(comprimes)


num = [int(x) for x in input().split()]
a, b = num[0], num[1]

# print("Getting primes")
def isPrime(x):
  # print(int(math.sqrt(x)))
  for i in range(2, int(math.sqrt(x))+1):
    # print(i)
    if(x%i==0):
      # print(x, i)
      return False
  return True

count = 0
for x in getCoprime(getDivisors(a, b)):
  if (isPrime(x)):
    count += 1

print(count)
#print("count: "+str(count))

Submission status: Time Limit Exceeded

Solution code:
import copy

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)
# print(cd)
stop_pos = len(cd) + 1
for i in range(0, len(cd) + 1):
    if i > stop_pos:
        break
    for j in range(i + 1, len(cd)):
        tmp = gcd(cd[i], cd[j])
        # print(str(cd[i]) + ', ' + str(cd[j]) + ' , ' + str(tmp))
        if tmp != 1:
            # print(str(cd[i]) + ', ' + str(cd[j]) + ' , ' + str(tmp))
            stop_pos = max(i,j)
            ans.discard(max(cd[i], cd[j]))
print(len(ans))
# print(len(cd))

Submission status: Time Limit Exceeded

Solution code:
A,B = map(int,input().split())
import numpy as np
def seachPrimeNum(N):
  max_ = int(np.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  if len(seachList) == 0:
    return 0
  while seachList[0] <= max_:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

p_list = []
max_n = max(A,B)
min_n = min(A,B)
list_ = seachPrimeNum(min_n)
if list_ == 0:
  print(1)
else:
  for i in list_:
    if A%i == 0 and B%i == 0:
      p_list.append(i)
  print(len(p_list)+1)

Submission status: Time Limit Exceeded

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

i = 1
result = 0
while i<=a and i<=b:
    if a%i == 0 and b%i == 0:
        result += 1
        if i > 1:
            while a%i==0 and b%i==0:
                a//=i
                b//=i
    i += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
import fractions
a,b = map(int, input().split())
g = fractions.gcd(a,b)
ans = 1
if g == 2:
  ans += 1
elif g > 2 and g%2 == 0:
  ans += 1
  while True:
    g //= 2
    if g%2 != 0:
      break
      
if g == 3:
  ans += 1
elif g > 3 and g%3 == 0:
  ans += 1
  while True:
    g //= 3
    if g%3 != 0:
      break

      
if g == 5:
  ans += 1
elif g > 5 and g%5 == 0:
  ans += 1
  while True:
    g //= 5
    if g%5 != 0:
      break
      
      
if g == 7:
  ans += 1
elif g > 7 and g%7 == 0:
  ans += 1
  while True:
    g //= 7
    if g%7 != 0:
      break

      
if g == 11:
  ans += 1
elif g > 11 and g%11 == 0:
  ans += 1
  while True:
    g //= 11
    if g%11 != 0:
      break

if g == 13:
  ans += 1
elif g > 13 and g%13 == 0:
  ans += 1
  while True:
    g //= 13
    if g%13 != 0:
      break

if g >= 17:
  for i in range(3, g+1):
    if g%i == 0:
      for j in range(2, i):
        if i%j == 0:
          break
      else:
        ans += 1
  print(ans)
else:
  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 = [1]
    for i in range(2, min(a, b) + 1):
        if a % i == 0 and b % i == 0:
            if debug:
                log(i)

            added = True
            for j in result[1:]:
                if i % j == 0:
                    added = False
                    break                

            if added:
                result.append(i)

    if debug:
        log("result=%s" % result)

    return len(result)


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:
def solve():
    A, B = map(int, input().split())

    C = max(A, B) // 2

    cnt = 1
    primeNum = []
    for i in range(3, C + 1, 2):
        if A % i == 0 and B % i == 0:
            if isPrime(i, primeNum):
                primeNum.append(i)
                cnt += 1

    if A % 2 == 0 and B % 2 == 0:
        cnt += 1
    
    print(cnt)
        

def isPrime(num, primeNum):
    for n in primeNum:
        if num % n == 0:
            return False
        
    
    return True


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

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

if a==1 or b==1:
    print(1)
else:
    while num!=1:
        if num%count==0:
            ans+=1
            while num%count==0:
                num= num/count
            count+=1
        else:
            count+=1
    print(ans)

Submission status: Time Limit Exceeded

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

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

from collections import deque
CommonDivs.reverse()
q = deque(CommonDivs)
ans = [q.pop()]
max_n = max(CommonDivs)
while len(q) > 0:
    a = q.pop()
    ans.append(a)
    if max_n/2 < a:
        break
    for _ in range(len(q)):
        b = q.pop()
        if b % a != 0:
            q.appendleft(b)
            
print(len(ans)+len(q))

Submission status: Time Limit Exceeded

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


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


list = [1]
if a % 2 == 0 and b % 2 == 0:
    list.append(2)

for i in range(3, min(a, b) + 1, 2):
    if a % i == 0 and b % i == 0:
        list.append(i)
cnt = 0


for i in list:
    if is_prime(i):
        cnt += 1
print(cnt + 1)

Submission status: Time Limit Exceeded

Solution code:
import math
a, b = list(map(int, input().split(' ')))
def gcd(l, s):
    return s if l % s == 0 else gcd(s, l % s)
g = gcd(a, b)
primes = []
if g % 2 == 0:
    primes.append(2)
def prime(n):
    for i in range(len(primes)):
        if n % primes[i] == 0:
            return False
    return True
def make():
    for i in range(3, g + 1, 2):
        if prime(i):
            primes.append(i)

make()

print(len([i for i in primes if g % i == 0]) + 1)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b):
  while b!=0:
    a,b=b,a%b
  return a
def cul(a, b):
  return [i for i in range(1,min(a,b)+1) if a%i==0 and b%i==0]

a, b = list(map(int, input().split()))
cf = cul(a, b)
n = len(cf)
c = 0
for i in range(0, n):
  d = 0
  for j in range(0, i):
    if gcd(cf[i], cf[j])!=1:
      d = 1
      break
  	
  if d==0:
    c+=1
print(c)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	A,B = inputMap()
	ans = 0

	lin = cf(A,B)
	lin.append(1)
	#lin.sort()

	ans = 0
	for i, val in enumerate(lin):
		if is_prime(val):
			ans += 1

	print(ans)

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 is_prime(n):
    i = 2
    while i * i <=n:
        if n % i == 0:
            return False
        i += 1
    return True

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import fractions

def coprime2(a, b):
    return fractions.gcd(a, b) == 1

A,B = map(int, input().split())
num_set = set()
i=2
while True:
    if(A%i==0 and B%i==0):
        num_set.add(i)
        A = A//i
        B = B//i
        if(coprime2(A,B)==1):
            break
    else:
        i = i+1
print(len(num_set)+1)

Submission status: Time Limit Exceeded

Solution code:
a, b = map(int, input().split())
import fractions
n = fractions.gcd(a, b)
devide = 2
l1 = []
while devide <= n:
    while n % devide == 0:
        n = n / devide
        l1.append(devide)
    devide += 1
l1 = list(set(l1))
print(int(len(l1) + 1))

Submission status: Time Limit Exceeded

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

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

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

def coprime(a, b):
    return gcd(a, b) == 1
  
num = cf(a,b)
num_2 = [1,2]
for n in num:
    if not n %2 == 0:
        num_2.append(n)
if len(num_2) == 2:
    print(1)
else:
    ans_num = []
    m_n = len(num_2)
    for i in range(m_n):
        if i == m_n:
            break
        else:
            for j in range(i+1,m_n):
                if coprime(num_2[i],num_2[j]):
                    ans_num.append(num_2[i])
                    ans_num.append(num_2[j])
                else:
                    ans_num.remove(num_2[j])
    print(len(set(ans_num)))

Submission status: Time Limit Exceeded

Solution code:
A, B = map(int,input().split())
C = abs(A-B) if A != B else A

while A%C != 0 and B%C != 0:
  if A < B:
    B = C
  else:
    A = C
  C = abs(A-B)

i = 2
ans = 1
while C > 1:
  if C%i == 0:
    ans += 1
    while C%i == 0:
      C //= i
  i += 1

print(ans)

Submission status: Time Limit Exceeded

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


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

import math
from fractions import gcd

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

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

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

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

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

prime = get_sieve_of_eratosthenes(g)
phash = {}
for p in prime:
    phash[p] = True

#print(prime)
#print(phash)

print( len(set(ggg) & set(prime)) +1 )

Submission status: Time Limit Exceeded

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

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

list = cf(a,b)
#print(list)                                                                   
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
count = 0

for i in list:
    if is_prime(i):
        count += 1

print(count+1)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
def f(n):
    tmp = n
    cnt = 0
    for i in range(2,n//1 + 1):
        if tmp < i:
            break
        if tmp % i == 0:
            cnt += 1
            while tmp % i == 0:
                tmp //= i
    if cnt == 0 and tmp != 1:
        cnt += 1
    return cnt

A, B = map(int, input().split())
g = gcd(A, B)
ans = f(g) + 1
print(ans)

Submission status: Time Limit Exceeded

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


c = cf(a, b)
d = []
for i in range(len(c)):
    for j in range(1, i):
        if c[i] % c[j] == 0:
            d.append(c[i])
            break
print(len(c) - len(d))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

def answer():
    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, b = map(int, input().split())
    g = gcd(a, b)
    divisors = make_divisors(g)
    set_divisors = set(divisors)

    for div1 in divisors[1:]:
        for div2 in divisors[1:]:
            item = div1*div2
            if item in set_divisors:
                set_divisors.remove(item)

    print(len(set_divisors))


if __name__ == '__main__':
    answer()

Submission status: Time Limit Exceeded

Solution code:
a,b=map(int,input().split())
l=[]
for i in range(2,min(a,b)+1):
    if a%i==0 and b%i==0: l.append(i)
cnt=len(l)+1
for i in range(1,len(l)+1):
    for j in range(len(l)-i):
        if l[-i]==l[j]: continue
        if l[-i]%l[j]==0: 
            cnt-=1
            break
print(cnt)

Submission status: Time Limit Exceeded

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

while b:
    a,b = b,a%b
g = a


if g == 1:
    print(1)
else:
    cnt = 1
    for i in range(2, g+1):
        if g % i == 0:
            cnt += 1
            while g % i == 0:
                g = g/i
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	A,B = inputMap()
	ans = 0

	lin = cf(A,B)
	lin.append(1)
	lin.sort()

	ans = 0
	for i, val in enumerate(lin):
		if is_prime(val):
			ans += 1

	print(ans)

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 is_prime(n):
    i = 2
    while i * i <=n:
        if n % i == 0:
            return False
        i += 1
    return True

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

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

factors = list()
f = 1
for f in range(1, (min_v//2)+1) :
    if A % f:
        pass
    elif B % f:
        pass
    else:
        factors.append(f)
    f += 1

prime_map = {0: False, 1: False, 2: True, 3: True, 4: False, 5: True, 6: False}
def is_prime(n):
    if n in prime_map:
        pass
    elif (n % 2) == 0:
        prime_map[n] = False
    else:
        for i in range(3, (n//2), 2):
            if (n % i) == 0:
                prime_map[n] = False
                break
        else:
            prime_map[n] = True
    
    return prime_map[n]

prime_factors_count = 0
for f in factors:
    if is_prime(f):
        prime_factors_count += 1

print(prime_factors_count + 1)

Submission status: Time Limit Exceeded

Solution code:

def sieve(n):
    nums = [i+1 for i in range(2, n, 2) if (i+1) % 3 != 0 and (i+1) % 5 !=0] # リスト内包表記で3,5の倍数をはじく
    ans = [2,3,5] # 3,5は素数なので加えてしまう
    while nums[0] <= n**0.5:
        for i in range(nums[0]**2, nums[-1]+1, nums[0]):
            if i in nums: nums.remove(i)
            ans.append(nums.pop(0))
            ans += nums
    return ans


A,B =map(int,input().split())
if A<B:
    A,B =B,A
foo = 1
while foo != 0:
    A,B = B, A%B
    #print(A,B)
    foo = B

foo =A

plis = sieve(1000)
ans = 1
for p in plis:
    if foo%p==0:
        ans += 1
        foo = foo//p
    while foo%p ==0:
        foo = foo//p



plis = sieve(max(7,foo))

for p in plis:
    if  foo % p ==0:
        ans += 1
        foo = foo//p
        if foo < 1:
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions

A, B = map(int, input().split())
list = []
for i in range(1, min(A, B) + 1):
    if A % i == 0 and B % i == 0:
        list.append(i)

stack = []
for element in list:
    break_flg = False
    for stack_element in stack:
        gcd = fractions.gcd(element, stack_element)
        if gcd != 1:
            break_flg = True
            break
    if break_flg == False:
        stack.insert(0, element)
    break_flg = True

print(len(stack))

Submission status: Time Limit Exceeded

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

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

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

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

g = divisor(gcd(A,B))
#g.sort()

cnt = 0
for i in g:
    if len(divisor(i)) <= 2:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math

A,B=map(int,input().split())
min=min(A,B)
#rng=math.ceil(math.sqrt(max))
divisor=[1]
for i in range(2,min+1):
    if A%i==0 and B%i==0:
        for x in divisor:
            if i%x==0 and x!=1:
                break
        else:
            divisor+=[i]

print(len(divisor))

Submission status: Time Limit Exceeded

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

if a > b:
    c = b
    d = a
else:
    c = a
    d = b

i = 2
ans = 1 
incre = True
while True:
    while c % i == 0 and d % i == 0:
        c /= i
        d /= i
        if incre:
            ans += 1
            incre = False
    incre = True
    if i > c / 2:
        break
    i += 1

if d%c == 0 and c > 1:
    ans += 1
    

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
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 using_sqrt(limit):
    n = 0
    for k in range(2, limit+1):
        factor = 0
        
        # 2以外の偶数は素数ではないので無視する
        if k % 2 == 0 and k != 2:
            continue
        
        # 繰り返しの上限を対象の平方根にする
        for divisor in range(2, math.floor(math.sqrt(k))+1):
            if k % divisor == 0:
                factor += 1
                
        if factor == 0:
            n += 1
            
    return n

l = cf(A, B)

cnt = 0
for i in range(len(l)):
  if using_sqrt(l[i]) <= 2:
    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

a,b = map(int, input().split())
cd = cf(a,b)
count = 0

for i in cd:
    if is_prime(i):
        count += 1

print(count + 1)

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions
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 is_prime(num):
    for i in range(2, num):  # 第二引数は sqrt(num)+1 でも良い
        if num % i == 0:
            return False

    return True

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

g = fractions.gcd(A, B)

# print(g)
div = make_divisors(g)
# print(div)
p = [i for i in div if is_prime(i)]
# print(p)
print(len(p))
# 2

Submission status: Time Limit Exceeded

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

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 is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1


lis_ab = cf(a,b)
for i in lis_ab:
    if is_prime(i):
        cnt = cnt+1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math


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 isPrime(num):
    if num == 1 or num == 2:
        return True
    elif num % 2 == 0:
        return False

    for i in range(3, math.floor(math.sqrt(num))+1, 2):
        if num % i == 0:
            return False

    return True


def main():
    A, B = map(int, input().split())
    X = cf(A, B)
    ans = 0
    for i in X:
        ans += isPrime(i)
    print(ans)


if __name__ == '__main__':
    main()

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

cfList = cf(a, b)
Comb = itertools.combinations
ans = [cfList[0]]
for l in cfList[1:]:
    l2 = l
    flg = True
    for i in ans:
        temp = cf(l2, i)
        if len(temp) != 1 or temp[0] != 1:
            flg = False
            break
    if flg:
        ans.append(l2)


print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import fractions
a,b = map(int, input().split())
g = fractions.gcd(a,b)
ans = 1
if g == 2:
  ans += 1
elif g > 2 and g%2 == 0:
  ans += 1
  while True:
    g //= 2
    if g%2 != 0:
      break
      
if g >= 3:
  for i in range(3, g+1):
    if g%i == 0:
      for j in range(2, i):
        if i%j == 0:
          break
      else:
        ans += 1
  print(ans)
else:
  print(ans)

Submission status: Time Limit Exceeded

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

if a < b:
    a, b = b, a
while a % b != 0:
    a, b = b, a % b
# print(b)

n = b
a = []

while n % 2 == 0:
  if 2 not in a:
    a.append(2)
  n //= 2
f = 3
while n > 1:
  if n % f == 0:
    if f not in a:
      a.append(f)
    n //= f
  else:
    f += 2

N = len(a)

# print(a)
print(N+1)

Submission status: Time Limit Exceeded

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

cf=[1]
for i in range(2,min(a,b)+1):
    if a%i==0 and b%i==0:
        cf.append(i)
n=len(cf)
dele=[]
for i in range(n-1):
    flag=0
    for j in range(i+1,n):
        if fractions.gcd(cf[i],cf[j])!=1:
            dele.append(cf[j])
result=set(cf)-set(dele)
print(len(result))

Submission status: Time Limit Exceeded

Solution code:
import itertools as it
from fractions import gcd as mygcd
a,b=map(int,input().split())
l=[]
for i in range(2,min(a,b)+1):
    if a%i==0 and b%i==0: l.append(i)
cnt=len(l)+1
for i in range(1,len(l)+1):
    for j in range(len(l)-i):
        if l[-i]==l[j]: continue
        if mygcd(l[-i],l[j])!=1: 
            cnt-=1
            break
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def is_prime(num):
    if num<2:
        return False
    if num==2 or num==3:
        return True
    for i in range(2,int(num**0.5)+1):
        if num%i==0:
            return False
    return True
 
def main():
    a,b=map(int,input().split())
    s,l=min(a,b),max(a,b)
    #sの約数のうち、素数を求める。
    s_sub=s
    #s_prime=[1]
    i=2
    ans=1
    while i<=s_sub:
        if s%i==0:
            if is_prime(i):
                if l%(i)==0:
                    ans+=1
                #s_prime.append(i)
                if is_prime(s//i):
                    if l%(s//i)==0:
                        ans+=1
                s_sub=s//i-1
        i+=1
        
    print(ans)
    
main()

Submission status: Time Limit Exceeded

Solution code:
# D
import math
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 coprime(a, b):
    return len(cf(a, b)) == 1

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
ans = 0
for i in cf(A,B):
    if (is_prime(i)):
        ans += 1
print(ans+1)

Submission status: Time Limit Exceeded

Solution code:


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

import math
from fractions import gcd

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

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

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

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

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

prime = get_sieve_of_eratosthenes(g)
phash = {}
for p in prime:
    phash[p] = True

#print(prime)
#print(phash)

count = 0
for c in ggg:
    if c in phash:
        count += 1


print(count+1)

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions
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 is_prime(num):
    for i in range(2, num):  # 第二引数は sqrt(num)+1 でも良い
        if num % i == 0:
            return False

    return True

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

g = fractions.gcd(A, B)

# print(g)
div = make_divisors(g)
# print(div)
p = [i for i in div if is_prime(i)]
# print(p)
print(len(p))
# 2

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))
for i in range(1,g[0]):
    if not a%i and not b%i:
        g.append(i)
g.append(g[0])
l = len(g)
c = 0
for i in range(2,l-1):
    for j in range(i+1,l):
        if g[i] != 0 and not g[j]%g[i]:
            g[j]=0
for i in range(1,l):
    if g[i]!=0:
        c+=1
print(c)