서로소 수 쌍 만들기
두 수 $a$와 $b$의 최대공약수(Greatest Common Divisor, GCD)가 1이면 서로소라고 합니다. GCD는 주어진 두 수 $a$와 $b$를 나눌 수 있는 가장 큰 양의 수를 뜻해요. 예를 들어, 7과 9의 GCD는 1이므로 두 수는 서로소입니다.
두 리스트 list1과 list2가 주어졌을 때, 두 리스트에서 서로소인 쌍만 담은 새로운 리스트 coprimes를 만들어 보세요.
그전에 먼저 다음 알고리즘을 이용해 GCD 함수를 작성해야 합니다:
- $b = 0$인지 확인합니다.
- 맞다면, $a$를 $a$와 $b$의 GCD로 반환합니다.
- 아니라면, 2단계로 이동합니다.
- 치환을 수행합니다: \(a \leftarrow b\), \(b \leftarrow a \% b\)
- 1단계로 돌아갑니다.
이 연습은 강의의 일부입니다
Python으로 코딩 인터뷰 문제 연습하기
실습형 인터랙티브 연습
이 예제를 이 샘플 코드를 완성하여 풀어보세요.
def gcd(a, b):
# Define the while loop as described
while ____:
temp_a = ____
a = ____
b = ____
# Complete the return statement
return ____