Sequenza di numeri coprimi
Due numeri \(a\) e \(b\) sono coprimi se il loro Massimo Comun Divisore (GCD) è 1. Il GCD è il più grande numero positivo che divide due numeri dati \(a\) e \(b\). Per esempio, i numeri 7 e 9 sono coprimi perché il loro GCD è 1.
Date due liste list1 e list2, il tuo compito è creare una nuova lista coprimes che contenga tutte le coppie coprime tratte da list1 e list2.
Ma prima, devi scrivere una funzione per il GCD usando il seguente algoritmo:
- verifica se \(b = 0\)
- se vero, restituisci \(a\) come GCD tra \(a\) e \(b\)
- se falso, vai al passo 2
- effettua la sostituzione \(a \leftarrow b\) e \(b \leftarrow a \% b\)
- torna al passo 1
Questo esercizio fa parte del corso
Esercitarsi con le domande di colloquio di coding in Python
esercizio interattivo pratico
Prova questo esercizio completando questo codice di esempio.
def gcd(a, b):
# Define the while loop as described
while ____:
temp_a = ____
a = ____
b = ____
# Complete the return statement
return ____