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: Wrong Answer

Solution code:
from fractions import gcd
from collections import defaultdict
def getlist():
	return list(map(int, input().split()))

L = [1 for i in range(100001)]
L[0] = 0
L[1] = 0
plist = []
for i in range(100001):
	if L[i] == 1:
		plist.append(i)
		c = 2
		while True:
			if i * c <= 100000:
				L[i * c] = 0
				c += 1
			else:
				break

#処理
A, B = getlist()
G = gcd(A, B)
D = defaultdict(int)
for i in plist:
	while True:
		if G % i == 0:
			D[i] += 1
			G = G // i
		else:
			break
if G != 1:
	D[G] += 1

ans = len(D) + 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())

from fractions import gcd
a = gcd(n,m)

import numpy as np

def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    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

t = seachPrimeNum(100)

c = 1

for item in t:
    if a % item == 0:
        c += 1

print(c)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

a, b = list(map(int, input().split()))
fct = factorization(gcd(a, b))
if len(fct) > 1:
    fct.append([1, 1])

#print(fct)
print(len(fct))

Submission status: Wrong Answer

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 a % i == 0 and b % i == 0:
        a //= i
        b //= i
        if incre:
            ans += 1
            incre = False
    incre = True
    i += 1
    if i*i > c:
        break


print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    def factorization(n):
        arr = []
        temp = n
        for i in range(2, int(-(-n**0.5//1))+1):
            if temp%i==0:
                cnt=0
                while temp%i==0:
                    cnt+=1
                    temp //= i
                arr.append([i, cnt])
    
        if temp!=1:
            arr.append([temp, 1])
    
        if arr==[]:
            arr.append([n, 1])
        arr = [(i,j) for i,j in arr]
        return arr
    
    a,b = map(int,input().split())
    fa = dict(factorization(a))
    fb = dict(factorization(b))
    fak = set(fa.keys())
    fbk = set(fb.keys())
    print(len(fak&fbk)+1)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from fractions import gcd

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

a, b = list(map(int, input().split()))
fct = factorization(gcd(a, b))
if len(fct) > 1:
    fct.append([1, 1])

print(fct)
print(len(fct))

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

a, b = na()

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

g = gcd(a, b)
ans = 0
for d in range(2,1000001):
    e = 0
    while g % d == 0:
        g //= d
        e += 1
    if e > 0:
        ans += 1
if g > 1:
    ans += 1
print(ans)

Submission status: Wrong Answer

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

A=[1]
B=[1]

for i in range(2,10**6+5):
    if a%i==0:
        A.append(i)
        while a%i==0:
            a//=i
        
for i in range(2,10**6+5):
    if b%i==0:
        B.append(i)
        while b%i==0:
            b//=i

ans=0
for i in range(len(A)):
    if A[i] in B:
        ans+=1
print(ans)

Submission status: Wrong Answer

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 a % i == 0 and b % i == 0:
        a /= i
        b /= i
        if incre:
            ans += 1
            incre = False
    incre = True
    i += 1
    if i*i > c:
        break


print(ans)

Submission status: Wrong Answer

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

divs = set()
m = 2
while m*m <= B:
    if A%m == B%m == 0:
        divs.add(m)
        a = A//m
        b = B//m
        if b%a == 0:
            divs.add(a)
    m += 1

def is_prime(n):
    if n == 2: return True
    if n < 2 or n%2 == 0: return False
    m = 3
    while m*m <= n:
        if n%m == 0: return False
        m += 2
    return True

ans = 0
for d in divs:
    if is_prime(d):
        ans += 1
print(ans+1)

Submission status: Wrong Answer

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

counter = 0
primes = [2, 3]

for n in range(5, math.ceil(math.sqrt(min(a,b))), 2):
    isprime = True
    for i in range(1, len(primes)):
        counter += 1
        if primes[i] ** 2 > n:
            break
        counter += 1
        if n % primes[i] == 0:
            isprime = False
            break
    if isprime:
        primes.append(n)

ans = 1
for i in primes:
    if a%i == 0 and b%i == 0:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:

def divisor(n): #nの約数を全て求める
  i = 2
  table = []
  while i * i <= n:
    if n%i == 0 and sum([i%ti==0 for ti in table])==0:
      table.append(i)
      #table.append(n//i)
      
    i += 1
  table = list(set(table))
  return [1]+table


a,b = map(int, input().split())
if a>b:
  a,b = b,a

a_div = divisor(a)
b_div = divisor(b)
ab_div = [ai for ai in a_div if ai in b_div]

print(len(ab_div))

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

d = gcd(A, B)
d_ori = d
ans = 1
k = 2
while d > 2:
    plus = 0
    while d % k == 0:
        d //= k
        plus = 1
    ans += plus
    k += 1
    if k > d**(1/2):
        ans += 1
        break
print(ans)

Submission status: Wrong Answer

Solution code:


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
    
a,b = [int(x) for x in input().split()]
import fractions
gcd = fractions.gcd(a,b)
factors = factorization(gcd)
print(len(factors)+1)

Submission status: Wrong Answer

Solution code:
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]

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

def gcd(a, b):  # a >= b
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

hoge = gcd(A, B)

ans = 1
i = 2
while i * i <= min(A, B):
    if hoge % i == 0:
        ans += 1
        while hoge % i == 0:
            hoge /= i
    i += 1

print(ans)

Submission status: Wrong Answer

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

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

g = gcd(A, B)
print(g)
primes = []
l = [1]
for i in range(2, g+1):
    # print(l)
    if all(i%p for p in primes):
        primes.append(i)
        if g%i == 0:
            l.append(i)

print(len(l))

Submission status: Wrong Answer

Solution code:
import fractions
import math
def primes(x):
    x+=1
    if x < 2:
        return []

    prime = [i for i in range(x)]
    prime[1] = 0

    for p in prime:
        if p > math.sqrt(x):
            break
        if p == 0:
            continue
        for non_prime in range(2 * p, x, p):
            prime[non_prime] = 0

    return [p for p in prime if p != 0]

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

g = fractions.gcd(a,b)
if g == 1:
    print(1)
    exit()
p = primes(10**6)
ans = 1
for x in p:
    if g%x==0:
        ans +=1
if ans == 1:
    print(2)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
a,b=map(int,input().split())
tmp=gcd(a,b)

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

ans=factorization(tmp)

if len(ans)==1:
    print(1)
else:
    print(len(ans)+1)

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def solve(n):
    prime = 1
    m = n
    for i in range(2,int(sqrt(n))+1):
        pri = False
        while m%i==0:
            m//=i
            pri = True
        if pri:
            prime += 1
    if n!=1:
        prime+=1
    return prime
def main():
    A,B = MI()
    G = gcd(A,B)
    ans = solve(G)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
import itertools
import math
INF = 10**9
MOD = 10**9+7

A, B = map(int, input().split())
s1 = set()
for i in range(2, int(math.sqrt(A))+1):
    if A % i == 0:
        s1.add(i)
        while A % i == 0:
            A //= i
if A > 1:
    s1.add(A)
s2 = set()
for i in range(2, int(math.sqrt(B))+1):
    if B % i == 0:
        s2.add(i)
        while B % i == 0:
            B //= i
print(len(s1&s2)+1)

Submission status: Wrong Answer

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

divs = set()
m = 2
while m*m <= B:
    if A%m == B%m == 0:
        divs.add(m)
    m += 1

def is_prime(n):
    if n == 2: return True
    if n < 2 or n%2 == 0: return False
    m = 3
    while m*m <= n:
        if n%m == 0: return False
        m += 2
    return True

ans = 0
for d in divs:
    if is_prime(d):
        ans += 1
print(ans+1)

Submission status: Wrong Answer

Solution code:
a,b=map(int,input().split())
s=[1]*(int(max(a,b)**0.5)+1)
c=1
for i in range(2,int(max(a,b)**0.5)+1):
    if a%i==0 and b%i==0:
        if s[i]:
            c+=1
            for j in range(i,int(max(a,b)**0.5)+1,i):
                s[j]=0
print(c)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
a,b=map(int,input().split())
m=gcd(a,b)
pf={}
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1
if m==1:print(1)
else:print(len(pf.keys())+1)

Submission status: Wrong Answer

Solution code:
A,B = map(int,input().split())
def factoring(M,n=2):
    for i in range(n,int(M**0.5)+1):
        if M%i==0:
            ret = factoring(M//i,i)
            ret[i] = ret.get(i,0)+1
            return ret
    return {M:1}
print(len(set(factoring(A).keys()) & set(factoring(B).keys()))+1)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

a,b = na()

def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
        
f = gcd(a,b)

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
    
d = factorization(f)
k = len(d)+1 if len(d) != 1 else 1
print(k)

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

a, b = na()

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

g = gcd(a, b)
ans = 0
for d in range(2,1000001):
    e = 0
    while g % d == 0:
        g //= d
        e += 1
    if e > 0:
        ans += 1
if g > 0:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
def inpl(): return list(map(int, input().split()))
A, B = inpl()

def primes(N):
    sieve = [1]*(N+1)
    sieve[:2] = [0, 0]
    P = []
    for i in range(2, N+1):
        if sieve[i]:
            P.append(i)
            for j in range(2*i, N+1, i):
                sieve[j] = 0
    return P

P = primes(10**6)

ans = 1

for p in P:
    ans += int(A%p == B%p == 0)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
from bisect import bisect_left

a, b = getList()

def koyak(a, b):
    koyak = []

    for i in range(1, int(math.sqrt(max(a, b))) + 1):
        if a % i == 0 and b % i == 0:
            koyak.append(i)

    return koyak

ko = koyak(a, b)
ans = []
for k in ko:
    fl = True
    for an in ans:
        if k % an == 0 and an != 1:
            fl = False
            break
    if fl:
        ans.append(k)

print(len(ans))

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

a,b = na()

def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
        
f = gcd(a,b)

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
    
d = factorization(f)
print(len(d)+1)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()
    print((n-(n>>1))/n)
    return

#B
def B():
    n,k = LI()
    h = LI()
    ans = 0
    for i in h:
        if i >= k:
            ans += 1
    print(ans)
    return

#C
def C():
    n = I()
    a = LI()
    b = [(a[i],i+1) for i in range(n)]
    b.sort()
    ans = [b[i][1] for i in range(n)]
    print(*ans)
    return

#D
def D():
    def divisor(n):
        if n < 4:
            return set([n])
        res = set([1])
        i = 2
        m = n
        while i**2 <= n:
            if m%i == 0:
                while m%i == 0:
                    m //= i
                res.add(i)
            i += 1
        return res
    a,b = LI()
    if min(a,b) == 1:
        print(1)
        return
    s = divisor(a)
    t = divisor(b)
    s &= t
    print(len(s))
    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
a, b = map(int, input().split())

gcd = gcd(a, b)
ans = 1
for i in range(2, gcd//2 + 1):
    if gcd%i == 0:
        ans += 1
        while gcd%i == 0:
            gcd //= i
    if gcd < i:
        break
if ans == 1 and gcd != 1:
    ans = 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
a, b = map(int, input().split())

gcd = gcd(a, b)
ans = 1
for i in range(2, gcd):
    if gcd%i == 0:
        ans += 1
        while gcd%i == 0:
            gcd //= i
    if gcd < i:
        break
if ans == 1 and gcd != 1:
    ans = 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
a, b = map(int, input().split())

gcd = gcd(a, b)
ans = 1
for i in range(2, gcd + 1):
    if gcd%i == 0:
        ans += 1
        while gcd%i == 0:
            gcd //= i
    if gcd < i:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
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 main():
    a,b = map(int, input().split())
    c = cf(a,b)
    c.append(1)
    list_cf = sorted(c)
    list_ans = []*len(list_cf)
    for i in range(len(list_cf)):
        for j in range(i+1,len(list_cf)):
            if list_cf[i] != 1 and cf(list_cf[j],list_cf[i])!=0 and list_cf[j]%list_cf[i]==0:
                list_ans.append(list_cf[j])
    print(len(list_cf)-len(list(set(list_ans))))
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

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 main():
    a,b = map(int, input().split())
    c = cf(a,b)
    c.append(1)
    list_cf = sorted(c)
    cnt =0
    list_ans = []*len(list_cf)
    for i in range(len(list_cf)):
        for j in range(i+1,len(list_cf)):
            if list_cf[i] != 1 and cf(list_cf[j],list_cf[i])!=0 and list_cf[j]%list_cf[i]==0:
                list_ans.append(list_cf[j])
    
    print(len(list_cf)-len(list(set(list_ans))))
                
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
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(q):
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0
    while True:
        prime = min(A)
        if prime > math.sqrt(limit):
            break
        P.append(prime)
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
    for a in A:
        P.append(a)
    return P
import math
a,b=map(int,input().split())
l=make_divisors(a)+make_divisors(b)
l=[x for x in set(l) if l.count(x) > 1]
ans=1
cnt=[]
for i in l:
  if is_prime(i):
    cnt.append(i)
try:
  cnt2=eratosthenes(cnt[-1])
except:
  pass
for i in cnt:
  if i in cnt2:
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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(q):
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1
import math
a,b=map(int,input().split())
l=make_divisors(a)+make_divisors(b)
l=[x for x in set(l) if l.count(x) > 1]
ans=1
for i in l:
  if is_prime(i):
    if i==2:
      ans+=1
    else:
      flag=True
      for j in range(2,int(math.sqrt(i))+1):
        if i%j==0:
          flag=False
          break
      if flag:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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

def main(x):
  cnt = 1
  if x % 2 == 0:
    while x % 2 == 0:
      x //= 2
    cnt += 1
  for i in range(3, x+1, 2):
    if x % i == 0:
      while x % i == 0:
        x //= i
      cnt += 1
    if x == 1:
      break
  return cnt

print(main(gcdab))

Submission status: Time Limit Exceeded

Solution code:
import math

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

def main(x):
  cnt = 1
  if x % 2 == 0:
    while x % 2 == 0:
      x //= 2
    cnt += 1
  for i in range(3, 10**12, 2):
    if x % i == 0:
      while x % i == 0:
        x //= i
      cnt += 1
    if x == 1:
      break
  return cnt

print(main(gcdab))

Submission status: Time Limit Exceeded

Solution code:
import math

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

def soinsu(x):
  s = {}
  if x % 2 == 0:
    t = 0
    while x % 2 == 0:
      x //= 2
      t += 1
    s[2] = t
  for i in range(3, 10**12, 2):
    t = 0
    if x % i == 0:
      while x % i == 0:
        x //= i
        t += 1
      s[i] = t
    if x == 1:
      break
  return s

ans = len(soinsu(gcdab)) + 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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

def soinsu(x):
  s = {}
  if x % 2 == 0:
    s[2] = 0
    while x % 2 == 0:
      x //= 2
      s[2] += 1
  for i in range(3, 10**12, 2):
    if x % i == 0:
      s[i] = 0
      while x % i == 0:
        x //= i
        s[i] += 1
    if x == 1:
      break
  return s

ans = len(soinsu(gcdab)) + 1
print(ans)

Submission status: Time Limit Exceeded

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

def soinsu(x):
  s = {}
  if x % 2 == 0:
    s[2] = 0
    while x % 2 == 0:
      x //= 2
      s[2] += 1
  for i in range(3, 10**12, 2):
    if x % i == 0:
      s[i] = 0
      while x % i == 0:
        x //= i
        s[i] += 1
    if x == 1:
      break
  return s

AS = soinsu(a)
BS = soinsu(b)

cnt = 1

for i in AS:
  if i in BS:
    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

def gcd(A, B):
  if A < B:
    A, B = B, A
  while B > 0:
    temp = A % B
    A = B
    B = temp
  return A

gcd_num = gcd(A, B)

def prime(a):
  max_a = int(math.sqrt(a))
  d = dict()
  d[1] = 1
  i = 2
  while a != 1:
    if a % i == 0:
      a = a // i
      if i in d:
        d[i] += 1
      else:
        d[i] = 1
    else:
      i += 1
  return d
d = prime(gcd_num) 

print(len(d))

Submission status: Time Limit Exceeded

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

def prime_factorization(n):
  i=2
  prime=[]
  while i*i<=n or n>1:
    if n%i:
      i+=1
    else:
      n//=i
      prime.append(i)
      while n%i==0:
        n//=i
  if n>1:
    prime.append(n)
  return prime

print(len(prime_factorization(gcd))+1)

Submission status: Time Limit Exceeded

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

def prime_factorization(n):
  i=2
  prime=[]
  while i*i<=n or n>1:
    if n%i:
      i+=1
    else:
      prime.append(i)
      while n%i==0:
        n//=i
  if n>1:
    prime.append(n)
  return prime

print(len(prime_factorization(gcd))+1)

Submission status: Time Limit Exceeded

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

def prime_factorization(n):
  if n==1:
    return []
  else:
    i=2
    ans=[]
    while n>1:
      if n%i==0:
        n//=i
        ans.append(i)
        while n%i==0:
          n//=i
      i+=1
    return ans

A=prime_factorization(a)
B=prime_factorization(b)

ans=0
for _a in A:
  if B.count(_a):
    ans+=1
print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a,b):
  while b:
    a,b=b,a%b
  return a
a,b=map(int,input().split())
g=gcd(a,b)
def prime_table(n):
  n+=1
  table=[i if i%2 else 2 for i in range(n)]
  for i in range(3,n,2):
    if table[i]==i:
      for j in range(i*i,n,2*i):
        if table[j]==j:
          table[j]=i
  return table


def prime_fact(n,table):
  p=set()
  while n!=1:
    pp=table[n]
    p.add(pp)
    n//=pp
  return p

print(len(prime_fact(g,prime_table(g)))+1)

Submission status: Time Limit Exceeded

Solution code:
import math
a,b = (int(x) for x in input().split())
saidai = 1
c = []
def yakusuu(x,y):
    return(y,x % y)

def cont(z):
    n = 0
    while True:
        if n - int(z ** (1/2)) + 1 == 0:
            c.append(z)
            break
                
        for j in range(2,int(z ** (1/2)) + 1):
            if z % j == 0:
                z = z // j
                c.append(j)
                n = 0
                break
        else:
            n = n + 1

saidai = math.gcd(a,b)


cont(saidai)
if max(c) == 1:
   print(1)
   exit()
print(len(set(c)) + 1)

Submission status: Time Limit Exceeded

Solution code:
a,b = (int(x) for x in input().split())
saidai = 1
c = []
def yakusuu(x,y):
    return(y,x % y)

def cont(z):
    n = 0
    while True:
        if n - int(z ** (1/2)) + 1 == 0:
            c.append(z)
            break
                
        for j in range(2,int(z ** (1/2)) + 1):
            if z % j == 0:
                z = z // j
                c.append(j)
                n = 0
                break
        else:
            n = n + 1

if a > b:
   while True:
      if a % b == 0:
         saidai = b
         break
      a,b = yakusuu(a,b)

else:
   while True:
     if b % a == 0:
       saidai = a
       break
     b,a = yakusuu(b,a)


cont(saidai)
if max(c) == 1:
   print(1)
   exit()
print(len(set(c)) + 1)

Submission status: Time Limit Exceeded

Solution code:
from math import *

def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)
    return divisors

def eratosthenes(n):
    table = [0] * (n + 1)
    prime_list = []
    
    for i in range(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in range(i + i, n + 1, i):
                table[j] = 1
                
    return prime_list

a,b = map(int,input().split())
upper = 10**8
ans = set(eratosthenes(upper)) & make_divisors(a) & make_divisors(b)
print(len(ans) + 1)

Submission status: Time Limit Exceeded

Solution code:
from math import *

def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)
    return divisors

def eratosthenes(n):
    table = [0] * (n + 1)
    prime_list = []
    
    for i in range(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in range(i + i, n + 1, i):
                table[j] = 1
                
    return prime_list

a,b = map(int,input().split())
upper = 10**8
ans = set(eratosthenes(upper)) & make_divisors(a) & make_divisors(b)
print(len(ans) + 1)

Submission status: Time Limit Exceeded

Solution code:
import math
A,B=map(int,input().split())
#nの約数を全て求める
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
answers=[]
a=divisor(A)
b=divisor(B)
for a_ in a:
    if a_ in b:
        answers.append(a_)
n = len(answers)
numbers=[]
for i in range(2 ** n):
    number = []
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            number.append(answers[j])  # フラグが立っていたら bag に果物を詰める
    numbers.append(number)
del numbers[0]
answer=0
for number in numbers:
    ans=0
    for m in range(len(number)-1):
        for n in range(m+1,len(number)):
            a=math.gcd(number[m],number[n])
            if a!=1:
                ans=1
                break
    if ans==0:
        answer=max(answer,len(number))
print(answer)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
A, B = map(int, input().split())
g = gcd(A, B)
ans = 1
n = 2
while g > 1:
  if g % n == 0:
    ans += 1
  while g % n == 0:
    g //= n
  n += 1
print(ans)