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
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)
            primes[factor] += 1

            n //= factor

        return primes

      
class FutureMath:
    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

    def gcd_(self, list):
        result = list[0]
        for el in list[1:]:
            result = self.gcd(result, el)
        return result

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

    def lcm_(self, list):
        result = list[0]
        for el in list[1:]:
            result = self.lcm(result, el)
        return result

    def divisors(self, n):
        result = list()
        for i in range(1, n+1):
            if n % i == 0:
                result.append(i)
        return result

fm = FutureMath()

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

prime = Prime()
primes = prime.find_factors(gcd)


print(len(primes) + 1)

Submission status: Time Limit Exceeded

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

s = []
m = int(min(a,b)/2)
if m == 0:
    print(1)
else:
    for i in range(1,m):
        if a%i == 0 and b%i == 0:
            if s == [] or s == [1]:
                s.append(i)
            else:
                p = 0
                for c in s[1:]:
                    if i%c == 0:
                        p = 1
                        break
                if p == 1:
                    p = 0
                else:
                    s.append(i)
                    p = 0

    print(len(s))

Submission status: Time Limit Exceeded

Solution code:
from math import log
def gcd(a,b):
    if a<b: a,b=b,a
    while b: a,b = b, a%b
    return a
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)

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)

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

def generateCoprimeSets(sofar, divisors):
	if divisors == []:
		return [sofar]
	done = generateCoprimeSets(sofar, divisors[1:])
	# print(done)
	for i in range(len(divisors)):
		d = divisors[i]
		is_invalid = False
		for s in sofar:
			if not is_coprime(d,s):
				is_invalid = True
				break
		if is_invalid:
			continue
		done.extend(generateCoprimeSets(sofar + [d], divisors[i+1:]))
	return done

print(len(max(generateCoprimeSets([],divisors),key=len)))

Submission status: Time Limit Exceeded

Solution code:
def cf(x1, x2):
    _cf = {}
    _cf_max = 0
    for i in range(2, min(x1, x2) + 1):
        if x1 % i == 0 and x2 % i == 0:
            _cf[i] = True
            _cf_max = max(_cf_max, i)
    return _cf, _cf_max


def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


a, b = list(map(int, input().split()))
cf_dict, cf_max = cf(a, b)
if len(cf_dict) > 0:
    prime_list = primes(cf_max)
else:
    prime_list = []
cnt = 1
for p in prime_list:
    if p in cf_dict:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
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
        i =2
    elif(A ==i or B == i):
        break
    else:
        i = i+1
print(len(num_set)+1)

Submission status: Time Limit Exceeded

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

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

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

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

if gcd(A,B)==1:
    print(1)
else:
    N=gcd(A,B)
    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)
    ans=0
    y=yakusuu(N)
    for i in range(len(y)):
        if y[i] in P:
            ans+=1
    print(ans)

Submission status: Time Limit Exceeded

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

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
def divisor(n): #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
def is_prime(n):
  for p in range(2, n):
    if n % p == 0:
      return False
  return True
cnt = 0
for i in divisor(gcd(a,b)):
  if is_prime(i):
    cnt += 1
print(cnt)

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 < 2000000:
        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:
import numpy as np
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
import random
from itertools import permutations, combinations

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:

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())

plis = sieve(max(7,min(A,B)))

ans = 1
for p in plis:
    if A%p +B%p ==0:
        ans += 1
        A = A//p
        B = B//p
        if min(A,B) == 1:
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
A, B = map(int,input().split())
D = 2
ans = 1
A_l = []
B_l = []
while True:
    if A % D == 0:
        while True:
            if A % D != 0:
                break
            A //= D
        A_l.append(D)
    if B % D == 0:
        while True:
            if B % D != 0:
                break
            B //= D
        B_l.append(D)
    if A == B == 1:
        break
    D += 1
for a in A_l:
    if a in B_l:
        ans += 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(2,min(x1,x2)+1):
    if x1 % i == 0 and x2 % i == 0:
      cf.append(i)
  return cf

Oks = []
for cand in cf(a,b):
  for div in Oks:
    if cand % div == 0:
      break
  else:
    Oks.append(cand)
print(len(Oks) + 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:
        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 fractions

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

# 1は絶対入る
cd = [1]
answer = 1
for i in range(2, min(A, B)):
    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:
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

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

c = 0
for i in range(1,min(a,b)+1):
	if a % i == 0 and b % i == 0:
		if is_prime(i):
			c+=1			
		#cd_n.append(i)
print(c)

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 < 2000000:
        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 math.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):
    while b != 0:
        a, b = b, a % b
    return a


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


if __name__ == '__main__':
    A, B = map(int, input().split())
    A = min(A, B)
    B = max(A, B)
    ans = set()
    for i in range(1, A+1):
        if A % i == 0 and B % i == 0:
            flag = True
            for a in ans:
                if gcd(i, a) != 1:
                    flag = False
                    break
            if flag:
                ans.add(i)
    print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
def gcd(a,b):
    if a < b:
        a, b = b, a
    while b >= 1:
        a, b = b, a % b
    return a

def shave(n):
    n_root = int(n**0.5)
    candidate = [i for i in range(3,n+1,2)]
    for i in range(3,n_root+2,2):
        candidate = [ j for j in candidate if j == i or j % i != 0]   
    candidate = [2] + candidate
    return candidate

x, y = [ int(v) for v in input().split() ]

gcd1 = gcd(x, y)
prime_list = shave(gcd1)

ans = 1
for i in prime_list:
    if gcd1 % i == 0:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

cn=1

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

for i in range(2,min(a,b)+1):
    if a % i == 0 and b % i == 0:
        if is_prime(i)==True:
            cn+=1

print(cn)