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:
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase
from typing import List
from math import gcd


def get_common_divisors(a: int, b: int) -> List[int]:
    i = 1
    ret = []
    # print(a, b)
    while i * i <= a:
        # print(i)
        if a % i == 0 and b % i == 0:
            ret.append(i)
            other = a // i
            if i == other:
                i += 1
                continue
            if a % other == 0 and b % other == 0:
                ret.append(other)
        i += 1

    ret.sort()
    return ret


def main() -> None:
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a

    divisors = get_common_divisors(a, b)
    ret = []

    for div in divisors:
        ok = True
        for i in ret:
            if gcd(i, div) != 1:
                ok = False
                break
        if ok:
            ret.append(div)

    print(len(ret))


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self, **kwargs):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

import itertools
import collections

class PrimeFactorize:
    def __init__(self, n):
        self.prime_factor_table = self.create_prime_factor_table(n)

    # O(NloglogN)
    def create_prime_factor_table(self, n):
        self.table = [0] * (n + 1)
        
        for i in range(2, n + 1):
            if self.table[i] == 0:
                for j in range(i + i, n + 1, i):
                    self.table[j] = i
        return self.table

    def prime_factor(self, n):
        prime_count = collections.Counter()
        
        while self.prime_factor_table[n] != 0:
            prime_count[self.prime_factor_table[n]] += 1
            n //= self.prime_factor_table[n]
        prime_count[n] += 1
        return prime_count
pf = PrimeFactorize(10**6+1)

for i in range(1,int(pow(A,0.5)//1)+1):
    if A%i==0 and 0 == pf.prime_factor_table[i]:
        A_DIVS.add(i)

for i in range(1,int(pow(B,0.5)//1)+1):
    if B%i==0 and 0 == pf.prime_factor_table[i]:
        B_DIVS.add(i)

print(len(A_DIVS&B_DIVS))

Submission status: Wrong Answer

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

#N以下の素数れっきょエラトステネス
def prime(N):
    lsprime = [0,0]+[1 for i in range(N-1)]
    lsprime2 = []
    for i in range(N+1):
        if lsprime[i] == 0:
            continue
        lsprime2.append(i)
        k = i
        while i <= N:
            lsprime[i] = 0
            i += k
    return lsprime2

lsprime = prime(int(C**(1/2))+1)
ans = 0
for i in lsprime:
    if C % i == 0:
        ans += 1
print(ans+1)

Submission status: Wrong Answer

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

gcd = gcd(a, b)
ans = 1
for i in range(2, int(gcd**0.5) + 2):
    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: Wrong Answer

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

def get_prime(n):
    num = [True]*(n + 1)
    for i in range(2, int(n**0.5) + 1):
        if num[i]:
            for j in range(i*2, n + 1, i):
                num[j] = False
    ans = [i for i in range(1, n) if num[i]]
    return ans

gcd = gcd(a, b)
p = get_prime(int(gcd**0.5) + 2)

ans = 0
for i in p:
    if gcd%i == 0:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

def prime_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)

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

setA=set(prime_factorization(A))
setB=set(prime_factorization(B))
setAB=setA &setB
print(len(setAB)+1)

Submission status: Wrong Answer

Solution code:
a,b=map(int,input().split())
ans=1
for i in range(2,int(min(a,b)**(1/2))+1):
  if a%i==0 and b%i==0:
    flg=0
    for j in range(2,int(i**(1/2))+1):
      if i%j==0:
        flg=1
    if flg==0:
      ans+=1
print(ans)

Submission status: Wrong Answer

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


def prime_numbers(N):
    n = N
    res = []
    for i in range(2, n):
        if i * i >= n: break
        if N % i != 0: continue
        while N % i == 0:
            N //= i
        res.append(i)
    res.append(N)
    return res


a = prime_numbers(A)
b = prime_numbers(B)
ans = min(len(a), len(b))
print(ans)

Submission status: Wrong Answer

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


def prime_numbers(N):
    n = N
    res = []
    for i in range(2, n):
        if i * i >= n: break
        if N % i != 0: continue
        while N % i == 0:
            N //= i
        res.append(i)
    res.append(N)
    return res


a = prime_numbers(A)
b = prime_numbers(B)
ans = min(len(a), len(b)) + 1
print(ans)

Submission status: Wrong Answer

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


def prime_numbers(N):
    n = N
    res = []
    for i in range(2, n):
        if i * i >= N: break
        if N % i != 0: continue
        while N % i == 0:
            N //= i
        res.append(i)
    res.append(N)
    return res


a = prime_numbers(A)
b = prime_numbers(B)
ans = min(len(a), len(b)) + 1
print(ans)

Submission status: Wrong Answer

Solution code:
from math import gcd,sqrt,floor
a,b = map(int,input().split())
c = gcd(a,b)
x = []
for i in range(1,floor(sqrt(c))+1):
    if c % i == 0:
        x.append(i)
        x.append(c//i)
x.sort()
y = []
i = 1
while c > 1 and i < len(x):
    if c % x[i] == 0:
        y.append(x[i])
        c = c // 2
    else:
        i += 1
if c != 1:
    y.append(c)
print(len(set(y))+1)

Submission status: Wrong Answer

Solution code:
from math import gcd,sqrt,floor
a,b = map(int,input().split())
c = gcd(a,b)
x = []
for i in range(1,floor(sqrt(c))+1):
    if c % i == 0:
        x.append(i)
        x.append(c//i)
x.sort()
y = []
i = 1
while c > 1 and i < len(x):
    if c % x[i] == 0:
        y.append(x[i])
        c = c // 2
    else:
        i += 1
print(len(set(y))+1)

Submission status: Wrong Answer

Solution code:
from math import gcd,sqrt,floor
a,b = map(int,input().split())
c = gcd(a,b)
x = []
for i in range(1,floor(sqrt(c))+1):
    if c % i == 0:
        x.append(i)
        x.append(c//i)
x.sort()
y = []
i = 1
while c > 1 and i < len(x):
    if c % x[i] == 0:
        y.append(x[i])
        c = c // 2
    else:
        i += 1
print(len(y)+1)

Submission status: Wrong Answer

Solution code:
from math import gcd,sqrt,floor
a,b = map(int,input().split())
c = gcd(a,b)
x = []
for i in range(2,floor(sqrt(c))+1):
    if c % i == 0:
        x.append(i)
        x.append(c//i)
x.sort()
y = []
i = 0
while c > 1 and i < len(x):
    if c % x[i] == 0:
        y.append(x[i])
        c = c // 2
    else:
        i += 1
print(len(y)+1)

Submission status: Wrong Answer

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

def factorization(n):
    arr=[]
    tmp=n
    for i in range(2,int(n**0.5)+1):
        while tmp%i==0:
            tmp//=i
            arr.append(i)
    if tmp!=1:
        arr.append(tmp)
    if arr==[]:
        arr.append(n)
    return list(set(arr))

ans=len(factorization(math.gcd(a,b)))
print(ans+1 if ans!=1 else 1)

Submission status: Wrong Answer

Solution code:
A, B = map(int, input().split())
a = set([])
b = set([])
n = 1
while n**2 <= max(A, B):
  if A%n == 0 and n**2 <= A:
    a.add(n)
    a.add(A//n)
  if B%n == 0 and n**2 <= B:
    b.add(n)
    b.add(B//n)
  n += 1
ab = a & b
ab = list(ab)
answer = 0
for i, n in enumerate(ab):
  prime = True
  for j, m in enumerate(ab):
    if i != j and n%m == 0:
      prime = False
      break
  if prime:
    answer += 1
print(answer+1)

Submission status: Wrong Answer

Solution code:
A, B = map(int, input().split())
a = set([])
b = set([])
n = 2
while n**2 <= max(A, B):
  if A%n == 0 and n**2 <= A:
    a.add(n)
    a.add(A//n)
  if B%n == 0 and n**2 <= B:
    b.add(n)
    b.add(B//n)
  n += 1
ab = a & b
ab = list(ab)
answer = 0
for i, n in enumerate(ab):
  prime = True
  for j, m in enumerate(ab):
    if i != j and n%m == 0:
      prime = False
      break
  if prime:
    answer += 1
print(answer+1)

Submission status: Wrong Answer

Solution code:
# a, bを素因数分解する。O(ルートa + ルートb)
# 共通の素因数を見つける。O(loga + logb)

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

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_prime = factorization(a)
b_prime = factorization(b)
ans = 0
for ap in a_prime:
  for bp in b_prime:
    if ap[0] == bp[0]:
      ans += 1
      break
print(ans+1)

Submission status: Wrong Answer

Solution code:
import math
import collections

def prime_factorize(n):
    s = []
    while n % 2 == 0:
        s.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            s.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        s.append(n)
    return s

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

g = math.gcd(a, b)
c = collections.Counter(prime_factorize(g))

print(sum(c.values()) + 1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import math
from functools import reduce


a,b=map(int,input().split())
g=math.gcd(a,b)
cc=[]
for i in range(1,int(math.sqrt(a))+1):
    if a%i==0 and b%i==0:
        cc.append(i)
ans=0
def isPrime(n):
    if n==1:
        return 1
    else:
        for p in range(1, int(math.sqrt(n))+1):
            if n % p == 0:
                return 0
        return 1
  
for i in cc:
    ans+=isPrime(i)
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import math
a,b=map(int,input().split())
g=math.gcd(a,b)
cc=[]
for i in range(1,int(math.sqrt(a))+1):
    if a%i==0 and b%i==0:
        cc.append(i)

ans=0
def isPrime(n):
  if n < 2:
    # 2未満は素数でない
    return 1
  if n == 2:
    # 2は素数
    return 1
  for p in range(2, n):
      if n % p == 0:
        # nまでの数で割り切れたら素数ではない
        return 0
  # nまでの数で割り切れなかったら素数
  return 1
  
for i in cc:
    ans+=isPrime(i)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
#試し割法
def trial_division(n):
    #素因数を格納するリスト
    factor = []
    #2から√n以下の数字で割っていく
    tmp = int(math.sqrt(n)) + 1
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    #リストが空ならそれは素数
    if not factor:
        factor.append(1)
        return factor
    else:
        factor.append(1)
        factor.append(n)
        return factor
A,B=map(int,input().split())
A_primes=trial_division(A)
B_primes=trial_division(B)
primes=[]
for p in A_primes:
  if p in B_primes:
    primes.append(B_primes.pop(B_primes.index(p)))
if A==1 and B==1:
  primes=[]
print(len(list(set(primes))))

Submission status: Wrong Answer

Solution code:
import math
#試し割法
def trial_division(n):
    #素因数を格納するリスト
    factor = []
    #2から√n以下の数字で割っていく
    tmp = int(math.sqrt(n)) + 1
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    #リストが空ならそれは素数
    if not factor:
        factor.append(1)
        return factor
    else:
        factor.append(1)
        factor.append(n)
        return factor
A,B=map(int,input().split())
A_primes=trial_division(A)
B_primes=trial_division(B)
primes=[]
for p in A_primes:
  if p in B_primes:
    primes.append(B_primes.pop(B_primes.index(p)))
print(len(list(set(primes))))

Submission status: Wrong Answer

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

Solution code:
import math

def soinsu(n):
    factor = set()
    tmp = int(math.sqrt(n)) + 1
    factor.add(1)
    factor.add(n)
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor.add(num)
    return factor

a,b=map(int,input().split())
A=soinsu(a)
B=soinsu(b)

print(len(A&B))

Submission status: Wrong Answer

Solution code:
import math

def soinsu(n):
    factor = []
    tmp = int(math.sqrt(n)) + 1
    factor.append(1)
    factor.append(n)
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    return factor

a,b=map(int,input().split())
A=set(soinsu(a))
B=set(soinsu(b))

print(len(A&B))

Submission status: Wrong Answer

Solution code:
def fact(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])
    if temp!=1:
        arr.append([temp])
    if arr==[]:
        arr.append([n])
    return arr
def main():
  count = 1
  A, B = map(int, input().split())
  A_lis = fact(A)
  B_lis = fact(B)
  if A == B == 1:
    print(1)
    exit()
  for i in range(len(A_lis)):
    for j in range(i, len(B_lis)):
      if A_lis[i] == B_lis[j]:
        count += 1
  print(count)
  
main()

Submission status: Wrong Answer

Solution code:
def fact(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])
    if temp!=1:
        arr.append([temp])
    if arr==[]:
        arr.append([n])
    return arr
def main():
  count = 1
  A, B = map(int, input().split())
  A_lis = fact(A)
  B_lis = fact(B)
  for i in range(len(A_lis)):
    for j in range(i, len(B_lis)):
      if A_lis[i] == B_lis[j]:
        count += 1
  print(count)
  
main()

Submission status: Wrong Answer

Solution code:
def factorization(n):
    arr = [1]
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            
            while temp%i==0:
                temp //= i
            arr.append(i)
    if len(arr)==1:
      arr.append(n)
    return arr 
A, B = map(int,input().split())
print(len(set(factorization(A))&set(factorization(B))))

Submission status: Wrong Answer

Solution code:
def factorization(n):
    arr = [1]
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            
            while temp%i==0:
                temp //= i
            arr.append(i)
    return arr 
A, B = map(int,input().split())
print(len(set(factorization(A))&set(factorization(B))))

Submission status: Wrong Answer

Solution code:
def factorization(n):
    arr = [1,n]
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            
            while temp%i==0:
                temp //= i
            arr.append(i)
    return arr 
A, B = map(int,input().split())
print(len(set(factorization(A))&set(factorization(B))))

Submission status: Wrong Answer

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

def prime_factorization(n):
  i=2
  prime=[]
  if n%i:
    i+=1
  else:
    n//=i
    prime.append(2)
    while n%i==0:
      n//=i
  while i*i<=n:
    if n%i:
      i+=2
    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: Wrong Answer

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

def prime_factorization(n):
  if n==1:
    return []
  else:
    i=2
    ans=[]
    k=int(n**0.5)+1
    for j in range(2,k+1):
      if n==1: break
      if n%j==0:
        n//=j
        ans.append(j)
        while n%j==0:
          n//=j
    if len(ans):
      return ans
    else:
      return [n]

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

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

def prime_factorization(n):
  if n==1:
    return []
  else:
    i=2
    ans=[]
    k=int(n**0.5)+1
    for j in range(2,k+1):
      if n==1: break
      if n%j==0:
        n//=j
        ans.append(j)
        while n%j==0:
          n//=j
    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: Wrong Answer

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

def prime_factorization(n):
  if n==1:
    return []
  else:
    i=2
    ans=[]
    k=int(n**0.5)+1
    for j in range(2,k):
      if n==1: break
      if n%j==0:
        n//=j
        ans.append(j)
        while n%j==0:
          n//=j
    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: Wrong Answer

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

def prime_factorization(n):
  if n==1:
    return []
  else:
    i=2
    ans=[]
    for j in range(2,int(n**0.5+1)):
      if n%j==0:
        n//=j
        ans.append(j)
        while n%j==0:
          n//=j
    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: Wrong Answer

Solution code:
import math

a,b=map(int,input().split())
#gcd=math.gcd(a,b)
#print(gcd)
ans=[]

n=2
while n<=min(a,b):
  flg=0
  if a%n==0:
    a//=n
    flg+=1
  if b%n==0:
    b//=n
    flg+=1
    if flg==2:
      ans.append(n)
  n+=1
ans.append(1)
print(len(ans))

Submission status: Wrong Answer

Solution code:
import math

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

def is_prime(n):
  if n==1:
    return True
  i=2
  while i<=n**0.5:
    if n%i==0:
      return False
      break
    i+=1
  return True

ans=0
for i in range(1,gcd+1):
  if a%i==0 and b%i==0:
    if is_prime(i):
      #print(i)
      ans+=1
if ans<=2:
  print(1)
else:  
  print(ans)

Submission status: Wrong Answer

Solution code:
def prime_list(n=10**6+1):
    res = []
    tmp = [1 for _ in range(n)]
    tmp[0] = 0
    tmp[1] = 0
    i = 2
    while i < len(tmp):
        j = i*2
        while tmp[i] == 1 and j < len(tmp):
            tmp[j] = 0
            j += i
        i += 1

    for i, j in enumerate(tmp):
        if j:
            res.append(i)

    return res

def check_prime(n):
    i = 2
    while i*i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

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

prime_divisord = []
primes = prime_list()

if b < a:
    a, b = b, a

for i in primes:
    if a % i == 0:
        if check_prime(a//i):
            prime_divisord.append(a//i)
        prime_divisord.append(i)
i = 2
flag = 1
while i*i <= a:
    if a % i == 0:
        flag = 0
        break
    i += 1
if a == 1:
    flag = 0
if flag:
    prime_divisord.append(a)

common_divisors = []

for i in prime_divisord:
    if b % i == 0:
        common_divisors.append(i)
# print(common_divisors)
print(len(common_divisors) + 1)

Submission status: Wrong Answer

Solution code:
def prime_list(n=10**6+1):
    res = []
    tmp = [1 for _ in range(n)]
    tmp[0] = 0
    tmp[1] = 0
    i = 2
    while i < len(tmp):
        j = i*2
        while tmp[i] == 1 and j < len(tmp):
            tmp[j] = 0
            j += i
        i += 1

    for i, j in enumerate(tmp):
        if j:
            res.append(i)

    return res

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

prime_divisord = []
primes = prime_list()

if b < a:
    a, b = b, a

for i in primes:
    if a % i == 0:
        prime_divisord.append(i)
i = 2
flag = 1
while i*i <= a:
    if a % i == 0:
        flag = 0
        break
    i += 1
if a == 1:
    flag = 0
if flag:
    prime_divisord.append(a)

common_divisors = []

for i in prime_divisord:
    if b % i == 0:
        common_divisors.append(i)
        
print(len(common_divisors) + 1)

Submission status: Wrong Answer

Solution code:
def prime_list(n=10**6+1):
    res = []
    tmp = [1 for _ in range(n)]
    tmp[0] = 0
    tmp[1] = 0
    i = 2
    while i < len(tmp):
        j = i*2
        while tmp[i] == 1 and j < len(tmp):
            tmp[j] = 0
            j += i
        i += 1

    for i, j in enumerate(tmp):
        if j:
            res.append(i)

    return res

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

prime_divisord = []
primes = prime_list()

if b < a:
    a, b = b, a

for i in primes:
    if a % i == 0:
        prime_divisord.append(i)
i = 2
flag = 1
while i*i < a:
    if a % i == 0:
        flag = 0
        break
    i += 1
if a == 1:
    flag = 0
if flag:
    prime_divisord.append(a)

common_divisors = []

for i in prime_divisord:
    if b % i == 0:
        common_divisors.append(i)
        
print(len(common_divisors) + 1)

Submission status: Wrong Answer

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)

c=1
for i in range(2,10**6+1):
  if g%i==0:
    c+=1
    while g%i==0:
      g//=i
if g:
  c+=1
print(c)

Submission status: Wrong Answer

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)

c=1
for i in range(2,10**6+1):
  if g%i==0:
    c+=1
    while g%i==0:
      g//=i
print(c)

Submission status: Wrong Answer

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 len(c) == 1:
   print(1)
   exit()
print(len(set(c)) + 1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

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

List = deque()  # リストの初期化
answer = []

for i in range(1, max(min(A, B, 10 ** 6 + 1), 2)):
    if A % i == 0 and B % i == 0:
        List.append(i)

dp = [0] * (10 ** 6 + 1)

for n in List:

    if dp[n] != 1:
        answer.append(n)
        if n != 1:
            for i in range(1, 10 ** 6 + 1):

                if n * i < 10 ** 6 + 1:
                    dp[n * i] = 1
                else:
                    break

if A == B and (A in List) == False:
    for n in answer:
        if A % n == 0:
            print(len(answer))
            sys.exit()

    print(len(answer) + 1)

else:
    print(len(answer))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

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

List = deque()  # リストの初期化
answer = []

for i in range(1, max(min(A, B, 10 ** 6 + 1),2)):
    if A % i == 0 and B % i == 0:
        List.append(i)

dp = [0] * (10 ** 6 + 1)

for n in List:

    if dp[n] != 1:
        answer.append(n)
        if n != 1:
            for i in range(1, 10 ** 6 + 1):
    
                if n * i < 10 ** 6 + 1:
                    dp[n * i] = 1
                else:
                    break

print(len(answer))

Submission status: Wrong Answer

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**7
ans = set(eratosthenes(upper)) & make_divisors(a) & make_divisors(b)
print(len(ans) + 1)

Submission status: Wrong Answer

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 = int(sqrt(max(a,b))) + 1
ans = set(eratosthenes(upper)) & make_divisors(a) & make_divisors(b)
print(len(ans) + 1)

Submission status: Wrong Answer

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 = int(sqrt(min(a,b))) + 1
ans = set(eratosthenes(upper)) & make_divisors(a) & make_divisors(b)
print(len(ans) + 1)

Submission status: Wrong Answer

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 = int(sqrt(min(a,b))) + 1
pl = set(eratosthenes(upper))
common_factor = make_divisors(a)&make_divisors(b)
ans = 0
for i in common_factor:
    if i in pl:
        ans += 1
print(ans + 1)

Submission status: Wrong Answer

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 = int(sqrt(min(a,b))) + 1
pl = set(eratosthenes(upper))
common_factor = make_divisors(a)|make_divisors(b)
ans = 0
for i in common_factor:
    if i in pl:
        ans += 1
print(ans + 1)

Submission status: Wrong Answer

Solution code:
from math import *
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 = int(sqrt(min(a,b))) + 1
pl = set(eratosthenes(upper))
common_factor = [ i for i in range(1,upper) if a % i == 0 and b % i == 0]
ans = 0
for i in common_factor:
    if i in pl:
        ans += 1
print(ans + 1)

Submission status: Wrong Answer

Solution code:
from math import *
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())
pl = set(eratosthenes(int(sqrt(min(a,b)))))
common_factor = [ i for i in range(1,int(sqrt(min(a,b)))) if a % i == 0 and b % i == 0]
ans = 0
for i in common_factor:
    if i in pl:
        ans += 1
print(ans + 1)