Sekvens av relativt prima tal
Två tal \(a\) och \(b\) är relativt prima om deras största gemensamma divisor (GGD) är 1. GGD är det största positiva talet som delar både \(a\) och \(b\). Till exempel är talen 7 och 9 relativt prima eftersom deras GGD är 1.
Given två listor list1 och list2 är din uppgift att skapa en ny lista coprimes som innehåller alla relativt prima par från list1 och list2.
Men först behöver du skriva en funktion för GGD med följande algoritm:
- kontrollera om \(b = 0\)
- om sant, returnera \(a\) som GGD för \(a\) och \(b\)
- om falskt, gå till steg 2
- gör substitutionen \(a \leftarrow b\) och \(b \leftarrow a \% b\)
- gå tillbaka till steg 1
Den här övningen är en del av kursen
Öva på kodningsintervjufrågor i Python
Interaktiv övning med praktiskt arbete
Testa den här övningen genom att slutföra den här exempelkoden.
def gcd(a, b):
# Define the while loop as described
while ____:
temp_a = ____
a = ____
b = ____
# Complete the return statement
return ____