Problem:


Score : 400 points

Problem Statement

Given are positive integers A and B.

Let us choose some number of positive common divisors of A and B.

Here, any two of the chosen divisors must be coprime.

At most, how many divisors can we choose?

Definition of common divisor

An integer d is said to be a common divisor of integers x and y when d divides both x and y.

Definition of being coprime

Integers x and y are said to be coprime when x and y have no positive common divisors other than 1.

Definition of dividing

An integer x is said to divide another integer y when there exists an integer \alpha such that y = \alpha x.

Constraints

All values in input are integers.

1 \leq A, B \leq 10^{12}

Input

Input is given from Standard Input in the following format:

A B

Output

Print the maximum number of divisors that can be chosen to satisfy the condition.

Sample Input 1

12 18

Sample Output 1

3

12 and 18 have the following positive common divisors: 1, 2, 3, and 6.

1 and 2 are coprime, 2 and 3 are coprime, and 3 and 1 are coprime, so we can choose 1, 2, and 3, which achieve the maximum result.

Sample Input 2

420 660

Sample Output 2

4

Sample Input 3

1 2019

Sample Output 3

1

1 and 2019 have no positive common divisors other than 1.



Sample input:
12 18


Sample output:
3

Submission status: Time Limit Exceeded

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


class Prime:
    seed_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

    def is_prime(self, n):
        """
        prime test (hybrid)

        see also: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """
        is_prime_common = self.is_prime_common(n)
        if is_prime_common is not None:
            return is_prime_common

        if n < 2000000:
            return self.is_prime_brute_force(n)
        else:
            return self.is_prime_miller_rabin(n)

    def is_prime_common(self, n):
        if n == 1: return False
        if n in Prime.seed_primes: return True
        if any(map(lambda x: n % x == 0, self.seed_primes)): return False

    def is_prime_brute_force(self, n):
        """
        brute force prime test
        use with is_prime_common if you want to skip seed_primes

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

    def is_prime_miller_rabin(self, n):
        """
        miller rabin prime test
        use with is_prime_common if you want to skip seed_primes

        see also
            algorithm: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
            implementation: https://qiita.com/srtk86/items/609737d50c9ef5f5dc59
            improvement: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """

        d = n - 1
        while d & 1 == 0:
            d >>= 1

        # use one of these lines / upper is more efficient.
        witnesses = self.get_witnesses(n)
        # witnesses = [random.randint(1, n - 1) for _ in range(100)]

        for w in witnesses:
            y = pow(w, d, n)

            while d != n - 1 and y != 1 and y != n - 1:
                y = (y * y) % n
                d <<= 1

            if y != n - 1 and d & 1 == 0:
                return False

        return True

    def get_witnesses(self, num):
        def _get_range(num):
            if num < 2047:
                return 1
            if num < 1373653:
                return 2
            if num < 25326001:
                return 3
            if num < 3215031751:
                return 4
            if num < 2152302898747:
                return 5
            if num < 3474749660383:
                return 6
            if num < 341550071728321:
                return 7
            if num < 3825123056546413051:
                return 9
            return 12

        return self.seed_primes[:_get_range(num)]

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

    @staticmethod
    def f(x, n, seed):
        """
        pseudo prime generator
        :param x:
        :param n:
        :param seed:
        :return: pseudo prime
        """
        p = Prime.seed_primes[seed % len(Prime.seed_primes)]
        return (p * x + seed) % n

    def find_factor(self, n, seed=1):
        """
        find one of factor of n
        this function is based to Pollard's rho algorithm

        see also
            algorithm: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
            implementation: https://qiita.com/gushwell/items/561afde2e00bf3380c98

        :param n:
        :param seed:
        :return: factor
        """
        if self.is_prime(n):
            return n

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

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

    def find_factors(self, n):
        primes = {}
        if self.is_prime(n):
            primes[n] = 1
            return primes

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

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

            n //= factor

        return primes


prime = Prime()
_gcd = prime.gcd(a, b)
fact_dict = prime.find_factors(_gcd)
print(len(fact_dict.keys()) + 1)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import math

def prime(x):
  if x==2:
    return True
  else:
      for j in range(2,math.ceil(math.sqrt(x))+1):
        if x%j==0:
          return False
          break
        else:
          pass
      else:
        return True
  
a,b = map(int,input().split())
ab = gcd(a,b)
cnt = 0
for i in range(1,ab+1):
  if ab%i==0:
    if prime(i):
      cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

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

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]]
    return table
    
table = sieve(max_gcd)

def cf(x,y):
    number = [1]
    for i in table:
        if x%i == 0 and y%i == 0:
            number.append(i)
        if i > max_gcd:
            break
    return number

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

s = cf(a,b)
cnt = 1
for i in s:
    t = is_prime(i)
    if t == True:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

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

n=min(a,b)
is_prime=[True]*(n+1)
is_prime[0],is_prime[1]=False,False
for i in range(2,int(n**0.5)+1):
    if not is_prime[i]:continue
    for j in range(i*2,n+1,i):
        is_prime[j]=False
prime=[i for i in range(n+1) if is_prime[i]]

number=prime
answer=cf
flag=0
count=1
for i in answer:
    if i==number[flag]:
        count +=1
        flag +=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import math

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

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

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

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

y = cf(A,B)

cnt = 0
for yi in y:
    if is_prime(yi):
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# 最大公約数GCD(x,y)
def GCD(x,y):
    x,y=max(x,y),min(x,y)
    if x%y==0:
        return y
    else:
        return GCD(y,x%y)

def divide(g,p):
    if g%p!=0:
        return g
    if g%p==0:
        global n
        n+=1
        while g%p==0:
            g//=p
        return g

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

n=1 # gの素因数の個数

if g>=2:
    g=divide(g,2)
p=3 # 最初の奇素数
while g>1:
    g=divide(g,p)
    p+=2
print(n)

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
cm=cf(a,b)
cnt=1
z=len(cm)
for j in range(z):
  for k in range(j+1,z):
    if cm[k]*cm[j]!=0 and cm[k]%cm[j]==0:
      cm[k]=0
cm=list(set(cm))
if 0 in cm:
  cm.remove(0)
print(len(cm)+1)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a,b):
	if a==0:
		return(b)
	return(gcd(b%a,a))
a,b=map(int,input().split())
g=gcd(a,b)
divide=2

ans=1
while(g!=1):
	if g%divide==0:
		ans+=1
		while(g%divide==0):
			g//=divide
	else:
		divide+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import random


class Prime:
    seed_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

    def is_prime(self, n):
        """
        prime test (hybrid)

        see also: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """
        is_prime_common = self.is_prime_common(n)
        if is_prime_common is not None:
            return is_prime_common

        if n < 2000000:
            return self.is_prime_brute_force(n)
        else:
            return self.is_prime_miller_rabin(n)

    def is_prime_common(self, n):
        if n == 1: return False
        if n in Prime.seed_primes: return True
        if any(map(lambda x: n % x == 0, self.seed_primes)): return False

    def is_prime_brute_force(self, n):
        """
        brute force prime test
        use with is_prime_common if you want to skip seed_primes

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

    def is_prime_miller_rabin(self, n):
        """
        miller rabin prime test
        use with is_prime_common if you want to skip seed_primes

        see also
            algorithm: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
            implementation: https://qiita.com/srtk86/items/609737d50c9ef5f5dc59
            improvement: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """

        d = n - 1
        while d & 1 == 0:
            d >>= 1

        # use one of these lines / upper is more efficient.
        witnesses = self.get_witnesses(n)
        # witnesses = [random.randint(1, n - 1) for _ in range(100)]

        for w in witnesses:
            y = pow(w, d, n)

            while d != n - 1 and y != 1 and y != n - 1:
                y = (y * y) % n
                d <<= 1

            if y != n - 1 and d & 1 == 0:
                return False

        return True

    def get_witnesses(self, num):
        def _get_range(num):
            if num < 2047:
                return 1
            if num < 1373653:
                return 2
            if num < 25326001:
                return 3
            if num < 3215031751:
                return 4
            if num < 2152302898747:
                return 5
            if num < 3474749660383:
                return 6
            if num < 341550071728321:
                return 7
            if num < 3825123056546413051:
                return 9
            return 12

        return self.seed_primes[:_get_range(num)]

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

    @staticmethod
    def f(x, n, seed):
        """
        pseudo prime generator
        :param x:
        :param n:
        :param seed:
        :return: pseudo prime
        """
        p = Prime.seed_primes[seed % len(Prime.seed_primes)]
        return (p * x + seed) % n

    def find_factor(self, n, seed=1):
        """
        find one of factor of n
        this function is based to Pollard's rho algorithm

        see also
            algorithm: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
            implementation: https://qiita.com/gushwell/items/561afde2e00bf3380c98

        :param n:
        :param seed:
        :return: factor
        """
        if self.is_prime(n):
            return n

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

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

    def find_factors(self, n):
        primes = {}
        if self.is_prime(n):
            primes[n] = 1
            return primes

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

        return primes

prime = Prime()

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

print(len(primes) + 1)

Submission status: Time Limit Exceeded

Solution code:

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

import math
from fractions import gcd

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

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

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

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

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

#print(prime)
#print(phash)

ggg = set()
for i in range(1, g):
    for j in range(i+1, g+1):
        if A%i == 0 and B%i == 0 and A%j == 0 and B%j == 0:
            if i in phash:
                ggg.add(i)
            if j in phash:
                ggg.add(j)

# 1 の分を +1
print(len(ggg)+1)

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt, ceil

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

count = 1
primes = [2]

for i in range(3, ceil(sqrt(min(A, B))), 2):
    for j in primes:
        if i % j == 0:
            break
    else:
        primes.append(i)

for i in primes:
    if A % i == B % i == 0:
        count += 1
if count == 1 and min(A, B) != 1 and max(A, B) % min(A, B) == 0:
    count += 1

print(count)

Submission status: Time Limit Exceeded

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


def comdiv(n, m):
    cds = []  # exclude 1
    for i in range(2, min(n, m) + 1):
        if n % i == 0 and m % i == 0:
            cds.append(i)

    return sorted(cds)


def main(a, b):
    cds = comdiv(a, b)
    cand = set()

    for cd in cds:
        if len(cand) == 0:
            cand.add(cd)
            continue
        if all([cd % x != 0 for x in cand]):
            cand.add(cd)

    return len(cand) + 1


print(main(a, b))

Submission status: Time Limit Exceeded

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

def make_divisors(a, b):
    n = min(a, b)
    m = max(a, b)
    import math
    divisors = []
    for i in range(2, n + 1):
        if n == 0:
            break
        if n % i == 0: #割り切れるとき
            if m % i == 0:
                divisors.append(i)
            while n % i == 0 and n != 1:
                n //= i
            if n == 1:
                break
    divisors.sort()
    return divisors

lst = make_divisors(A, B) #この中から素数を数えたらいい
print (len(lst) + 1)

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

cd = []

for i in range(1, min(A, B) + 1):
    if A % i == 0 and B % i == 0:
        if i % 2 == 0 and i != 2:
            continue
        if i % 3 == 0 and i != 3:
            continue
        if i % 5 == 0 and i != 5:
            continue
        if i % 7 == 0 and i != 7:
            continue
        if i % 11 == 0 and i != 11:
            continue
        if i % 13 == 0 and i != 13:
            continue
        cd.append(i)

l = []

for i in range(0, len(cd)):
    c = cd[i]
    if not l:
        l.append(c)
    else:
        join = True
        for j in range(0, len(l)):
            k = l[j]
            if fractions.gcd(c, k) != 1:
                join = False
                break
        if join:
            l.append(c)

print(len(l))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(20000000)
a, b = [int(i) for i in input().split()]
def gcd(a, b):
    _min = min(a,b)
    _max = max(a,b)
    while True:
        _max = _max % _min
        if _max == 0:
            return _min
        else:
            tmp = _min
            _min = _max
            _max = tmp

_gcd = gcd(a, b)
import math

class Prime:
    seed_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

    def is_prime(self, n):
        """
        prime test (hybrid)

        see also: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """
        is_prime_common = self.is_prime_common(n)
        if is_prime_common is not None:
            return is_prime_common

        if n < 2000000:
            return self.is_prime_brute_force(n)
        else:
            return self.is_prime_miller_rabin(n)

    def is_prime_common(self, n):
        if n == 1: return False
        if n in Prime.seed_primes: return True
        if any(map(lambda x: n % x == 0, self.seed_primes)): return False

    def is_prime_brute_force(self, n):
        """
        brute force prime test
        use with is_prime_common if you want to skip seed_primes

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

    def is_prime_miller_rabin(self, n):
        """
        miller rabin prime test
        use with is_prime_common if you want to skip seed_primes

        see also
            algorithm: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
            implementation: https://qiita.com/srtk86/items/609737d50c9ef5f5dc59
            improvement: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """

        d = n - 1
        while d & 1 == 0:
            d >>= 1

        # use one of these lines / upper is more efficient.
        witnesses = self.get_witnesses(n)
        # witnesses = [random.randint(1, n - 1) for _ in range(100)]

        for w in witnesses:
            y = pow(w, d, n)

            while d != n - 1 and y != 1 and y != n - 1:
                y = (y * y) % n
                d <<= 1

            if y != n - 1 and d & 1 == 0:
                return False

        return True

    def get_witnesses(self, num):
        def _get_range(num):
            if num < 2047:
                return 1
            if num < 1373653:
                return 2
            if num < 25326001:
                return 3
            if num < 3215031751:
                return 4
            if num < 2152302898747:
                return 5
            if num < 3474749660383:
                return 6
            if num < 341550071728321:
                return 7
            if num < 3825123056546413051:
                return 9
            return 12

        return self.seed_primes[:_get_range(num)]

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

    @staticmethod
    def f(x, n, seed):
        """
        pseudo prime generator
        :param x:
        :param n:
        :param seed:
        :return: pseudo prime
        """
        p = Prime.seed_primes[seed % len(Prime.seed_primes)]
        return (p * x + seed) % n

    def find_factor(self, n, seed=1):
        """
        find one of factor of n
        this function is based to Pollard's rho algorithm

        see also
            algorithm: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
            implementation: https://qiita.com/gushwell/items/561afde2e00bf3380c98

        :param n:
        :param seed:
        :return: factor
        """
        if self.is_prime(n):
            return n

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

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

    def find_factors(self, n):
        primes = {}
        if self.is_prime(n):
            primes[n] = 1
            return primes

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

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

            n //= factor

        return primes


prime = Prime()
fact_dict = prime.find_factors(_gcd)
print(len(fact_dict.keys()) + 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest
import math

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """12 18"""
        output = """3"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """420 660"""
        output = """4"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """1 2019"""
        output = """1"""
        self.assertIO(input, output)
def sosuu(N):
    mx = int(math.sqrt(N))
    target = [i for i in range(2,N+1)]
    pN= []
    while len(target)>0 and target[0] <= mx:
        pN.append(target[0])
        tmp = target[0]
        target = [i for i in target if i % tmp != 0]
    pN.extend(target)
    return pN


def resolve():
    (A,B)=(int(i) for i in input().split())
    N=min(A,B)
    count=0
    for i in sosuu(N):
        if A%i ==0 and B%i==0:
            count+=1        
    print(count+1)
    


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# abc142/abc142_d
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    A, B = i2nn()
    ds = set()
    for i in range(2, min(A, B) + 1):
        if A % i == 0 and B % i == 0:
            check(i, ds)
    #print(ds)
    print(len(ds)+1)
    return


def check(n, ds):
    for d in ds:
        if n % d == 0:
            return
    ds.add(n)
    return

main()

Submission status: Time Limit Exceeded

Solution code:
str_list = input().split(' ')
int_list = [int(x) for x in str_list]
A, B = int_list[0], int_list[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

cf = cf(A, B)

count = 0

import numpy as np
cf = np.array(cf)

count = 0
while len(cf) > 0:
    count += 1
    if len(cf)==1:
        break
    x = int( cf[0] )
    cf = cf[np.where( cf%x!=0 )]
print(count+1)

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
    i += 1
    if i > c:
        break

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce


def factors(n):
    return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))


a1, b1 = map(int, input().split())
temp = factors(a1).intersection(factors(b1))
s = set(range(2, max(a1, b1)))
li = []
while s:
    m = min(s)
    li.append(m)
    s -= set(range(m, max(a1, b1)+1, m))
c = 0
for i in temp:
    if i == 1:
        c += 1
    if i in li:
        c += 1
print(c)

Submission status: Time Limit Exceeded

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

def gcd(a, b):
	if b == 0:
		return(a)
	else :
		return gcd(b, a % b)
		
a = gcd(A, B)
ctr = 1

for i in range(2, a + 1):
	do = 0
	while a % i == 0:
		a /= i
		do = 1
		if a == 1:
			break
	if do:
		ctr += 1
	if a == 1:
		break
		
print(ctr)

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

# 1は絶対入る
cd = [1]
answer = 1
if A%2 == 0 and B%2 == 0:
    cd.append(2)
    answer += 1
for i in range(3, fractions.gcd(A, B)+1, 2):
    if A%i == 0 and B%i == 0:
        for j in cd:
            if fractions.gcd(i, j) != 1:
                break
        else:
            cd.append(i)
            answer += 1
            
print(answer)

Submission status: Time Limit Exceeded

Solution code:
A, B = list(int(el) for el in input().split(' '))

set_a=set()
set_b=set()

set_a.add(1)
set_b.add(1)

num=2

while True:
  if A%num == 0:
    A=A//num
    if num not in set_a: set_a.add(num)
  else:
    num+=1
    
  if num >= A+1: break
    
num=2
while True:
  if B%num == 0:
    B=B//num
    if num not in set_b: set_b.add(num)
  else:
    num+=1
    
  if num >= B+1: break

print(len(set_a & set_b))

Submission status: Time Limit Exceeded

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

cf = cf(a,b)

ans = [1] * len(cf)
for i in reversed(range(1,len(cf))):
    for j in range(1,i):
        if cf[i] % cf[j] == 0:
            ans[i] = 0
            break

print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
import fractions
a, b = map(int, input().split())
gcd = fractions.gcd(a, b)
primes = []
for i in range(2, int(gcd) + 1):
    if gcd % i == 0:
        isPrime = True
        for j in range(2, i):
            if i % j == 0:
                isPrime = False
                break
        if isPrime:
            primes.append(i)
print(len(primes) + 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 = set()
for i in range(1, g):
    for j in range(i+1, g+1):
        if A%i == 0 and B%i == 0 and A%j == 0 and B%j == 0:
            ggg.add(i)
            ggg.add(j)

#print(ggg)

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 x in ggg:
    if x in phash:
        count += 1

# 1 の分を +1
print(count+1)