ПочатиПочніть безкоштовно

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

Два числа \(a\) і \(b\) є взаємно простими, якщо їхній найбільший спільний дільник (GCD) дорівнює 1. GCD — це найбільше додатне число, яке ділить обидва задані числа \(a\) і \(b\). Наприклад, числа 7 і 9 взаємно прості, оскільки їхній GCD дорівнює 1.

Маючи два списки list1 і list2, ваше завдання — створити новий список coprimes, який міститиме всі пари взаємно простих чисел із list1 і list2.

Але спочатку вам потрібно написати функцію для обчислення GCD, використовуючи такий алгоритм:

  1. перевірте, чи \(b = 0\)
    • якщо так, поверніть \(a\) як GCD для \(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 ____
Редагувати та запускати код