Coprime number sequence
Two numbers \(a\) and \(b\) are coprime if their Greatest Common Divisor (GCD) is 1. GCD is the largest positive number that divides two given numbers \(a\) and \(b\). For example, the numbers 7 and 9 are coprime because their GCD is 1.
Given two lists list1 and list2, your task is to create a new list coprimes that contains all the coprime pairs from list1 and list2.
But first, you need to write a function for the GCD using the following algorithm:
- check if \(b = 0\)
- if true, return \(a\) as the GCD between \(a\) and \(b\)
- if false, go to step 2
- make a substitution \(a \leftarrow b\) and \(b \leftarrow a \% b\)
- go back to step 1
Latihan ini merupakan bagian dari kursus
Practicing Coding Interview Questions in Python
Latihan interaktif langsung praktik
Cobalah latihan ini dengan melengkapi kode contoh ini.
def gcd(a, b):
# Define the while loop as described
while ____:
temp_a = ____
a = ____
b = ____
# Complete the return statement
return ____