НачатьНачать бесплатно

Последовательность взаимно простых чисел

Два числа \(a\) и \(b\) называются взаимно простыми, если их Наибольший Общий Делитель (НОД) равен 1. НОД — это наибольшее положительное число, на которое делятся оба числа \(a\) и \(b\). Например, числа 7 и 9 являются взаимно простыми, поскольку их НОД равен 1.

Даны два списка list1 и list2. Ваша задача — создать новый список coprimes, содержащий все пары взаимно простых чисел из list1 и list2.

Но сначала необходимо написать функцию для вычисления НОД по следующему алгоритму:

  1. Проверьте, равно ли \(b = 0\)
    • если да, верните \(a\) как НОД чисел \(a\) и \(b\)
    • если нет, перейдите к шагу 2
  2. Выполните замену \(a \leftarrow b\) и \(b \leftarrow a \% b\)
  3. Вернитесь к шагу 1

Это упражнение является частью курса

Практика задач для собеседования по программированию на Python

Посмотреть курс

Интерактивное практическое упражнение

Попробуйте выполнить это упражнение, дополнив этот пример кода.

def gcd(a, b):
    # Define the while loop as described
    while ____:
        temp_a = ____
        a = ____
        b = ____ 
    # Complete the return statement
    return ____
Редактировать и запускать код