🔎 Как проверить числа на взаимную простоту в Python: полезные советы и примеры кода

Как проверить числа на взаимную простоту в Python?

Есть несколько способов проверить, являются ли два числа взаимно простыми в Python.

1. С помощью алгоритма Евклида:

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def are_coprime(a, b):
    return gcd(a, b) == 1

a = 12
b = 7

if are_coprime(a, b):
    print(f"{a} и {b} - взаимно простые числа.")
else:
    print(f"{a} и {b} - не взаимно простые числа.")

2. С использованием встроенной функции math.gcd:

import math

a = 12
b = 7

if math.gcd(a, b) == 1:
    print(f"{a} и {b} - взаимно простые числа.")
else:
    print(f"{a} и {b} - не взаимно простые числа.")

Оба подхода возвращают True, если числа являются взаимно простыми, и False в противном случае.

Как проверить числа на взаимную простоту в Python?

Взаимная простота двух чисел означает, что эти числа не имеют общих делителей, кроме 1. Когда мы говорим о проверке чисел на взаимную простоту в Python, мы хотим определить, являются ли эти числа взаимно простыми или нет.

Алгоритм проверки чисел на взаимную простоту:

1. Нам нужно взять два числа, для которых мы хотим проверить взаимную простоту. Пусть эти числа называются a и b.

2. Наша задача - найти наибольший общий делитель (НОД) этих двух чисел.

3. НОД a и b равен 1, если эти числа взаимно просты; иначе НОД будет больше единицы.

4. Для нахождения НОД можно использовать алгоритм Эвклида. Этот алгоритм основан на том, что если a > b, то НОД(a, b) равен НОД(b, a mod b). Мы должны продолжать делить a на b, пока остаток (a mod b) не станет равным 0. Когда это произойдет, НОД будет равен b.

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

a = int(input("Введите первое число: "))
b = int(input("Введите второе число: "))

if gcd(a, b) == 1:
    print(f"{a} и {b} являются взаимно простыми числами.")
else:
    print(f"{a} и {b} не являются взаимно простыми числами.")
    

В этом коде мы используем функцию gcd для нахождения НОД. Если НОД равен 1, мы выводим сообщение, что числа являются взаимно простыми. Если НОД больше 1, мы выводим сообщение, что числа не являются взаимно простыми.

Примеры:

Пример 1:

Введите первое число: 35
Введите второе число: 42

Вывод:
35 и 42 не являются взаимно простыми числами.

Пример 2:

Введите первое число: 9
Введите второе число: 16

Вывод:
9 и 16 являются взаимно простыми числами.

Объяснение кода:

В начале кода мы определяем функцию gcd, которая использует рекурсивный алгоритм Эвклида для нахождения НОД.

Затем мы запрашиваем у пользователя два числа: a и b.

Далее мы вызываем функцию gcd с аргументами a и b и проверяем, равен ли НОД 1. Если да, то выводим сообщение о взаимной простоте чисел. Если НОД больше 1, то выводим сообщение о том, что числа не являются взаимно простыми.

Вывод:

Таким образом, мы можем легко проверить числа на взаимную простоту в Python, используя алгоритм Эвклида для нахождения НОД. Если НОД равен 1, то числа являются взаимно простыми, в противном случае они не являются взаимно простыми.