[Codility] 12.2 CommonPrimeDivisors

CommonPrimeDivisors 문제 풀기

$gcd(x, y)=1$이면 ($x, y$가 서로소라면) 공유하는 소수(소인수)가 없다는 뜻이다.

$g = gcd(x, y)$라 하자. $gcd(x, g)=1$이라면 $x, y$사이에 공유하지 않는 소수가 존재한다는 뜻이므로 이를 이용한다.

x가 gcd로 나누어지면 x = x // gcd를 하여 중복되는 소수를 제외한다. 그리고 x = 1이 되는 순간 x와 gcd는 공유하는 소수만 존재한다는 뜻이다.
하지만 그 전에 gcd = 1이 되는 순간 공유하지 않는 소수가 존재한다는 것이다.

def getGCD(a, b):
    if a < b:
        a, b = b, a
    if a % b == 0:
        return b
    return getGCD(b, a % b)

def solution(A, B):
    ret = 0
    for i in range(len(A)):
        # a와 b가 공유하는 소수만 이루어여있다면 True, 아니면 False
        flag = True
        
        a, b = A[i], B[i]
        G = getGCD(a, b)

        while a != 1:
            g = getGCD(a, G)
            # a가 1이 아닌데 이미 a와 gcd가 서로소면
            # 공유하지 않는 소수가 존재한다
            if g == 1:
                flag = False
                break
            a //= g

        # 이미 a가 gcd와 공유하지 않는 소수가 존재하면 False
        # b는 더이상 관찰할 필요가 없다.
        if not flag:
            continue
        
        while b != 1:
            g = getGCD(b, G)
            # b가 1이 아닌데 이미 b와 gcd가 서로소면
            # 공유하지 않는 소수가 존재한다
            if g == 1:
                flag = False
                break
            b //= g
        
        # a와 b가 공유하는 소수만으로 이루어져있다면 답 개수 증가
        if flag:
            ret += 1

    return ret