Reeks van coprime getallen
Twee getallen \(a\) en \(b\) zijn coprime als hun Greatest Common Divisor (GCD) gelijk is aan 1. GCD is het grootste positieve getal dat twee gegeven getallen \(a\) en \(b\) deelt. Bijvoorbeeld, de getallen 7 en 9 zijn coprime omdat hun GCD 1 is.
Gegeven twee lijsten list1 en list2, is je taak een nieuwe lijst coprimes te maken die alle coprime paren uit list1 en list2 bevat.
Maar eerst moet je een functie voor de GCD schrijven met het volgende algoritme:
- controleer of \(b = 0\)
- als dat zo is, return \(a\) als de GCD tussen \(a\) en \(b\)
- zo niet, ga naar stap 2
- maak een substitutie \(a \leftarrow b\) en \(b \leftarrow a \% b\)
- ga terug naar stap 1
Deze oefening maakt deel uit van de cursus
Oefenen met coding-interviewvragen in Python
Interactieve oefening met praktijkervaring
Probeer deze oefening door deze voorbeeldcode aan te vullen.
def gcd(a, b):
# Define the while loop as described
while ____:
temp_a = ____
a = ____
b = ____
# Complete the return statement
return ____