Dãy số nguyên tố cùng nhau
Hai số \(a\) và \(b\) là nguyên tố cùng nhau nếu Ước số chung lớn nhất (GCD) của chúng bằng 1. GCD là số dương lớn nhất chia hết cho cả hai số \(a\) và \(b\). Ví dụ, 7 và 9 là nguyên tố cùng nhau vì GCD của chúng bằng 1.
Với hai danh sách list1 và list2, nhiệm vụ của bạn là tạo danh sách mới coprimes chứa tất cả các cặp nguyên tố cùng nhau từ list1 và list2.
Trước hết, bạn cần viết hàm tính GCD theo thuật toán sau:
- kiểm tra nếu \(b = 0\)
- nếu đúng, trả về \(a\) là GCD giữa \(a\) và \(b\)
- nếu sai, chuyển sang bước 2
- thực hiện phép gán thay thế \(a \leftarrow b\) và \(b \leftarrow a \% b\)
- quay lại bước 1
Bài tập này là một phần của khóa học
Luyện tập câu hỏi phỏng vấn lập trình bằng Python
Bài tập tương tác thực hành trực tiếp
Hãy thử làm bài tập này bằng cách hoàn thành đoạn mã mẫu này.
def gcd(a, b):
# Define the while loop as described
while ____:
temp_a = ____
a = ____
b = ____
# Complete the return statement
return ____