[Codility/Lesson12]CommonPrimeDivisors

| 1트

def solution(A, B):
    count = 0
    for (a, b) in zip(A, B):
        gcd_value = gcd(a, b)
        
        if gcd_value % (a / gcd_value) == 0 and gcd_value % (b / gcd_value) == 0:
            count += 1 

    return count 

def gcd(M, N):
    if M == N:
        return M
    if M > N:
        return gcd(M - N, N)
    else:
        return gcd(N - M, M)

• M, N의 대소 관계가 정해져있지 않기 때문에 위와 같이 해보았다

| 2트

def solution(A, B):
    count = 0
    for (a, b) in zip(A, B):
        
        gcd_value = gcd(max(a, b), min(a, b))

        if gcd_value % (a / gcd_value) == 0 and gcd_value % (b / gcd_value) == 0:
            count += 1 
    return count 

def gcd(N, M):
    if M == 0:
        return N 
    return gcd(M, N % M)

• gcd 함수의 방식만 바꾸었는데도 timeout은 없어졌다
• 절대 처음 방식은 사용하지 말아야지

결과 1, 결과 2

| 3트

def solution(A, B):
    # write your code in Python 3.6
    count = 0
    for (a, b) in zip(A, B):
        ab_gcd = gcd(max(a,b), min(a,b))

        a_gcd = gcd(max(a / ab_gcd, ab_gcd), min(a/ ab_gcd, ab_gcd))
        b_gcd = gcd(max(b / ab_gcd, ab_gcd), min(b/ ab_gcd, ab_gcd))

        a_div_gcd = a / ab_gcd / a_gcd
        b_div_gcd = b / ab_gcd / b_gcd

        #print(a_div_gcd, b_div_gcd)
        if a_div_gcd == 1 and b_div_gcd == 1:
            count += 1 
    return count 


def gcd(N, M):
    if M == 0:
        return N 
    return gcd(M, N % M)

• 한번 더 나눈 결과를 사용했는데 같았다

결과는 여기에

| 4트

def solution(A, B):
    # write your code in Python 3.6
    count = 0
    for (a, b) in zip(A, B):
        ab_gcd = gcd(max(a,b), min(a,b))

        a /= ab_gcd 
        b /= ab_gcd 

        a_gcd , b_gcd = ab_gcd, ab_gcd

        while a_gcd != 1: 
            a_gcd = gcd(a, a_gcd)
            a /= a_gcd
        
        while b_gcd != 1:
            b_gcd = gcd(b, b_gcd)
            b /= b_gcd 


        if a == 1 and b == 1 :
            count += 1 

    return count 


def gcd(N, M):
    if M == 0:
        return N 
    return gcd(M, N % M)

• 최대공약수가 1이 될 때 까지 진행했더니 성공했다

결과는 여기에